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

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

... and solved

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