Saturday, January 15, 2011

Sudoku solver in Prolog

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..9 domain and then used clpfd:all_distinct predicate. Elegant and fast.


Updated on 4 Mar 2011: Format of examples updated.














A sudoku example
521379468
46  15 7 
3  68425 
893526147
  6 4 9 3
 4 9 1  6
2   63895
 841 7  2
  5 9 7 4












... and solved
521379468
468215379
379684251
893526147
156748923
742931586
217463895
984157632
635892714

2 comments:

Anonymous said...

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.

_St said...

Yes, I tried declaring dif/2 before instantiating the row permutation, but did not notice any major improvement in performance.