Prolog Solvers

SudokuSolver.pl

% (SWI-Prolog)
:- use_module(library(clpfd)).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%!	sudoku(?Rows) is nondet.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

sudoku(Rows) :-
	sudoku__rows(Rows),
	sudoku__cols(Rows),
	sudoku__boxs(Rows),
	sudoku__lbl(Rows).

sudoku__lbl([]).
sudoku__lbl([Row| Rs]) :-
	label(Row),						%% (S) solve
	sudoku__lbl(Rs).

sudoku__rows(Rows) :-
	length(Rows, 9),
	sudoku__rows_do(Rows).

sudoku__rows_do([]).
sudoku__rows_do([Row| Rs]) :-
	length(Row, 9),
	Row ins 1..9,					%% (C.0) each element in 1..9
	all_different(Row),			%% (C.1) row elements all different
	sudoku__rows_do(Rs).

sudoku__cols(Rows) :-
	Rows = [R1, R2, R3, R4, R5, R6, R7, R8, R9],
	sudoku__cols_do(R1, R2, R3, R4, R5, R6, R7, R8, R9).

sudoku__cols_do([], [], [], [], [], [], [], [], []).
sudoku__cols_do(R1, R2, R3, R4, R5, R6, R7, R8, R9) :-
	R1 = [R11| RT1], R2 = [R21| RT2], R3 = [R31| RT3],
	R4 = [R41| RT4], R5 = [R51| RT5], R6 = [R61| RT6],
	R7 = [R71| RT7], R8 = [R81| RT8], R9 = [R91| RT9],
	Col = [R11, R21, R31, R41, R51, R61, R71, R81, R91],
	all_different(Col),			%% (C.2) col elements all different
	sudoku__cols_do(RT1, RT2, RT3, RT4, RT5, RT6, RT7, RT8, RT9).

sudoku__boxs(Rows) :-
	Rows = [R1, R2, R3, R4, R5, R6, R7, R8, R9],
	sudoku__boxs_do(R1, R2, R3),
	sudoku__boxs_do(R4, R5, R6),
	sudoku__boxs_do(R7, R8, R9).

sudoku__boxs_do([], [], []).
sudoku__boxs_do(R1, R2, R3) :-
	R1 = [R11, R12, R13| RT1],
	R2 = [R21, R22, R23| RT2],
	R3 = [R31, R32, R33| RT3],
	Box = [R11, R12, R13, R21, R22, R23, R31, R32, R33],
	all_different(Box),			%% (C.3) box elements all different
	sudoku__boxs_do(RT1, RT2, RT3).

SudokuSolverTests.pl

/* ---------------------------------------------------------------------------

% EASY
?- test_sudoku_ok('00',_Rows).
% 226,573 inferences, 0.047 CPU in 0.047 seconds (100% CPU, 4841272 Lips)

% HARD ("Platinum Blonde")
% http://mathforum.org/kb/message.jspa?messageID=9121982
?- test_sudoku_ok('01',_Rows).
% 47,972,512 inferences, 8.299 CPU in 8.315 seconds (100% CPU, 5780341 Lips)

% HARD ("Unsolvable 28")
% http://www.sudokuwiki.org/Weekly_Sudoku.asp?puz=28
?- test_sudoku_ok('02',_Rows).
% 63,482,589 inferences, 11.154 CPU in 11.185 seconds (100% CPU, 5691427 Lips)

% HARD ("Ronk's Level 3")
% http://www.sudokuwiki.org/A_New_Metric_for_Difficult_Sudoku_Puzzles
?- test_sudoku_ok('03',_Rows).
% 29,681,385 inferences, 5.179 CPU in 5.195 seconds (100% CPU, 5730845 Lips)

--------------------------------------------------------------------------- */

% (SWI-Prolog)
:- consult('SudokuSolver.pl').

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%!	test_sudoku_NN(-Rows)		is det.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

test_sudoku_00(
	[	[ _, 3, _, _, _, 9, _, _, 5 ],
		[ 6, _, _, 8, _, _, _, 1, _ ],
		[ _, _, 4, _, _, 3, _, _, _ ],
		[ 1, _, _, _, 5, _, _, 4, _ ],
		[ _, _, 7, _, _, _, 3, _, _ ],
		[ _, 9, _, _, 6, _, _, _, 8 ],
		[ _, _, _, 2, _, _, 7, _, _ ],
		[ _, 5, _, _, _, 8, _, _, 2 ],
		[ 4, _, _, 1, _, _, _, 3, _ ]
	]).

test_sudoku_01(
	[	[ _, _, _, _, _, _, _, 1, 2 ],
		[ _, _, _, _, _, _, _, _, 3 ],
		[ _, _, 2, 3, _, _, 4, _, _ ],
		[ _, _, 1, 8, _, _, _, _, 5 ],
		[ _, 6, _, _, 7, _, 8, _, _ ],
		[ _, _, _, _, _, 9, _, _, _ ],
		[ _, _, 8, 5, _, _, _, _, _ ],
		[ 9, _, _, _, 4, _, 5, _, _ ],
		[ 4, 7, _, _, _, 6, _, _, _ ]
	]).

test_sudoku_02(
	[	[ 6, _, _, _, _, 8, 9, 4, _ ],
		[ 9, _, _, _, _, 6, 1, _, _ ],
		[ _, 7, _, _, 4, _, _, _, _ ],
		[ 2, _, _, 6, 1, _, _, _, _ ],
		[ _, _, _, _, _, _, 2, _, _ ],
		[ _, 8, 9, _, _, 2, _, _, _ ],
		[ _, _, _, _, 6, _, _, _, 5 ],
		[ _, _, _, _, _, _, _, 3, _ ],
		[ 8, _, _, _, _, 1, 6, _, _ ]
	]).

test_sudoku_03(
	[	[ 1, _, _, _, _, _, 7, _, _ ],
		[ _, _, 7, 1, _, 9, _, _, _ ],
		[ 6, 8, _, _, 7, _, _, _, _ ],
		[ _, _, 1, _, 9, _, 6, _, _ ],
		[ _, _, _, 3, _, _, _, 2, _ ],
		[ _, 4, _, _, _, _, _, _, 3 ],
		[ _, _, 8, _, 6, _, 1, _, _ ],
		[ 5, _, _, _, _, _, _, 4, _ ],
		[ _, _, _, _, _, 2, _, _, 5 ]
	]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%!	test_sudoku(?Rows)			is nondet.
%!	test_sudoku(+NN, ?Rows)		is nondet.
%!	test_sudoku_all(+NN, -Cnt)	is semidet.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

test_sudoku(Rows) :-
	time(sudoku(Rows)),
	test_sudoku__write(Rows).

test_sudoku(NN, Rows) :-
	test_sudoku__case(NN, Rows),
	test_sudoku(Rows).

test_sudoku_ok(NN, Rows) :-
	test_sudoku__case(NN, Rows),
	time(findall(Rows, sudoku(Rows), [Rows])),
	test_sudoku__write(Rows).

test_sudoku__write([]).
test_sudoku__write([Row| Rs]) :-
	writeln(Row),
	test_sudoku__write(Rs).

test_sudoku__case(NN, Rows) :-
	atom_concat('test_sudoku_', NN, G_nn),
	call(G_nn, Rows).