kuoe0
7/21/2013 - 5:06 PM

## sudoku solver with Prolog

sudoku solver with Prolog

``````%=============================================================================
%     FileName: sudoku_solver.pl
%         Desc: sudoku solver
%  Environment: Mac OS X 10.8.2, SWI-Prolog 6.2.6
%        Usage: swipl -q -s sudoku_solver.pl
%        Input: Enter all number in one line and seperate by one space. 0 denote the empty element.
%       Output: Show all number in one line and seperate by one space.
%       Author: KuoE0
%        Email: kuoe0.tw@gmail.com
%     HomePage: http://kuoe0.ch/
%=============================================================================

% index conversion
get_index(Row, Col, Idx) :- Idx is Row * 9 + Col.
get_col(Idx, Col) :- Col is Idx mod 9.
get_row(Idx, Row) :- Row is Idx div 9.
get_block(Idx, Block) :-
get_row(Idx, R), get_col(Idx, C),
Block is (R div 3) * 3 + C div 3.
get_pos(Idx, Row, Col, Block) :-
get_row(Idx, Row), get_col(Idx, Col), get_block(Idx, Block).

% find the available number with constraints
available(Row, Col, Block, X) :-
between(1, 9, X),
not(row_used(Row, X)),
not(col_used(Col, X)),
not(block_used(Block, X)).

% initial the constraints with the original problem
init_cons([], _).
% non-empty element
init_cons([Num|Remain], Idx) :-
between(1, 9, Num),
get_pos(Idx, R, C, B),
% add the constraints into database
asserta(row_used(R, Num)),
asserta(col_used(C, Num)),
asserta(block_used(B, Num)),
Idx1 is Idx + 1, init_cons(Remain, Idx1).
% skip empty element
init_cons([Num|Remain], Idx) :-
not(between(1, 9, Num)),
Idx1 is Idx + 1, init_cons(Remain, Idx1).

modify_cons(Cons) :- asserta(Cons).
modify_cons(Cons) :- retract(Cons), fail.

% solve
solve_sudoku(Prob, Sol) :-
init_cons(Prob, 0),
solve(Prob, Sol, 0).

% key procedure
solve([],Sol,_) :- Sol = [].
% skip non-empty element
solve([Num|Remain], Sol, Idx) :-
between(1, 9, Num),
Idx1 is Idx + 1, solve(Remain, Sol1, Idx1), Sol = [Num|Sol1].
% enumerate available number
solve([Num|Remain], Sol, Idx) :-
not(between(1, 9, Num)),
get_pos(Idx, R, C, B),
available(R, C, B, X),
modify_cons(row_used(R, X)),
modify_cons(col_used(C, X)),
modify_cons(block_used(B, X)),
Idx1 is Idx + 1, solve(Remain, Sol1, Idx1), Sol = [X|Sol1].

sudoku_solver :-