Hilfe gesucht bei Verständnis und Portierung von Python Programm

Code-Stücke können hier veröffentlicht werden.
Antworten
alfware17
User
Beiträge: 51
Registriert: Montag 9. September 2024, 17:53

Hallo, ich hänge wirklich schon seit Wochen an dem Problem, wie ich ein 16x16 Sudoku lösen kann und mehr und mehr macht sich Verzweiflung und Frustration breit. Mein 9x9 Sudoku funktioniert relativ gut und einfach, sowohl in Lazararus als auch in Python und Java testweise. Es geht mit einfachem Backtracking.
Ok bei 16x16 ist der Suchraum zu groß, ich habe versucht neue Ideen und Algorithmen ein- und davorzubauen, alles bisher erfolglos. Meine Impulse erhalte ich aus fremdem Code und/oder von ChatGPT, welcher mir manchmal bei der sprachlichen Umwandlung hilft, manchmal aber auch nur Schlagworte und Vorschläge hat und die dann aber nicht in meinem Code einbauen kann.

Nun habe ich auf Github eine funktionierende Lösung für 16x16 gefunden, die zwar mit einem fest verdrahteten Sudoku arbeitete, hier habe ich aber selbst eine Eingabe/Ausgabe/Anzeige geschrieben in Python, die soweit ich es sehe auch gut funktioniert. Der Lösungsalgorithmus ist der originale, den habe ich so übernommen, sprich ab "SolveSudoku", bis zum Import und dann wieder ab Save/Print habe ich gemacht - man sieht sicher auch den Bruch im Stil. Hier ist das lauffähige Ergebnis

Code: Alles auswählen

import math;
from collections import defaultdict;
import itertools;
import functools;
import copy;
import time;
import sys;

@functools.lru_cache()
def intSqrt (n):
    "Computes integer square-root of perfect squares.";
    rootN = int(math.sqrt(n));
    if rootN ** 2 != n:
        raise ValueError(f"Expected a perfect square, not: {n}");
    return rootN;

def importGame (s):
    "Reads a string-represented game as a list of rows.";
    rows = [];
    for line in s.splitlines():
        if line.strip():
            rows.append([]);
            for word in line.split():
                if word.isdigit():
                    rows[-1].append(int(word));
                elif word == "." * len(word):
                    rows[-1].append(".");
                else:
                    raise ValueError(f"Unexpected word: {word}");
    n = len(rows);
    rootN = intSqrt(n);
    assert rootN ** 2 == n;
    for i in range(n):
        if len(rows[i]) != n:
            raise ValueError("Game-grid isn't a perfect square.");
    return rows;

def formatCell(cell):
    """Formats cell value for display; converts 10-15 to A-F."""
    try:
        cell = int(cell)  # Versuche, den Zellenwert in int zu konvertieren
    except ValueError:
        return str(cell)  # Falls es nicht möglich ist, gib den ursprünglichen Wert zurück

    if cell == 16:
        return '0'
    elif 10 <= cell <= 15:
        return chr(ord('A') + cell - 10)
    else:
        return str(cell)

def printGame(game):
    """Pretty-prints `game` with numbers 10-15 displayed as A-F."""
    n = len(game)
    rootN = int(n**0.5)
    maxDigits = 2  # A-F sind immer zweistellig im Kontext

    def leftPad(s):
        return s if len(s) == maxDigits else " " + s

    output = ""
    for i, row in enumerate(game):
        if i % rootN == 0 and i != 0:
            output += "\n"
        for j, cell in enumerate(row):
            if j % rootN == 0 and j != 0:
                output += "  "
            value = formatCell(cell)
            output += leftPad(value) + " "
        output += "\n"
    print(output)

def readGame(filename):
    """Reads the entire content of a Sudoku game file as a single string."""
    with open(filename, 'r') as file:
        content = file.read()
    return content

def saveGame(game, filename):
    """Saves the `game` to a file with `filename`."""
    n = len(game)
    rootN = int(n**0.5)
    maxDigits = 2

    def leftPad(s):
        return s if len(s) == maxDigits else " " + s

    with open(filename, 'w') as file:
        for i, row in enumerate(game):
            if i % rootN == 0 and i != 0:
                file.write("\n")
            for j, cell in enumerate(row):
                if j % rootN == 0 and j != 0:
                    file.write("  ")
                value = formatCell(cell)
                file.write(leftPad(value) + " ")
            file.write("\n")

def getRow (i, game):
    "Returns the i^th row in `game`.";
    return game[i];

def getCol (j, game):
    "Returns the j^th column in `game`.";
    return list(map(lambda row: row[j], game));

def getBoxStartPos (i, j, rootN):
    "Returns starting position of box containing (i, j).";
    iBox = math.floor(i / rootN) * rootN;
    jBox = math.floor(j / rootN) * rootN;
    return (iBox, jBox)

def getFlatBox (i, j, game):
    "Returns inner-box w.r.t (i, j), as a _flat_ list.";
    rootN = intSqrt(len(game));
    iBox, jBox = getBoxStartPos(i, j, rootN);
    flatBox = [];
    for ii in range(iBox, iBox + rootN):
        for jj in range (jBox, jBox + rootN):
            flatBox.append(game[ii][jj]);
    return flatBox;

def collectPossibleTrioLists (game):
    "Collects possibly deducible trios, (i, j, x), in `game`.";
    n, rootN = len(game), intSqrt(len(game));
    isFilled = True;                # Initial assumption
    cellwise = defaultdict(list);
    rowwise = defaultdict(list);
    colwise = defaultdict(list);
    boxwise = defaultdict(list);
    #
    @functools.lru_cache()
    def getRowSet (i): return set(getRow(i, game));
    #
    @functools.lru_cache()
    def getColSet (j): return set(getCol(j, game));
    #
    @functools.lru_cache()
    def getBoxSet (iBox, jBox):
        return set(getFlatBox(iBox, jBox, game));
    #
    iBox, jBox = (0, 0);
    for i in range(n):
        if i % rootN == 0:
            iBox = i;
        for j in range(n):
            if j % rootN == 0:
                jBox = j; 
            if game[i][j] == ".":
                isFilled = False;
                rowSet = getRowSet(i);
                colSet = getColSet(j);
                boxSet = getBoxSet(iBox, jBox);
                for x in range(1, n+1):
                    if x not in (rowSet | colSet | boxSet):
                        trio = (i, j, x);
                        cellwise[(i, j)].append(trio);
                        rowwise[(i, x)].append(trio);
                        colwise[(j, x)].append(trio);
                        boxwise[((iBox, jBox), x)].append(trio);
    possibleTrioLists = itertools.chain(
        cellwise.values(), rowwise.values(),
        colwise.values(), boxwise.values(),
    );
    return (possibleTrioLists, isFilled);

def deduce (game):
    "Tries to logically fill game using the rules of Sudoku.";
    putCount = 0;
    minTrioList = None;
    (iterTrioLists, isFilled) = collectPossibleTrioLists(game);
    for trioList in iterTrioLists:
        if len(trioList) == 1:
            (i, j, x) = trioList[0]; 
            if game[i][j] == ".":
                game[i][j] = x;
                putCount += 1;
        elif len(trioList) == 0:
            pass;
        elif (not minTrioList) or len(trioList) < len(minTrioList):
            minTrioList = trioList;
    # Finally ...
    if putCount:
        return deduce(game);
    # otherwise ...
    #printGame(game);
    return (isFilled, minTrioList);

