sudoku_simple.pl : Simple Sudoku Solver Very naive sudoku solver in just two rules. Use one of the more advanced solvers if you actually want to solve real sudoku puzzles. This one is for toy examples.
How to use: Board positions are encoded as Row-Col, e.g. the top-left corner is 1-1 and the top-right corner is 1-9. First give all given cell values as given(Row-Col,Value). Then give all unknown cells as maybe(Row-Col,[1,2,3,4,5,6,7,8,9]). (or another second argument if you want to solve smaller or larger sudoku puzzles) Look at the example queries for some useful auxiliary predicates. The predicate sees/2 is used to compare two sudoku positions; it should succeed if two positions cannot share the same value and it should fail otherwise.
See also: See also: sudoku.pl
Program: Change the code, then submit! /* sudoku_simple.pl: Simple Sudoku Solver (C) Jon Sneyers, October 2009, K.U.Leuven This program is distributed under the terms of the GNU General Public License: http://www.gnu.org/licenses/gpl.html %% DESCRIPTION Very naive sudoku solver in just two rules. Use one of the more advanced solvers if you actually want to solve real sudoku puzzles. This one is for toy examples. %% HOW TO USE Board positions are encoded as Row-Col, e.g. the top-left corner is 1-1 and the top-right corner is 1-9. First give all given cell values as given(Row-Col,Value). Then give all unknown cells as maybe(Row-Col,[1,2,3,4,5,6,7,8,9]). (or another second argument if you want to solve smaller or larger sudoku puzzles) Look at the example queries for some useful auxiliary predicates. The predicate sees/2 is used to compare two sudoku positions; it should succeed if two positions cannot share the same value and it should fail otherwise. %% SEE ALSO See also: sudoku.pl %% SAMPLE QUERIES Q: mini. A: given(4-4, 2), given(4-3, 3), given(4-2, 1), given(4-1, 4), given(3-4, 1), given(3-2, 2), given(3-1, 3), given(2-4, 4), given(2-3, 1), given(1-4, 3), given(3-3, 4), given(2-2, 3), given(2-1, 2), given(1-3, 2), given(1-2, 4), given(1-1, 1) */ :- use_module(library(chr)). :- use_module(library(lists)). :- chr_option(optimize,full). :- chr_option(debug,off). :- chr_constraint given(+pos,+val), maybe(+pos,+list(val)). :- chr_type pos ---> row-col. :- chr_type row == int. :- chr_type col == int. :- chr_type val == int. :- chr_type list(X) ---> [] ; [X|list(X)]. given(P1,V) \ maybe(P2,L) <=> sees(P1,P2), select(V,L,L2) | maybe(P2,L2). maybe(P,L) <=> member(V,L), given(P,V). sees(X-_, X-_). % same row sees(_-X, _-X). % same column % 9-by-9 sudoku %sees(X-Y, A-B) :- X//3 =:= A//3, Y//3 =:= B//3. % same 3x3 box % 4-by-4 sudoku sees(X-Y, A-B) :- X//2 =:= A//2, Y//2 =:= B//2. % same 2x2 box mini :- X = [[1,4,2,-], [2,3,-,-], [-,-,4,-], [-,-,-,-]], givens(X), maybes(X,[1,2,3,4]). % query below takes ages - this sudoku solver is too naive for real puzzles % (also make sure to use the right definition of sees/2) example :- X = [[5,3,-,-,7,-,-,-,-], [6,-,-,1,9,5,-,-,-], [-,9,8,-,-,-,-,6,-], [8,-,-,-,6,-,-,-,3], [4,-,-,8,-,3,-,-,1], [7,-,-,-,2,-,-,-,6], [-,6,-,-,-,-,2,8,-], [-,-,-,4,1,9,-,-,5], [-,-,-,-,8,-,-,7,9]], givens(X), maybes(X,[1,2,3,4,5,6,7,8,9]). givens(L) :- givens(L,1). givens([],_). givens([Row|Rest],N) :- givens(Row,N,1), N1 is N+1, givens(Rest,N1). givens([],_,_). givens([X|Xs],Row,Col) :- (X = '-' -> true ; given(Row-Col,X) ), Col1 is Col+1, givens(Xs,Row,Col1). maybes(L,N) :- maybes(L,1,N). maybes([],_,_). maybes([Row|Rest],N,M) :- maybes(Row,N,1,M), N1 is N+1, maybes(Rest,N1,M). maybes([],_,_,_). maybes([X|Xs],Row,Col,M) :- (X = '-' -> maybe(Row-Col,M) ; true ), Col1 is Col+1, maybes(Xs,Row,Col1,M).
Console: Enter query or select example from below, then submit and wait for answer! % loading puzzle/sudoku_simple.pl | ?- consult(...). yes [0.439 seconds] | ?-