| Moderator
Registriert seit: 20.07.05 Likes: 198 | 
Eine etwas andere Lösungsweise:
Wir betrachten einmal die Regeln: es gibt Zeilen, Spalten und Blöcke. Darin sollen Ziffern von 1 bis N stehen. Weder in einer Zeile,noch Spalte noch Block soll eine Ziffer doppelt vorkommen.
D.h ein intelligenter Brutforcer sollte beim Ausprobieren erstmal berücksichtigen, welche Ziffern überhaupt als Kandidaten in Frage kommen, bevor er etwas einträgt.
Damit wären wir auch schon bei der Lösung  : http://de.wikipedia.org/wiki/Constraintprogrammierung
Umsetzung (ja, in diesem Stück Code steckt wirklich sowohl der "Löser" wie auch der "Korrektheit-Checker" ): sudoku.pl, Sicstus Version,mit SWI kompatibel Code: :-use_module(library(clpfd)).
:-consult(processfile).
:-consult(sudoku_prettyprint).
constrain_rows([]).
constrain_rows([Row|Rows]):- all_different(Row),constrain_rows(Rows).
constrain_lines([]).
constrain_lines([Line|Lines]):- all_different(Line),constrain_lines(Lines).
constrain_blocks([]).
constrain_blocks([Block|Blocks]):- all_different(Block),constrain_blocks(Blocks).
constrain_all(Domain,Cells,Ln,Rw,Bl):- domain(Cells,1,Domain), %Cells ins 1..Domain,
constrain_rows(Rw),
constrain_lines(Ln),
constrain_blocks(Bl).
solve(File):-processfile(File,Cells,Domain,Ln,Rw,Bl),
constrain_all(Domain,Cells,Ln,Rw,Bl),
labeling([ff],Cells),board(Domain,LinesInBlock,RowsInBlock),
print(Ln,LinesInBlock,RowsInBlock). der Code macht nichts anderes, als sich erstmal das Spielfeld (Zeilen,Spalten,Blöcke)
zu holen und ihre Bereiche zu definieren. Die Lösung ist dann eine Platzierung aller Ziffern, die diese Regeln nicht verletzen.
Wer SWI nutzt, sollte in Zeile 14 das "domain(...)" durch das auskommentierte "Cells ins 1..Domain" ersetzen.
Jetzt die 2 Begleitmodule: sudoku_prettyprint Code: print(Lines,LinesInBlock,RowsInBlock):-print(Lines,1,LinesInBlock,RowsInBlock),!.
print([],_,_,_).
print([Line|Lines],Count,LinesInBlock,RowsInBlock):-
print_line(Line,1,RowsInBlock),
(0 is mod(Count,LinesInBlock),nl,nl;nl),
NewCount is Count+1,print(Lines,NewCount,LinesInBlock,RowsInBlock).
print_line([E],_,_):-write(E).
print_line([E|Elements],Count,RowsInBlock):-
(0 =\= mod(Count,RowsInBlock),
format('~q,',[E]);
format('~q ',[E])),
NewCount is Count+1,
print_line(Elements,NewCount,RowsInBlock),!. sorgt für die schöne formatierte Ausgabe ;) processfile, liest die Datei ein und zerlegt das Spielfeld in Zeilen/Spalten/Blöcke Code: %anpassbar: für jeden:
%Zeichen, die als Platzhalter dienen:
char('0',_).
char('.',_).
char(X,Num):-number_chars(Num,[X]).
%festcodierte Blockgrößen: board(Seitenlänge,Zeilen im Block,Spalten im Block)
board(6,2,3).
board(8,2,4).
board(9,3,3).
board(12,3,4).
board(16,4,4).
board(25,5,5).
board(X,_,_):- \+member(X,[6,8,9,12,16,25]),write('Unbekannte Sudoku Größe, bitte die Aufteilung des Feldes\n'),
write('in Blocks(wieviele Zeilen/Spalten im Block sind) vornehemen!\n'),
write('In: processfile.pl, ab Zeile 7'),fail.
%anpassbar: nicht für jeden ;-)
:-use_module(library(lists)).
processfile(File,Cells,Domain,Lines,Rows,Blocks):-open(File,read,Stream),
(reader(Stream,Cells)->close(Stream);close(Stream)),
check(Cells,Domain),lines(Cells,Lines),rows(Lines,Rows),
blocks(Cells,Blocks).
check(Cells,Size):-length(Cells,Len),Size is ceiling(sqrt(Len)),board(Size,_,_),!.
reader(Stream,[]):- peek_char(Stream,end_of_file),!.
reader(Stream,[Cell|Cells]):- get_char(Stream,Char),get_cell(Char,Cell),reader(Stream,Cells),!.
reader(Stream,T):-reader(Stream,T),!.
get_cell(Char,Cell):-
Char\='\n',char(Char,Cell).
/*Konstruiere Spalten
Parameter: +Input,-Result; Zeilenlänge muss =Zeilenanzahl */
rows(Lines,Res):-length(Lines,RowSize),rows(Lines,0,RowSize,Res),!.
rows(_,Size,Size,[]).
rows(Lines,Count,Size,[Row|Rows]):- NewCount is Count+1 ,
row(Lines,NewCount,Row),
rows(Lines,NewCount,Size,Rows).
row([],_,[]).
row([Line|Lines],Nth,[E|Row]):- nth1(Nth,Line,E),row(Lines,Nth,Row).
/*Konstruiere aus Raw Data Zeilen
Parameter: +Input,-List of Lines,Inputgröße sollte X*X sein, wobei X ganzzahlig ist*/
lines([],[],_).
lines(Data,[Line|Lines],Len):- line(Data,0,Len,Line,Tail),lines(Tail,Lines,Len).
lines(Data,Lines):- line_len(Data,LineLen),
lines(Data,Lines,LineLen),!.
line(Tail,Size,Size,[],Tail).
line([E|Data],Count,Size,[E|Line],Tail):-NewCount is Count+1,
line(Data,NewCount,Size,Line,Tail).
line_len(Cells,LineLen):-length(Cells,Len),LineLen is (ceiling(sqrt(Len))).
blocks(Cells,Blocks):-line_len(Cells,Len),board(Len,LnNum,RowNum),
TotalBlocks is ceiling((Len*Len)/(LnNum*RowNum)),
blocks(Cells,TotalBlocks,Len,Blocks),!.
blocks(_,0,_,[]).
blocks(Cells,Count,Len,[Block|Blocks]):-block(Cells,0,Count,Len,Block),NewCount is Count-1,
blocks(Cells,NewCount,Len,Blocks),!.
block([],_,_,_,[]).
block([Cell|Cells],Count,Num,Len,[Cell|Block]):- board(Len,LnNum,RowNum),
VBlocks is ceiling(Len/LnNum),
BlockNum is ceiling(floor(Count/Len+1)/LnNum)
+ (ceiling((mod(Count,Len)+1)/RowNum)*VBlocks)-VBlocks,
NewCount is Count+1,BlockNum is Num,
block(Cells,NewCount,Num,Len,Block),!.
block([_|Cells],Count,Num,Len,Block):- NewCount is Count+1,
block(Cells,NewCount,Num,Len,Block),!. hier wird das Spielfeld eingelesen und in Zeilen, Spalen und Blöcke unterteilt.
Da die Routine mit dynamischen Größen arbeitet sind es eben etwas mehr Zeilen Code ;). Ein festkodiertes 9x9 Board könnte man natürlich auch mit viel weniger Aufwand erstellen.
Diese Sichtweise ist nicht nur extrem bequem bei dieser Problemstellung - sie ist auch viel effizienter, als reines BF. Bsp:
"Near worst case" sudoku puzzle for brute force solver" http://en.wikipedia.org/wiki/Algorit...orce_algorithm
Ausgabe: Ausgabe Zitat:
SICStus 4.0.4 (x86-win32-nt-4): Tue Jun 17 00:06:53 WEST 2008
?- time(solve('worstcase.sudoku')).
9,8,7 6,5,4 3,2,1
2,4,6 1,7,3 9,8,5
3,5,1 9,2,8 7,4,6
1,2,8 5,3,7 6,9,4
6,3,4 8,9,2 1,5,7
7,9,5 4,6,1 8,3,2
5,1,9 2,8,6 4,7,3
4,7,2 3,1,9 5,6,8
8,6,3 7,4,5 2,1,9
solve('worstcase.sudoku') took 0.313 sec.
|
Die Messzeit beinhaltet den kompletten Vorgang -auch das Lesen/Parsen des Spielfeldes von der Festplatte
Andere: Eastermonster,tarek,golden nugget Zitat:
time(solve('eastermonster.sudoku')).
1,7,4 3,8,5 9,6,2
2,9,3 4,6,7 1,5,8
5,8,6 1,9,2 7,3,4
4,5,1 9,2,3 8,7,6
9,2,8 6,7,4 3,1,5
3,6,7 8,5,1 2,4,9
7,1,9 5,4,8 6,2,3
6,3,5 2,1,9 4,8,7
8,4,2 7,3,6 5,9,1
solve('eastermonster.sudoku') took 0.031 sec.
yes
| Zitat:
| ?- time(solve('tarek.sudoku')).
7,6,1 3,5,4 2,8,9
2,9,8 1,6,7 3,4,5
4,5,3 9,2,8 1,6,7
8,1,2 6,4,9 7,5,3
9,7,6 5,1,3 4,2,8
5,3,4 8,7,2 6,9,1
3,2,7 4,8,5 9,1,6
1,8,9 2,3,6 5,7,4
6,4,5 7,9,1 8,3,2
solve('tarek.sudoku') took 0.062 sec.
yes
| Zitat:
| ?- time(solve('goldennugget.sudoku')).
7,5,1 8,4,6 2,3,9
8,9,2 3,7,1 4,6,5
6,4,3 2,5,9 8,7,1
2,3,8 1,9,7 5,4,6
9,7,4 5,6,2 3,1,8
1,6,5 4,3,8 9,2,7
3,1,9 6,8,4 7,5,2
5,2,7 9,1,3 6,8,4
4,8,6 7,2,5 1,9,3
solve('goldennugget.sudoku') took 0.110 sec.
yes
|
Nutzung:
solve(Filename).
Spielfeldformat: wie in Wikipedia - entweder Ziffern oder Platzhalter(0 oder . (Punkt)),
Zeilenumbrüche sind egal. Wer andere Zeichen als Platzhalter nutzen möchte, sollte sie in 'processfile' (ab Zeile 1 - siehe Kommentar) eintragen.
Spielfeldgrößen: dynamisch. Allerdings gibt es 2 Sachen - zum einen muss bei exotischen Boards die Blockauteilung noch eingetragen werden (wieviele Zeilen/Spalten in einem Block sein sollen). Zum anderen hatte ich dann keine Lust mehr eine Extraroutine zum Einlesen von Boards>9 (vor allem - jemand müsste diese Boards vorher auch noch abtippen ) zu erstellen, so dass aktuell nur Boards bis 9x9 eingelesen werden.
__________________
Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
Selig, wer nichts zu sagen hat und trotzdem schweigt. |