def solveGame (inputGame, verbose=False, search="bfs"):
    "Solves `inputGame` using deductions and BFS/DFS.";
    search = search.lower();
    if search not in ["bfs", "dfs"]:
        raise ValueError(f"Unexpected param `search`: {search}");
    assert search in ["bfs", "dfs"];
    solutionList = [inputGame];         # Search-list (AKA Open-list)
    maxSolListLen = 1;
    while solutionList:
        game = solutionList.pop(0 if search == "bfs" else -1);
        (isFilled, minTrioList) = deduce(game);
        if isFilled and checkSolved(game):
            if verbose:
                print(f"Search list's maximum length: {maxSolListLen}");
            return game;
        elif minTrioList:
            for (i, j, x) in minTrioList:
                newGame = copy.deepcopy(game);
                newGame[i][j] = x;
                solutionList.append(newGame);
            if len(solutionList) > maxSolListLen:
                maxSolListLen = len(solutionList);
    # otherwise ...
    raise ValueError("Can't solve game.");

def checkSolved (game):
    n = len(game);
    rootN = intSqrt(n);
    fullSet = set(range(1, n+1));
    for k in range(0, n):
        rowAndColOk = (
            set(getRow(k, game)) == fullSet and
            set(getCol(k, game)) == fullSet #and
        );
        if not rowAndColOk:
            return False;
    for i in range(0, n, rootN):
        for j in range(0, n, rootN):
            if set(getFlatBox(i, j, game)) != fullSet:
                return False;
    return True;

def format_and_manipulate_string(input_str):
    symbols = input_str.split()
    length = len(symbols)
    
    for i, symbol in enumerate(symbols):
        if symbol in 'ABCDEF':
            symbols[i] = str(10 + ord(symbol) - ord('A'))
        elif symbol == '0':
            symbols[i] = '.' if length < 82 else '16'
        elif symbol in ('__', '_'):
            symbols[i] = '.'
    
    interval = 4 if length < 17 else 9 if length <= 81 else 16
    formatted_str = ''
    for i, symbol in enumerate(symbols, start=1):
        formatted_str += symbol + ' '
        if i % interval == 0:
            formatted_str += '\n'
    
    formatted_str = formatted_str.rstrip()
    if length % interval == 0:
        formatted_str += '\n'
    
    return formatted_str

def test(input_filename, output_filename):
    print("---------------------------------------------------------")
    try:
        gameText = readGame(input_filename)
        gameText = format_and_manipulate_string(gameText)
    except ValueError as e:
        print(f"Fehlerhafte Eingabe: {e}")
        return

    game = importGame(gameText)
    printGame(game)
    try:
        solvedGame = solveGame(game, verbose=True, search="bfs")
    except ValueError:
        pass
    else:
        assert checkSolved(solvedGame)
        printGame(solvedGame)
        saveGame(solvedGame, output_filename)
    print("---------------------------------------------------------")

def timer(fn):
    @functools.wraps(fn)
    def wrapper(*a, **ka):
        t0 = time.time()
        result = fn(*a, **ka)
        tDiff = time.time() - t0
        print(f"Time taken by {fn.__name__}(.): {tDiff}")
        return result
    return wrapper

if __name__ == "__main__":
    input_filename = sys.argv[1] if len(sys.argv) > 1 else "aufgabe.txt"
    output_filename = sys.argv[2] if len(sys.argv) > 2 else "loesung.txt"
    solveGame = timer(solveGame)
    test(input_filename, output_filename)



# End xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
mit folgenden Eingabedaten (aufgabe.txt)

Code: Alles auswählen

. 	. 	. 	. 	7	9	5	. 	. 	. 	. 	C	. 	. 	. 	. 
. 	B	. 	. 	. 	. 	. 	F	9	8	A	. 	. 	6	3	4
D	F	. 	. 	. 	. 	C	. 	B	E	. 	. 	A	8	. 	. 
. 	. 	. 	. 	. 	. 	A	B	. 	. 	F	. 	. 	. 	D	7
. 	7	. 	E	. 	D	. 	. 	6	. 	5	4	C	. 	9	A
A	. 	. 	. 	F	5	4	. 	. 	0	. 	3	D	. 	. 	. 
9	. 	F	4	. 	. 	. 	. 	. 	. 	2	. 	. 	B	. 	5
. 	. 	. 	. 	. 	. 	1	. 	. 	. 	. 	D	. 	F	7	8
8	. 	7	. 	. 	E	. 	. 	. 	. 	6	. 	. 	. 	. 	3
0	1	. 	. 	5	A	. 	8	. 	3	. 	E	. 	. 	C	. 
3	. 	9	A	B	. 	. 	. 	. 	7	D	. 	. 	. 	. 	. 
B	. 	2	. 	. 	. 	. 	. 	. 	C	. 	. 	. 	E	. 	. 
1	. 	. 	. 	9	. 	. 	. 	. 	. 	. 	0	F	. 	. 	D
. 	. 	8	. 	. 	. 	. 	. 	. 	2	. 	. 	. 	7	. 	E
. 	. 	A	. 	8	1	F	. 	D	. 	. 	. 	. 	. 	. 	. 
. 	5	. 	. 	3	. 	E	D	C	1	. 	9	. 	. 	. 	B
Nun habe ich mir eine meiner Lazarus-Programme geschnappt, da die (nur für 9x9 funktionierende Logik) ausgebaut und nur das Ein/Ausgabe-Gerüst gelassen. Sieht so aus:

Code: Alles auswählen

program SudokuSolver;

uses
  Classes, SysUtils, Math, Algebra;

const
  MAX = 16;

type
  TGrid = array[0..MAX-1, 0..MAX-1] of Integer;
  TTrio = record
    Row, Col, Value: Integer;
  end;

var
  SIZE: Integer;
  RootN: Integer;

function ReadGrid(const FileName: string): string;
var
  FileContent: TStringList;
begin
  FileContent := TStringList.Create;
  try
    FileContent.LoadFromFile(FileName);
    Result := FileContent.Text;
  finally
    FileContent.Free;
  end;
end;

function FormatAndManipulateString(const InputStr: string): string;
var
  Symbols: TStringList;
  Length, Interval, I: Integer;
  Symbol: string;
