Sudoku solver in clp(FD)

July 17, 2006

Here’s the code for a sudoku solver written in GNU Prolog using the constraint logic programming library. The puzzle is represented as a list of variables and numbers. The interpreter took 500ms to solve a hard puzzle, but it should run much faster when compiled. GNU Prolog behaved strangely in some cases. The findall predicate makes a copy of the terms it collects; therefore, applying the fd_all_different constraint doesn’t effect the main puzzle. I switched to setof which has the expected behavior; however, a nested setof (one within the goal of another) also copies the terms. I assume both are a bug because there is a copy_term predicate available if I need that behavior. The code could probably be shrunk significantly to compete with the shortest sudoku solvers.

sudoku(P) :-
 Xs = [1,2,3,4,5,6,7,8,9],

row(P,[X|Xs]) :-
 setof(V,[C,I]^(for(C,1,9),I is (X-1)*9+C,nth(I,P,V)),L1),

col(P,[X|Xs]) :-
 setof(V,[R,I]^(for(R,1,9),I is (R-1)*9+X,nth(I,P,V)),L2),

unit(P,[U|Us]) :-
 Cs is ((U-1) mod 3)*3+1, Ce is Cs+2,
 Rs is ((U-1) // 3)*3+1, Re is Rs+2,
 setof(V,[R,C,I]^(for(R,Rs,Re),for(C,Cs,Ce),I is (R-1)*9+C,nth(I,P,V)),L),

| ?- L=[_,_,3,_,2,_,6,_,_,
        _,_,5,_,1,_,3,_,_], sudoku(L).

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Get every new post delivered to your Inbox.

%d bloggers like this: