Skip to content

Instantly share code, notes, and snippets.

@thornbill
Created February 3, 2015 21:57
Show Gist options
  • Save thornbill/c9568b24131d2594f8dc to your computer and use it in GitHub Desktop.
Save thornbill/c9568b24131d2594f8dc to your computer and use it in GitHub Desktop.
% 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 ).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment