sudoku

% helper predicates
square_to_subgrid(Row, Col, Subgrid) :- 
        floor((Row - 1)/3, RowBase), 
        floor((Col - 1)/3, ColBase), 
        Subgrid is 3 * RowBase + ColBase + 1.
one_to_nine(X) :-
        member( X, [1, 2, 3, 4, 5, 6, 7, 8, 9] ).
next_square( Puzzle, Row, Col ) :-
        one_to_nine(Row), 
        one_to_nine(Col),
        not( member( [Row, Col, _], Puzzle ) ), !.

% print the sudoku puzzle
print_puzzle( [] ).
print_puzzle( [[_, 9, Value] | Tail] ) :-
        write( Value ), nl, print_puzzle( Tail ).
print_puzzle( [[_, _, Value] | Tail] ) :-
        write( Value ), write( ' ' ), print_puzzle( Tail ).

% the puzzle is solved if length is 81
solve( Puzzle ) :- 
        length( Puzzle, 81 ),
        print_puzzle( Puzzle ).

% solve the puzzle
solve( Puzzle ) :-
        guess( Puzzle, Row, Col, Val ),
        insert( [Row, Col, Val], Puzzle, NewPuzzle ),
        solve( NewPuzzle ).

% guess a value for the next empty square
guess( Puzzle, Row, Col, Val ) :-
       next_square( Puzzle, Row, Col ),
       one_to_nine( Val ),
       check( Puzzle, Row, Col, Val ).
% check to see if the guess violates the rules
check( Puzzle, Row, Col, Val ) :-
       not(is_in_row( Puzzle, Row, Val )),
       not(is_in_col( Puzzle, Col, Val )),
       square_to_subgrid( Row, Col, Subgrid ),
       not(is_in_subgrid( Puzzle, Subgrid, Val )).
% see if the value is already in the row
is_in_row( [], Row, Val ) :- fail.
is_in_row( [[R, C, V] | PTail], Row, Val ) :-
       R == Row, V == Val, is_in_row( PTail, Row, Val ).
% see if the value is already in the column
is_in_col( [], Col, Val ) :- fail.
is_in_col( [[R, C, V] | PTail], Col, Val ) :-
       C == Col, V == Val, is_in_col( PTail, Col, Val ).
% see if the value is already in the subgrid
is_in_subgrid( [], Subgrid, Val ) :- fail.
is_in_subgrid( [[R, C, V] | PTail], Subgrid, Val ) :-
       square_to_subgrid( R, C, SG ),
       SG == Subgrid, V == Val,
       is_in_subgrid(PTail, Subgrid, Val).

% insert a square into the puzzle
insert( [Row, Col, Val], Puzzle, NewPuzzle ) :-
       NP = NewPuzzle,
       append( NP, [Row, Col, Val], NewPuzzle ).
insert( [Row, Col, Val], Puzzle, NewPuzzle ) :-
       C < Col, !,
       [[R, C, V]| PTail] = Puzzle,
       Row == R,
       append( NewPuzzle, [R, C, V], NP ),
       insert( [Row, Col, Val], PTail, NP ).