begin
  Symbols := TStringList.Create;
  try
    Symbols.Delimiter := ' ';
    Symbols.DelimitedText := StringReplace(InputStr, #9, ' ', [rfReplaceAll]);
    Length := Symbols.Count;

    for I := 0 to Symbols.Count - 1 do
    begin
      Symbol := Symbols[I];
      if (Symbol = '0') then begin
         if Length < 82 then
            Symbols[I] := '.'
         else
            Symbols[I] := '16';
      end
      else if (Symbol = '__') or (Symbol = '_') then
        Symbols[I] := '.'
      else if (Symbol[1] in ['A'..'F']) then
        Symbols[I] := IntToStr(10 + Ord(Symbol[1]) - Ord('A'));
    end;

    if Length < 17 then
      Interval := 4
    else if Length <= 81 then
      Interval := 9
    else
      Interval := 16;

    Result := '';
    for I := 0 to Symbols.Count - 1 do
    begin
      Result := Result + Symbols[I] + ' ';
      if ((I + 1) mod Interval = 0) then
        Result := Result + sLineBreak;
    end;

    Result := Trim(Result);
  finally
    Symbols.Free;
  end;
end;

procedure ImportGrid(const S: string; var Grid: TGrid);
var
  Lines, Words: TStringList;
  I, J: Integer;
begin
  Lines := TStringList.Create;
  Words := TStringList.Create;
  try
    Lines.Text := S;
    SIZE := Lines.Count;
    if SIZE > MAX then
      raise Exception.Create('Sudoku hat zu viele Zeilen');

    RootN := Trunc(Sqrt(SIZE));
    if RootN * RootN <> SIZE then
      raise Exception.Create('Sudoku ist kein perfektes Quadrat');
    for I := 0 to SIZE - 1 do
    begin
      Words.DelimitedText := Lines[I];
      if Words.Count <> SIZE then
        raise Exception.Create('Zeilenlänge inkonsistent');

      for J := 0 to SIZE - 1 do
      begin
        if Words[J] = '.' then
          Grid[I, J] := 0
        else
          Grid[I, J] := StrToInt(Words[J]);
      end;
    end;
  finally
    Lines.Free;
    Words.Free;
  end;
end;

procedure PrintGrid(const Game: TGrid);
var
  I, J: Integer;
  Cell: string;
begin
  for I := 0 to SIZE - 1 do
  begin
    if (I > 0) and (I mod RootN = 0) then
      WriteLn;

    for J := 0 to SIZE - 1 do
    begin
      if (J > 0) and (J mod RootN = 0) then
        Write('  ');

      if Game[I, J] = 0 then
        Cell := '.'
      else if (Game[I, J] >= 10) and (Game[I, J] <= 15) then
        Cell := Chr(Ord('A') + Game[I, J] - 10)
      else if Game[I, J] = 16 then
        Cell := '0'
      else
        Cell := IntToStr(Game[I, J]);

      Write(Cell:2, ' ');
    end;
    WriteLn;
  end;
end;

procedure SaveGrid(const FileName: string; const Game: TGrid);
var
  F: TextFile;
  I, J: Integer;
begin
  AssignFile(F, FileName);
  Rewrite(F);
  try
    for I := 0 to SIZE - 1 do
    begin
      for J := 0 to SIZE - 1 do
      begin
        if Game[I, J] = 0 then
          Write(F, '. ')
        else if Game[I, J] >= 10 then
          Write(F, Chr(Ord('A') + Game[I, J] - 10), ' ')
        else
          Write(F, Game[I, J], ' ');
      end;
      WriteLn(F);
    end;
  finally
    CloseFile(F);
  end;
end;

procedure GetRow(Row: Integer; var Grid: TGrid; var RowSet: BITSET);
var
  Col: Integer;
begin
  RowSet := [];
  for Col := 0 to SIZE - 1 do
    if Grid[Row, Col] <> 0 then
      bIncl(RowSet, Grid[Row, Col]);
end;

procedure GetCol(Col: Integer; var Grid: TGrid; var ColSet: BITSET);
var
  Row: Integer;
begin
  ColSet := [];
  for Row := 0 to SIZE - 1 do
    if Grid[Row, Col] <> 0 then
      bIncl(ColSet, Grid[Row, Col]);
end;

procedure GetBoxStartPos(Row, Col: Integer; var StartRow, StartCol: Integer);
begin
  StartRow := (Row div ROOTN) * ROOTN;
  StartCol := (Col div ROOTN) * ROOTN;
end;

procedure GetBox(Row, Col: Integer; var Grid: TGrid; var BoxSet: BITSET);
var
  StartRow, StartCol, i, j: Integer;
begin
  BoxSet := [];
  GetBoxStartPos(Row, Col, StartRow, StartCol);
  for i := StartRow to StartRow + ROOTN - 1 do
    for j := StartCol to StartCol + ROOTN - 1 do
      if Grid[i, j] <> 0 then
        bIncl(BoxSet, Grid[i, j]);
end;

function CheckSolved(var Grid: TGrid): Boolean;
var
  Row, Col, StartRow, StartCol: Integer;
  FullSet, RowSet, ColSet, BoxSet: BITSET;
begin
  CheckSolved := True;
  bInit(FullSet, 1, SIZE);

  for Row := 0 to SIZE - 1 do
  begin
    GetRow(Row, Grid, RowSet);
    if RowSet <> FullSet then
      Exit(False);
  end;

  for Col := 0 to SIZE - 1 do
  begin
    GetCol(Col, Grid, ColSet);
    if ColSet <> FullSet then
      Exit(False);
  end;

  for StartRow := 0 to SIZE - ROOTN do
    for StartCol := 0 to SIZE - ROOTN do
    begin
      GetBox(StartRow, StartCol, Grid, BoxSet);
      if BoxSet <> FullSet then
        Exit(False);
    end;
end;

function SolveSudoku(var Grid: TGrid): Boolean;
begin
  SolveSudoku := False;
end;

var
  InputFile, OutputFile, GridText: string;
  Grid: TGrid;
begin
  try
    InputFile := 'aufgabe.txt';
    OutputFile := 'koesung.txt';

    GridText := ReadGrid(InputFile);
    GridText := FormatAndManipulateString(GridText);
    ImportGrid(GridText, Grid);

    WriteLn('Originales Sudoku:');
    PrintGrid(Grid);

    if SolveSudoku(Grid) then
    begin
      WriteLn('Gelöstes Sudoku:');
      PrintGrid(Grid);
      SaveGrid(OutputFile, Grid);
      WriteLn('Lösung wurde in "', OutputFile, '" gespeichert.');
    end
    else
      WriteLn('Das Sudoku konnte nicht gelöst werden.');
    readln;

  except
    on E: Exception do
      WriteLn('Fehler: ', E.Message);
  end;
end.

Und wollte nun "nur noch" die 3 Methoden Decuce, SolveSudoku und CollectPossibleTrio einfügen also ins Lazarus-Programm. Aber ich begreif's einfach nicht :-( Meine Unit Algebra mit dem Bitset sollte funktionieren, da schon "alt". Die Umsetzung der CheckSolved nach Lazarus ist mir denke mal auch gelungen aber diese 3 Methoden überfordern anscheinend mein Python-Wissen und (durch die vielen Fehlversuche) auch zunehmend meine Motivation und Wissen in Lazarus, obwohl ich das noch am besten könnte. Kann mir bitte jemand auf die Sprünge helfen?
Benutzeravatar
__blackjack__
User
Beiträge: 13808
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@alfware17: Irgendwie vermisse ich hier den Python-Bezug. Der erste Quelltext ist ja alles mögliche, nur kein tatsächliches Python. Über 90 unsinnige Semikolons, Namen die sich nicht an die Konventionen halten, unpythonischer Code, fast der gleiche Code bei der Ausgabe mit `print()` und beim Speichern in eine Datei, kleinteiliger Code um Hexadezimaldarstellungen von Zahlen in beide Richtungen zu wandeln, eine Funktion um eine Zahl die in Hexadezimaldarstellung umgewandelt mit (einem) Leerzeichen auf zwei Zeichen aufzufüllen wenn sie kürzer ist, … das ist alles nichts was man so als Python-Programmierer schreiben würde.
Die drei Todfeinde des Programmieres:
Sonnenlicht, frische Luft und das unerträgliche Gebrüll der Vögel.
alfware17
User
Beiträge: 51
Registriert: Montag 9. September 2024, 17:53

Ich kann @blackjack die Kritik vom Hohen Roß ja nicht einmal verübeln, da auch ich den Code nicht gut gelungen finde. Vergiß aber bitte nicht, ich bin Anfänger und bei so einem Kuddelmuddel von einem anscheinend Fach-Profi, der aber auf Sorgfalt keinen Wert gelegt hat und dann mindestens noch 2 weiteren Autoren, die es ver(schlimm)bessert haben, ziemlich hilflos. Zudem will ich für das Python-Programm ja auch keinen Schönheitswettbewerb gewinnen, sondern nur den Lösungsalgorithmus verstehen und dann nach Lazarus umbauen. Da sehe ich ziemliche Hürden, weil mit Dictionaries und Listen und Sets und kombiniert ziemlich jogliert wird und ich selbst einfachste Dinge wie 2 return-Werte umsetzen muß in call by reference Parameter, ich müßte es auch bei nur 1 return schon, weil Pascal als Funktionsergebnisse kaum komplexe Typen erlaubt. Ich will also einfach nur rausfinden, was da abgeht und ob man es nicht viel einfacher und viel flacher machen kann, auch wenn es dann nicht so schick Python aussieht.
Ich gebe zu, die Eingabe/Ausgabe/Anzeige ist komisch - es ist dem ursprünglichen Quelltext geschuldet, der beim "Import" eben einen langen String erwartet. Was ich einerseits gut finde, wenn der Lösungsalgorithmus das dann kann - andererseits habe ich es eben ein bißchen umständlich, wenn ich Textdatei lese/schreibe und auch noch die Fälle vorsehen will, daß beispielweise entweder 12 oder C drin stehen kann, das Leerzeichen Space oder Tab und das leere Feld entweder 0 oder . sein darf, d.h. die 0 nur beim 9x9. Meine von verschiedenen Webseiten kopierten Sudoku-Aufgaben hatten nach copy+paste eben dieses Format.

Könnte mir bitte zB jemand helfen, wie ich beim collectPossibleTrioLists ohne die Dictionaries auskomme? Am liebsten würde ich so eine Liste (i, j, x) als record ausdrücken und mit SETs kann ich umgehen, das heißt bei mir Bitset.
Benutzeravatar
__blackjack__
User
Beiträge: 13808
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@alfware17: Das Problem ist halt wenn das dermassen nicht nach Python aussieht, dann ist das schwer zu lesen. Es geht nicht darum einen “Schönheitswettbewerb“ zu gewinnen, sondern das der Code nicht unnötig schwer zu lesen und umständlich formuliert ist.

Wenn man Wörterbücher braucht, programmiert man die sich halt in der anderen Programmiersprache. Hashmaps sind ja keine dunkle Magie.
Die drei Todfeinde des Programmieres:
Sonnenlicht, frische Luft und das unerträgliche Gebrüll der Vögel.
alfware17
User
Beiträge: 51
Registriert: Montag 9. September 2024, 17:53

@blackjack: also wenn dich das Thema nicht interessiert, kannst du es doch ignorieren. Aber einfach nur sagen "das ist kein Python" ist wenig konstruktiv.
Ihr habt mir hier bisher schon bei 2-3 Themen geholfen, richtig gut sogar, daher vermutete ich eben, jemand kann den fremden Python Code (der Kern sind die 3 Methoden die jetzt noch offen sind),
besser lesen und den Algorithmus dahinter verstehen.
Mein Zielsystem (Lazarus bzw Turbo-Pascal) kann eben vieles nicht, was in Python mit ein paar Zaubertricks zwar elegant aussieht aber eben nicht offensichtlich ist.

Daß ich, um das zum Angucken zu kriegen, die Ein/Ausgabe anpassen muß und dabei nicht 100% sorgsam bin,
weil ich ja eh ein Lazarus Programm haben will und da die Ein/Ausgabe schon geht
(eine andere, nicht die über den langen String wie hier)
und ich am liebesten erst bei meiner Datenstruktur anfangen will, die ein 2d-array von int ist. habe ich wohl nicht so deutlich gesagt.

Mittlerweile behelfe ich mir damit die Python Zeilen schrittweise alle durchzugehen und mit print zu schauen, was ist in den Variablen drin.
Viele Listen, Dictionary. später noch ein Stack, die muß ich mir alle bauen bzw anpassen (Grid-Stack habe ich gerade heute gemacht).

Wenn ich nun aber wüßte, der Zauber angefangen von den Sets (ok habe ich auch fertig) über die Dictionaries mit den 3-teiligen Keys
und das dann wieder verketten, kürzen usw. muß eigentlich gar nicht sein sondern sieht nur in Python schick und einfach aus....
dann kann ich mir doch die ganzen neuen Tools sparen und mit einfacheren Daten arbeiten.

Ich habe zB herausgefunden ( i , j ) bzw ( ( i , j ), x ) ist wahrscheinlich Luxus und ich kann einfach einen Record mit drei Zahlen als Key nehmen und das x im Zweifel 0 lassen.
Es kommt ja nur darauf an, daß die Trio ( i , j , x ) sich nicht gegenseitig stören/aufheben und irgendwann mal im Deduce wieder 3 Variablen werden.

Alleine schon so ein ( x , y ) = aufruf ( a , b ) mag in Python schick aussehen ( x , y ) mit und ohne () -
stört aber nur das Denken, wenn man als Ziel eigentlich ein flaches aufruf ( var x; var y; a; b ) im Turbo-Pascal braucht und so wie ich trotzdem erstmal mit Kanonen auf Spatzen schießt
und überall Bitsets einbaut und dann feststellt, halt Python hat ganz andere Daten an den Schnittstellen übergeben.

Und dann kommen noch solche "Effekte" wie das itertools.chain, wo das wenn ich es vor der Auswerteschleife erstmal print mache zum Angucken, dann sofort weg ist - da schimpfe ich nach 3 Stunden Suchen
über Python und daß man es nicht lesen kann, selbst wenn es da steht aber es ist eine Trickserei genauso wie das mit dem Cache. (beim chain hat geholfen, ein list ( ) drum herum zu machen, dann war es nicht mehr flüchtig
Benutzeravatar
sparrow
User
Beiträge: 4452
Registriert: Freitag 17. April 2009, 10:28

Das ist lustig.
Du beschwert dich ausufernd darüber, dass der Quelltext schwer zu lesen ist und wenn dir jemand sagt, dass das der schlecht zu lesen ist, weil völlig unpythomisch ist, ist dir das auch nicht recht.

Aber so ist es nun einmal. Und so muss man halt vorgehen, wenn man unbekannten Code in einer unbekannten Sprache verstehen oder portieren will. Und wenn Python aussehen würde wie TurboPascal, dann wäre es wohl TurboPascal. Auch wenn es Menschen gibt, die denken Python ist Java.
Und da der Quelltext aus den vok __blackjack__ genannten Gründen auch nicht aussieht wie Python, muss das auf jeder erfahrene Python Programmierer tun.
alfware17
User
Beiträge: 51
Registriert: Montag 9. September 2024, 17:53

Ich habe mich nur "beschwert", daß der User und nun auch du nur meckern können, es wäre kein Python oder entspräche nicht eurem Schönheitsideal - konstruktive Hilfe ist jedoch nicht zu erwarten. Warum ignorierst du es denn nicht einfach. Ich habe keine Ahnung, ob der Verfasser meines Ursprungscodes erfahren war oder nicht. Mehr und mehr verhärtet sich bei mir jedoch der Eindruck, daß ihm Tricks und Geschwindigkeit wichtiger waren als Verstehen. Ich muß es nun aber mal verstehen und möchte es nachvollziehen und mache mir die Mühe, hinter die Klippen und ich sage jetzt mal Eitelkeiten von Python zu steigen. Wie du an meinen Beispielen siehst - da ist neben der von dir Stümperei genannten Erweiterung von einer 2 oder 3.Person im Kern auch vieles was eben in Python einfach so geschrieben werden kann weil es geht und weil es schick aussieht oder was weiß ich. Ich wollte jedoch nicht den Elfenbeinturm nachbauen sondern nur das Problem lösen und daher wissen, was dahinter steckt und ob es nicht viel einfacher auszudrücken geht.
Sirius3
User
Beiträge: 18135
Registriert: Sonntag 21. Oktober 2012, 17:20

@alfware17: um einen Algorithmus verstehen zu können, muß er erst einmal in der jeweiligen Programmiersprache verständlich geschrieben sein. Und sobald man verstanden hat, was da passiert, kann man das dann auch in eine andere Programmiersprache übertragen.
Zum Verständnis gehört erst einmal, dass fundamentale Konventionen eingehalten werden. Also einigermaßen verständliche Variablennamen. Dann sollte man die Mächtigkeit, die eine Sprache bietet auch nutzen, weil es zu kürzerem, verständlicherem Code führt.
Doppelter Code muß eliminiert werden, was wiederum zu verständlicherem Code führt.
Also kommt man schließlich ungefähr hier raus:

Code: Alles auswählen

import math
from collections import defaultdict
import itertools
import copy
import sys


def import_game(lines):
    "Reads a string-represented game as a list of rows."
    rows = []
    for line in lines:
        if line.strip():
            row = []
            for word in line.split():
                if word.isdigit():
                    row.append(int(word))
                elif word in "ABCDEF":
                    row.append(int(word, 16))
                elif word in ["." * len(word), "_" * len(word)]:
                    row.append(None)
                else:
                    raise ValueError(f"Unexpected word: {word}")
            rows.append(row)
    size = len(rows)
    if size == 9:
        # convert 0 to empty
        rows = [[None if cell == 0 else cell for cell in row] for row in rows]
    if any(len(row) != size for row in rows):
        raise ValueError("Game-grid isn't a perfect square.")
    if math.isqrt(size) ** 2 != size:
        raise ValueError(f"Expected a perfect square, not: {size}")
    return rows


def game_to_string(game):
    """Pretty-prints `game` with numbers 10-15 displayed as A-F."""
    size_of_area = math.isqrt(len(game))

    output_rows = []
    for i, row in enumerate(game):
        if i % size_of_area == 0:
            output_rows.append("")
        output_row = []
        for j, cell in enumerate(row):
            if j % size_of_area == 0:
                output_row.append("")
            output_row.append(f"{cell % 16:2x}" if cell is not None else " .")
        output_rows.append("  ".join(output_row[1:]))
    return "\n".join(output_rows[1:])


def iter_rows(game):
    yield from game


def iter_columns(game):
    yield from zip(*game)


def iter_areas(game):
    size_of_area = math.isqrt(len(game))
    areas = []
    for row in game:
        areas.append(
            [
                row[i : i + size_of_area]
                for i in range(0, len(row), size_of_area)
            ]
        )
        if len(areas) == math.isqrt(len(game)):
            for row in zip(*areas):
                yield list(itertools.chain.from_iterable(row))
            areas = []

def check_solved(game):
    all_digits = set(range(1, len(game) + 1))
    for iter_cells in [iter_rows, iter_columns, iter_areas]:
        if any(set(cells) != all_digits for cells in iter_cells(game)):
            return False
    return True

def collect_possible_values(game):
    "Collects possibly deducible trios, (i, j, x), in `game`."
    size_of_area = math.isqrt(len(game))

    cellwise = defaultdict(list)
    rowwise = defaultdict(list)
    colwise = defaultdict(list)
    boxwise = defaultdict(list)

    areas = list(iter_areas(game))
    for row_index, row in enumerate(iter_rows(game)):
        row_digits = set(range(1, len(game) + 1))
        row_digits.difference_update(row)
        if row_digits:
            for column_index, column in enumerate(iter_columns(game)):
                column_digits = row_digits.difference(column)
                if column_digits:
                    area_index = (row_index // size_of_area) * size_of_area + (column_index // size_of_area)
                    digits = column_digits.difference(areas[area_index])
                    if game[row_index][column_index] is None:
                        for digit in digits:
                            trio = (row_index, column_index, digit)
                            cellwise[row_index, column_index].append(trio)
                            rowwise[row_index, digit].append(trio)
                            colwise[column_index, digit].append(trio)
                            boxwise[area_index, digit].append(trio)
    return itertools.chain(
        cellwise.values(), rowwise.values(),
        colwise.values(), boxwise.values(),
    )


def deduce(game):
    "Tries to logically fill game using the rules of Sudoku."
    while True:
        game_updated = False
        minimal_trios = None
        game_trios = collect_possible_values(game)
        for trios in game_trios:
            if not trios:
                pass
            elif len(trios) == 1:
                row_index, column_index, digit = trios[0]
                game[row_index][column_index] = digit
                game_updated = True
            elif not minimal_trios or len(trios) < len(minimal_trios):
                minimal_trios = trios
        if not minimal_trios or not game_updated:
            break
    return minimal_trios


def solve_game(input_game, search="bfs"):
    "Solves `input_game` using deductions and BFS/DFS."
    if search not in ["bfs", "dfs"]:
        raise ValueError(f"Unexpected param `search`: {search}")

    solution_stack = [input_game]
    max_solution_stack_length = 1
    while solution_stack:
        game = solution_stack.pop(0 if search == "bfs" else -1)
        minimal_trios = deduce(game)
        if not minimal_trios:
            if check_solved(game):
                print(f"Search list's maximum length: {max_solution_stack_length}")
                return game
            # else: no solution, try next one
        else:
            for row_index, column_index, digit in minimal_trios:
                new_game = copy.deepcopy(game)
                new_game[row_index][column_index] = digit
                solution_stack.append(new_game)
            max_solution_stack_length = max(max_solution_stack_length, len(solution_stack))
    raise ValueError("Can't solve game.")


def test(input_filename, output_filename):
    with open(input_filename) as lines:
        game = import_game(lines)
    print(game_to_string(game))
    solved_game = solve_game(game, search="bfs")
    assert check_solved(solved_game)
    print(game_to_string(game))
    with open(output_filename) as file:
        file.write(game_to_string(game))


def main():
    input_filename = sys.argv[1] if len(sys.argv) > 1 else "aufgabe.txt"
    output_filename = sys.argv[2] if len(sys.argv) > 2 else "loesung.txt"
    test(input_filename, output_filename)


if __name__ == "__main__":
    main()
alfware17
User
Beiträge: 51
Registriert: Montag 9. September 2024, 17:53

Hallo Sirius3, danke für deine Verbesserungen. Bei open(output_filename) habe ich ein "w" ergänzt.
Im Prinzip läuft es (und sieht viel besser aus :-)
Aber....
Es wird für die o.a. Testdaten keine Lösung gefunden (dann wird die Meldung gezogen).
Und wenn ich mal testweise ein 9x9 Sudoku aufgebe,

Code: Alles auswählen

1	5	0	0	0	0	0	0	0 	 	 	 	 	 	 
2	3	0	0	0	0 	7	0	0 	 
0 	8	0	0	0	0	0 	9	0 
0	0	0	0	0	0	0	0	8
0 	7	0	0 	8	0	0 	4	2
4	1	0	0 	3	0	0	0	0		 	 	 	 
0	0	0 	2	7	0	6	0 	0	 
0	0	0 	9	0 	5	0 	1	0 
0	0	0	0	4	0 	8	7	0
dann schreibt er zwar, aber es blieben 4 Felder auf . stehen. Sicher nur ein Flüchtigkeitsfehler?
Sirius3
User
Beiträge: 18135
Registriert: Sonntag 21. Oktober 2012, 17:20

Ja, es könnten Flüchtigkeitsfehler sein, Dein Beispiel funktioniert aber fehlerlos, bis auf den Umstand, dass es keine eindeutige Lösung gibt.
alfware17
User
Beiträge: 51
Registriert: Montag 9. September 2024, 17:53

Es gibt aber eine Lösung

Code: Alles auswählen

 1  5  4    8  9  7    3  2  6 
 2  3  9    4  5  6    7  8  1 
 7  8  6    1  2  3    4  9  5 

 9  6  2    7  1  4    5  3  8 
 5  7  3    6  8  9    1  4  2 
 4  1  8    5  3  2    9  6  7 

 3  9  1    2  7  8    6  5  4 
 8  4  7    9  6  5    2  1  3 
 6  2  5    3  4  1    8  7  9 
Der ursprüngliche Code, der nicht Python ist (s.o.) findet die aber (deshalb will den Algorithmus ja haben).

und meine 16x16 Aufgabe (auch oben) löst es auch.

Code: Alles auswählen

 
 6  A  3  8    7  9  5  4    2  D  1  C    E  0  B  F 
 7  B  C  2    E  0  D  F    9  8  A  5    1  6  3  4 
 D  F  4  1    6  3  C  2    B  E  0  7    A  8  5  9 
 E  0  5  9    1  8  A  B    3  4  F  6    2  C  D  7 

 2  7  B  E    0  D  8  3    6  F  5  4    C  1  9  A 
 A  8  1  C    F  5  4  9    7  0  B  3    D  2  E  6 
 9  D  F  4    C  7  6  E    8  A  2  1    3  B  0  5 
 5  6  0  3    2  B  1  A    E  9  C  D    4  F  7  8 

 8  C  7  F    4  E  9  1    0  B  6  2    5  D  A  3 
 0  1  D  6    5  A  7  8    F  3  4  E    B  9  C  2 
 3  E  9  A    B  2  0  C    5  7  D  8    6  4  F  1 
 B  4  2  5    D  F  3  6    1  C  9  A    7  E  8  0 

 1  3  E  B    9  C  2  7    A  6  8  0    F  5  4  D 
 C  9  8  D    A  6  B  5    4  2  3  F    0  7  1  E 
 4  2  A  7    8  1  F  0    D  5  E  B    9  3  6  C 
 F  5  6  0    3  4  E  D    C  1  7  9    8  A  2  B 
alfware17
User
Beiträge: 51
Registriert: Montag 9. September 2024, 17:53

Sirius3 hat geschrieben: Mittwoch 22. Januar 2025, 08:00 Ja, es könnten Flüchtigkeitsfehler sein, Dein Beispiel funktioniert aber fehlerlos, bis auf den Umstand, dass es keine eindeutige Lösung gibt.
mit deinem Programm bleiben bei mir 4 Punkte
Sirius3
User
Beiträge: 18135
Registriert: Sonntag 21. Oktober 2012, 17:20

Nein, es gibt zwei Lösungen:

Code: Alles auswählen

 1  5  4    8  9  7    3  2  6 
 2  3  9    4  5  6    7  8  1 
 7  8  6    1  2  3    4  9  5 

 9  6  2    7  1  4    5  3  8 
 5  7  3    6  8  9    1  4  2 
 4  1  8    5  3  2    9  6  7 

 3  9  1    2  7  8    6  5  4 
 8  4  7    9  6  5    2  1  3 
 6  2  5    3  4  1    8  7  9 
und

Code: Alles auswählen

 1  5  4    8  9  7    3  2  6 
 2  3  9    4  5  6    7  8  1 
 7  8  6    3  2  1    4  9  5 

 9  6  2    7  1  4    5  3  8 
 5  7  3    6  8  9    1  4  2 
 4  1  8    5  3  2    9  6  7 

 3  9  1    2  7  8    6  5  4 
 8  4  7    9  6  5    2  1  3 
 6  2  5    1  4  3    8  7  9 
was das Beispiel nicht zu einem regulären Sudoku macht.
Beim 16x16-Bespiel ist einfach noch nicht der Sonderfall 0 beim Einlesen implementiert.
alfware17
User
Beiträge: 51
Registriert: Montag 9. September 2024, 17:53

Ja gut, aber haben nicht viele Sudokus mehrere Lösungen? Mir ging es darum, daß nicht wenigstens eine davon angezeigt. Am Monitor wie auch in der Datei bleiben die Felder, wo oben die 1 und die 3 nicht eindeutig sind, einfach frei (auf Punkt).

Beim 16x16 habe ich die 0 (in der Eingabe) auf 16 umgesetzt. Bei der Ausgabe daher dann wieder 16 -> 0. Es war der Kompromiss, da viele Webseiten 0..F benutzen, manche habe ich auch schon mit 1..16 also zweistellig gesehen. Daher auch die vielleicht kritisierte umständliche (aber extra gemachte) Auswertung von 0 und Punkt abhängig von der Boardgröße.

Ebenso bei 25x25 (ich hatte mal hohe Pläne), wo ich von 1..25 über 1..N bis A..Y auch alles gesehen habe. Zweistellige Symbole fand ich doof, wobei mein Lazarus-Programm die auch schon kann.
Hier (Code ganz oben) bin ich mir nicht mehr sicher, auch nicht was der Original-Code (ohne Datei, beginnend mit ImportGame) gemacht hatte. Die weiteren Kompromisse (Leerzeichen, Tabs, 0 und . zulassen) kommen alle daher, daß ich die meisten meiner Vorlagen per copy+paste eben von diesen Webseiten holte. Nur wenn für "leer" gar nichts also Space steht, da habe ich keine flexible Lösung.
Benutzeravatar
noisefloor
User
Beiträge: 4035
Registriert: Mittwoch 17. Oktober 2007, 21:40
Wohnort: WW
Kontaktdaten:

Hallo,

nee, Sudokus sollen eindeutig sein, d.h. jedes Sudoku hat genau eine Lösung. So sagen es zumindest einschlägige Quellen im Internet, wie z.B. https://de.wikipedia.org/wiki/Sudoku

In dem Artikel werden übrigens auch jede Menge Ansätze für das systematische Lösung und Algorithmen erklärt. Falls du mal einen anderen Algorithmus probieren willst. Oder man geht das mal mit Logiksprachen wie Prolog an.

Gruß, noisefloor
alfware17
User
Beiträge: 51
Registriert: Montag 9. September 2024, 17:53

Ich weiß jetzt nicht, was genau du mir mit der "Eindeutigkeit" sagen willst. Es geht doch auf Webseiten, in Rätselheften usw auch darum, EINE Lösung zu finden - ich schmeiße doch das Heft nicht weg, wenn ich nach der ersten Lösung merke, oh da hätte ich aber noch mal wechselseitig was tauschen können. Ich weiß es gibt den Wettbewerb Finde alle Lösungen zu einem Sudoku usw. Wenn ich aber mir eines aus einer Liste oder einer Datei hole, will ich es lösen und wieder wegschreiben.
Mein kleines 9x9 Beispiel löst der Ursprungscode, bei Sirus3 blieben 4 Punkte offen. Kein Vorwurf. kein Problem. Nur eben, irgendwo hat der Algorithmus eben einen Flüchtigkeitsfehler erlitten bei der Schönheitskur.
Letztere hat mir übrigens sehr geholfen - ich habe das Programm neu strukturiert und auf potentiell 25x25 erweitert. Die 3 Methoden, die mir fehlten, habe ich nun analysiert und alle Datentypen, die ich brauche, um es in Lazarus auszudrücken, Im Verein bzw eher Streit mit ChatGPT habe ich das mit den TrioListen und auch das Verdichten und das BFS bzw DFS begriffen. Ich habe alle Units in Turbo Pascal, die ich brauche um das nachzubauen.
Und nebenbei habe ich unterschiedliche Schwierigkeitsgrade von Sudokus gesehen. Während das hier im Thread gezeigte 16x16 beinahe schon durch das deduce erledigt wird
(und meine Backtracking Versuche von 2024 trotzdem kläglich scheiterten), habe ich im Testfundus des Erstellers meines Ursprungsprogramms auch eins gefunden, welches schon mal eine 4-stellige Rekursionstiefe erreicht und trotzdem im Sekundenbereich fertig wird. Na gut, in Pascal werde ich sehen, aber wenigstens weiß ich jetzt wozu die Solution-Deque da ist und wie ich sie nachbaue.
Sirius3
User
Beiträge: 18135
Registriert: Sonntag 21. Oktober 2012, 17:20

Ein richtiges Sudoku muß man nicht mit Raten und Ausprobieren lösen, sondern es gibt immer einen Logischen Lösungspfad. Ein Deinem 9x9-Beispiel beleibt man also bei den 4 leeren Feldern stehen und kommt nicht weiter.
Was aber mein Code nicht tut, weil der ja alle Möglichkeiten ausprobiert. Warum das bei Dir nicht tut? Ich weiß ja nicht, was Du wirklich ausführst.
Benutzeravatar
noisefloor
User
Beiträge: 4035
Registriert: Mittwoch 17. Oktober 2007, 21:40
Wohnort: WW
Kontaktdaten:

Grundsätzlich sollte jedes sauber designete Sudoku _genau_ein_ Lösung habe. Und nicht mehr.

Man kann bestimmt auch Sudoku generieren, die mehr als eine Lösung haben. Das sind dann aber keine Sudokus, die man als "klassische Sudokus" bezeichnet.
Ein Deinem 9x9-Beispiel beleibt man also bei den 4 leeren Feldern stehen und kommt nicht weiter.
Dann ist das Sudoku unterbestimmt, d.h. es fehlt (mindestens) ein Hinweis (=eine vorgegeben Zahl), um das Soduko eindeutig zu lösen.

Gruß, noisefloor
alfware17
User
Beiträge: 51
Registriert: Montag 9. September 2024, 17:53

Ihr könnt mir gerne was in Python erzählen und erklären, was ich meistens sehr dankbar annehme.

Aber die Aussage, ein Programm sollte, wenn das Sudoku nicht eindeutig gelöst werden kann, sich nicht wenigstens für EINE der Lösungen entscheiden und die auch anzeigen, sondern statt dessen einfach mit 4 ungelösten Feldern stehen bleiben - halte ich für sehr weltfremd, akademisch oder einfach falsch, sorry. Zumal ja auch kein Hinweis kam, daß das Sudoku nicht gelöst wurde (im 9x9 Beispiel) bzw das Programm einfach abbrach, obwohl eine Lösung existiert (im 16x16 Beispiel).

Noch mal, kein Vorwurf an Sirius3 - aber mein Ausgangs-Code hat beide Beispiele gelöst und ich hatte nur vermutet, daß da bei der Übertragung ein Flüchtigkeitsfehler eingeschlichen war. Und ja, ich habe deinen Code noch einmal kopiert und probiert (ich sah es daran, daß ich bei open das "w" erneut ergänzen mußte, es lief bei mir wirklich dieser Code und der hatte eben 4 Felder auf Punkt gelassen. Ich habe auch einen "Verdacht" es könnte das yield sein

Egal, ich lasse meinen Python-Code jetzt so:

Code: Alles auswählen

import time
import functools
import math
from collections import defaultdict
import itertools

SIZE = 0
rootN = 0
LEER = 255

def char2num(SIZE, char):
    if not (SIZE in (9,16,25)):
        return 'XXX'
    if char in '123456789' and len(char)==1:
        return char
    if char in ('.', '_', '__'):
        return '.'
    if char == '0':
      return '16' if SIZE == 16 else '.'
    if SIZE == 16:
        if '10' <= char <= '16' and len(char)==2:
            return char
        elif 'A' <= char <= 'F':
            return str(10 + ord(char) - ord('A'))
    if SIZE == 25:
        if '10' <= char <= '25' and len(char)==2:
            return char
        elif 'A' <= char <= 'Y':
            return str(1 + ord(char) - ord('A'))
    return 'XXX'

def num2char(SIZE, num):
    if not (SIZE in (9,16,25)):
        return 'XXX'
    if num in (LEER, 0):
        return '.'
    if 1 <= num <= 9 and SIZE in (9,16):
        return chr(num  + ord('0'))
    if SIZE == 16:
        if 10 <= num <= 15:
            return chr(num - 10  + ord('A'))
        elif num == 16:
            return '0'
    if SIZE == 25:
        if 1 <= num <= 25:
            return chr(num - 1  + ord('A'))
    return 'XXX'

def formatInput(input):
    global SIZE, rootN
    symbols = input.split()
    length = len(symbols)
    SIZE = int(math.sqrt(length))
    rootN = int(math.sqrt(SIZE))
    formatted = ''
    for i, symbol in enumerate(symbols, start=1):
        ergebnis = char2num(SIZE, symbol)
        if ergebnis == 'XXX':
            raise ValueError("ungültiges Symbol: "+symbol)
        formatted += ergebnis + ' '
        if i % SIZE == 0:
            formatted += '\n'
    return formatted.rstrip() + '\n'

def importGame(s):
    global SIZE, rootN
    rows = []
    for line in s.splitlines():
        if line.strip():
            rows.append([])
            for word in line.split():
                if word.isdigit():
                    rows[-1].append(int(word))
                    if word == "0":
                        raise ValueError("Unerwartete 0 gefunden")
                elif word == "." * len(word):
                    rows[-1].append(LEER)
                else:
                    raise ValueError(f"Unerwartetes Wort: {word}")
    SIZE = len(rows)
    rootN = int(math.sqrt(SIZE))
    for i in range(SIZE):
        if len(rows[i]) != SIZE:
            raise ValueError("Das Spielfeld ist kein perfektes Quadrat.")
    return rows

def readGame(filename):
    with open(filename, 'r') as file:
        content = file.read()
    return content

def formatGame(game):
    def leftPad(s):
        return s if len(s) == 2 else " " + s
    output = []
    for i, row in enumerate(game):
        if i % rootN == 0 and i != 0:
            output.append("")
        formatted_row = []
        for j, cell in enumerate(row):
            if j % rootN == 0 and j != 0:
                formatted_row.append("  ")
            ergebnis = num2char(SIZE, cell)
            if ergebnis == 'XXX':
                raise ValueError(f"falscher Wert: {cell}")
            formatted_row.append(leftPad(ergebnis))
        output.append(" ".join(formatted_row))
    return "\n".join(output)

def printGame(game):
    print(formatGame(game))
    print("Felder gefüllt:", countFilled(game))

def saveGame(game, filename):
    with open(filename, 'w') as file:
        file.write(formatGame(game) + "\n")

def getRow(i, game):
    return game[i]

def getRowSet(i, game):
    return set(getRow(i, game))

def getCol(j, game):
    return list(zip(*game))[j]

def getColSet(j, game):
    return set(getCol(j, game))

def getBox(i, j, game):
    iBox = math.floor(i / rootN) * rootN
    jBox = math.floor(j / rootN) * rootN
    return [game[row][col] 
                for row in range(iBox, iBox + rootN) 
                    for col in range(jBox, jBox + rootN)]

def getBoxSet(i, j, game):
    return set(getBox(i, j, game))

def isSetValid(symbol_set):
    seen = set()
    for symbol in symbol_set:
        if symbol != LEER:
            if symbol in seen or symbol > SIZE:
                return False, symbol
            seen.add(symbol)
    return True, None

def isValid(game, row=None, col=None):
    def checkAndReport(checks):
        for name, values, index in checks:
            valid, symbol = isSetValid(values)
            if not valid:
                return False, f"{name} {index} enthält ein ungültiges Symbol: {symbol}"
        return True, None

    if row is not None and col is not None:
        value = game[row][col]
        if value == LEER:
            return True, None
        checks = [("Zeile", getRow(row, game), row),
                  ("Spalte", getCol(col, game), col),
                  ("Block", getBox(row, col, game), (row, col))]
        return checkAndReport(checks)
    else:
        checks = [("Zeile", getRow(i, game), i) for i in range(SIZE)] + [
                 ("Spalte", getCol(i, game), i) for i in range(SIZE)] + [
                 ("Block", getBox(i, j, game), (i, j))
                 for i in range(0, SIZE, rootN)
                 for j in range(0, SIZE, rootN)]
        return checkAndReport(checks)

def countFilled(game):
    count = 0
    for row in game:
        for value in row:
            if value != LEER:
                count += 1
    return count

def isFilled(game):
    return countFilled(game) == SIZE*SIZE

def isSolved(game):
    fullSet = set(range(1, SIZE+1))
    for k in range(SIZE):
        if not (getRowSet(k, game) == fullSet and
                getColSet(k, game) == fullSet):
            return False
    for i in range(0, SIZE, rootN):
        for j in range(0, SIZE, rootN):
            if getBoxSet(i, j, game) != fullSet:
                return False
    return True

def collectPossibleTrioLists(game):
    cellwise = defaultdict(list)
    rowwise = defaultdict(list)
    colwise = defaultdict(list)
    boxwise = defaultdict(list)
    iBox, jBox = (0, 0)
    for i in range(SIZE):
        if i % rootN == 0:
            iBox = i
        for j in range(SIZE):
            if j % rootN == 0:
                jBox = j
            if game[i][j] == LEER:
                rowSet = getRowSet(i, game)
                colSet = getColSet(j, game)
                boxSet = getBoxSet(iBox, jBox, game)
                mergeSet = (rowSet | colSet | boxSet)
                for x in range(1, SIZE+1):
                    if x not in mergeSet:
                        trio = (i, j, x)
                        cellwise[(i, j)].append(trio)
                        rowwise[(i, x)].append(trio)
                        colwise[(j, x)].append(trio)
                        boxwise[((iBox, jBox), x)].append(trio)
    possibleTrioLists = itertools.chain(
        cellwise.values(), rowwise.values(),
        colwise.values(), boxwise.values(),
    )
    return possibleTrioLists

def deduce(game):
    minTrioList = None
    possibleTrioLists = collectPossibleTrioLists(game)
    while True:
        updated = False
        for trioList in possibleTrioLists:
            if len(trioList) == 1:  
                (i, j, x) = trioList[0]
                if game[i][j] == LEER:
                    game[i][j] = x
                    updated = True
            elif len(trioList) == 0: 
                pass
            elif (not minTrioList) or len(trioList) < len(minTrioList):
                minTrioList = trioList
        if updated:
            possibleTrioLists = collectPossibleTrioLists(game)
        else:
            break
    return minTrioList

def searchGame(inputGame, verbose=False, search="bfs"):
    search = search.lower()
    if search == "bfs":
        pop_index = 0
    elif search == "dfs":
        pop_index = -1
    else:
        raise ValueError(f"Unerwarteter Parameter `search`: {search}")
    solutionList = [inputGame] 
    maxSolListLen = 1
    while solutionList:
        game = solutionList.pop(pop_index)
        if verbose:
            print("Aktueller Spielzustand:")
            printGame(game)
            print(f"Länge der Liste: {len(solutionList)}")
        minTrioList = deduce(game)
        if isFilled(game) and isSolved(game):
            if verbose:
                print(f"Maximale Länge der Liste: {maxSolListLen}")
            return game
        elif minTrioList:
            for (i, j, x) in minTrioList:
                newGame = [row.copy() for row in game]
                newGame[i][j] = x
                solutionList.append(newGame)
            if len(solutionList) > maxSolListLen:
                maxSolListLen = len(solutionList)
            if verbose:
                print(f"Maximale Länge der Liste bisher: {maxSolListLen}")
    raise ValueError("Das Spiel kann nicht gelöst werden.")

def solveGame(inputGame, verbose=False, search="bfs"):
    valid, grund = isValid(inputGame)
    if not valid:
        printGame(inputGame)
        raise ValueError("Ungültiges Spiel: " + grund)
    search = search.lower()
    if search not in ["bfs", "dfs"]:
        raise ValueError(f"Unerwarteter Parameter `search`: {search}")
    return searchGame(inputGame, verbose=verbose, search=search)

def timer(fn):
    @functools.wraps(fn)
    def wrapper(*a, **ka):
        t0 = time.time()
        result = fn(*a, **ka)
        tDiff = time.time() - t0
        print(f"Time taken by {fn.__name__}(.): {tDiff}")
        return result
    return wrapper

def ablaufSudoku(gameText):
    solveGameT = timer(solveGame)
    print("---------------------------------------------------------")
    try:
        gameText = formatInput(gameText)
    except ValueError as e:
        print(f"Fehlerhafte Eingabe: {e}")
        return
    game = importGame(gameText)
    printGame(game)
    try:
        solvedGame = solveGameT(game, verbose=False, search="bfs")
    except ValueError as e:
        print(e)
        solvedGame = None
    else:
        if isSolved(solvedGame):
            printGame(solvedGame)
        else:
            print("Sudoku nicht lösbar.")
    print("---------------------------------------------------------")
    return solvedGame
 
# End xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
und

Code: Alles auswählen

import sys
from sudoku import *

def test(input_filename, output_filename):
    gameText = readGame(input_filename)
    solvedGame = ablaufSudoku(gameText)
    if solvedGame != None:
        saveGame(solvedGame, output_filename)

if __name__ == "__main__":
    input_filename = sys.argv[1] if len(sys.argv) > 1 else "aufgabe.txt"
    output_filename = sys.argv[2] if len(sys.argv) > 2 else "loesung.txt"
    test(input_filename, output_filename)
Nicht wundern, warum 2 Files - ich habe noch eine andere test() ohne Files, die die gameText aus einer Liste einliest.

In Lazarus habe ich mein Programm jetzt soweit, daß es alle 3 Methoden die ich ganz oben vermißt und angefragt hatte, implementiert habe, es kommt auch eine Lösung heraus. Nur habe ich noch zu viele Sprachmittel drin, die es in Turbo-Pascal nicht gibt und muß noch meine eigenen Units (Dict, Stack, Sets usw.) einsetzen. Aber schön schon mal zu sehen, daß es richtig rechnet - auch bei 9x9, 16x16 und 25x25 Sudokus. Das "Deduce" bringt von Fall zu Fall sehr viel und macht das Backtracking fast überflüssig.
Antworten