Sudoku solver in clp(FD)

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) :-
 fd_domain(P,1,9),
 Xs = [1,2,3,4,5,6,7,8,9],
 row(P,Xs),
 col(P,Xs),
 unit(P,Xs),
 fd_labeling(P).

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

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

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),
 fd_all_different(L),
 unit(P,Us).

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

About these ads