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
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
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.
