Noticing sudoku almost everywhere, I thought it might be a good excercise to develop a sudoku solver. I spend a bit of time thinking and remembered that it could go easily in Prolog. So I started playing.
Sudoku has simple rules, every row, every column and every marked block contains numbers 1 to 9, each exactly once. Hence my first idea:
sudoku(Plan) :-
get_rows( Plan, Rows), % Plan = Rows,
get_columns( Plan, Columns), % transpose( Plan, Columns),
get_blocks( Plan, Blocks),
% every row, every column, every block is actually permutation of 1..9
maplist( permutation([1,2,3,4,5,6,7,8,9]), Rows),
maplist( permutation([1,2,3,4,5,6,7,8,9]), Columns),
maplist( permutation([1,2,3,4,5,6,7,8,9]), Blocks).
I am afraid the first idea, did not give any answer in reasonable time. I remembered that in large backtracking you need to fail as soon as possible. The second attempt
sudoku(Plan) :-
rows( Plan, []),
% columns are OK thanks to rows predicate
get_blocks( Plan, Blocks),
maplist( permutation([1,2,3,4,5,6,7,8,9]), Blocks).
rows( [], _).
rows( [ActualRow|RowsBelow], RowsAbove) :-
% instantiate free variables in the actual row
permutation( [1,2,3,4,5,6,7,8,9], ActualRow),
% only allow meaningful rows
maplist( constrain_difs( ActualRow), RowsAbove),
rows( RowsBelow, [ActualRow|RowsAbove]).
constrain_difs( [], []).
constrain_difs( [X|Xs], [Y|Ys]) :-
X \= Y,
constrain_difs( Xs, Ys).
had a great improvement. Immediately after the free variables were instantiated in the
ActualRow, there was a constraint that the ActualRow had to be different from any RowsAbove on every column. As an effect, any row that would obviously break the sudoku was rejected soon and resulting columns were following the sudoku rules.The second version responded in few seconds already.
Notes:
- I have been using SWI-Prolog.
- While browsing the documentation I discovered another sudoku solver in clpfd library, that limited variables to
1..9domain and then usedclpfd:all_distinctpredicate. Elegant and fast.
Updated on 4 Mar 2011: Format of examples updated.
| 5 | 2 | 1 | 3 | 7 | 9 | 4 | 6 | 8 |
| 4 | 6 | 1 | 5 | 7 | ||||
| 3 | 6 | 8 | 4 | 2 | 5 | |||
| 8 | 9 | 3 | 5 | 2 | 6 | 1 | 4 | 7 |
| 6 | 4 | 9 | 3 | |||||
| 4 | 9 | 1 | 6 | |||||
| 2 | 6 | 3 | 8 | 9 | 5 | |||
| 8 | 4 | 1 | 7 | 2 | ||||
| 5 | 9 | 7 | 4 |
| 5 | 2 | 1 | 3 | 7 | 9 | 4 | 6 | 8 |
| 4 | 6 | 8 | 2 | 1 | 5 | 3 | 7 | 9 |
| 3 | 7 | 9 | 6 | 8 | 4 | 2 | 5 | 1 |
| 8 | 9 | 3 | 5 | 2 | 6 | 1 | 4 | 7 |
| 1 | 5 | 6 | 7 | 4 | 8 | 9 | 2 | 3 |
| 7 | 4 | 2 | 9 | 3 | 1 | 5 | 8 | 6 |
| 2 | 1 | 7 | 4 | 6 | 3 | 8 | 9 | 5 |
| 9 | 8 | 4 | 1 | 5 | 7 | 6 | 3 | 2 |
| 6 | 3 | 5 | 8 | 9 | 2 | 7 | 1 | 4 |
2 comments:
Using finite domain constraints for Sudoku is indeed elegant and efficient, and probably the best option. You can still improve your own version even without switching to CLP(FD) by posting dif/2 constraints as soon as possible, allowing faster pruning in permutation/2.
Yes, I tried declaring dif/2 before instantiating the row permutation, but did not notice any major improvement in performance.
Post a Comment