Prolog Sudoku solver issue

Question

I'm trying to write a sudoku 9 x 9 solver. I have used this following code:

:-use_module(library(clpfd)).
solve(X, Grid):-

X =    [A1, A2, A3, A4, A5, A6, A7, A8, A9,
    B1, B2, B3, B4, B5, B6, B7, B8, B9,
    C1, C2, C3, C4, C5, C6, C7, C8, C9,
    D1, D2, D3, D4, D5, D6, D7, D8, D9,
    E1, E2, E3, E4, E5, E6, E7, E8, E9,
    F1, F2, F3, F4, F5, F6, F7, F8, F9,
    G1, G2, G3, G4, G5, G6, G7, G8, G9,
    H1, H2, H3, H4, H5, H6, H7, H8, H9,
    I1, I2, I3, I4, I5, I6, I7, I8, I9],

member(Grid, X),

%rows have to be unique and from 1 to 9
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A1, A2, A3, A4, A5, A6, A7, A8, A9]),
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [B1, B2, B3, B4, B5, B6, B7, B8, B9]),
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [C1, C2, C3, C4, C5, C6, C7, C8, C9]),
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [D1, D2, D3, D4, D5, D6, D7, D8, D9]),
    permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [E1, E2, E3, E4, E5, E6, E7, E8, E9]),
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [F1, F2, F3, F4, F5, F6, F7, F8, F9]),
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [G1, G2, G3, G4, G5, G6, G7, G8, G9]),
    permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [H1, H2, H3, H4, H5, H6, H7, H8, H9]),
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [I1, I2, I3, I4, I5, I6, I7, I8, I9]),


%coloums have to be unique and from 1 to 9
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A1, B1, C1, D1, E1, F1, G1, H1, I1]),
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A2, B2, C2, D2, E2, F2, G2, H2, I2]),
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A3, B3, C3, D3, E3, F3, G3, H3, I3]),
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A4, B4, C4, D4, E4, F4, G4, H4, I4]),
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A5, B5, C5, D5, E5, F5, G5, H5, I5]),
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A6, B6, C6, D6, E6, F6, G6, H6, I6]),
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A7, B7, C7, D7, E7, F7, G7, H7, I7]),
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A8, B8, C8, D8, E8, F8, G8, H8, I8]),
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A9, B9, C9, D9, E9, F9, G9, H9, I9]),

%3X3 boxes have to be unique and from 1 to 9
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A1, A2, A3, B1, B2, B3, C1, C2, C3]),
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A4, A5, A6, B4, B5, B6, C4, C5, C6]),
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [A7, A8, A9, B7, B8, B9, C7, C8, C9]),
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [D1, D2, D3, E1, E2, E3, F1, F2, F3]),
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [D4, D5, D6, E4, E5, E6, F4, F5, F6]),
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [D7, D8, D9, E7, E8, E9, F7, F8, F9]),
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [G1, G2, G3, H1, H2, H3, I1, I2, I3]),
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [G4, G5, G6, H4, H5, H6, I4, I5, I6]),
permutation(['1','2', '3', '4', '5', '6', '7', '8', '9'], [G7, G8, G9, H7, H8, H9, I7, I8, I9]).

However, when I run the query:

solve(X,[_,7,2,4,_,_,_,_,1,_,8,_,7,_,_,3,2,_,6,3,1,_,_,_,7,_,_,_,_,_,5,2,_,_,1,4,_,_,5,9,_,4,6,_,_,8,4,_,_,3,7,_,_,_,_,_,9,_,_,_,2,5,3,_,6,8,_,_,5,_,7,_,2,_,_,_,_,9,4,6,_]).

The program just hangs. Can anyone see what errors i have made? thanks.

EDIT: Noticed the error in the query, however program still hangs after fix

Answer 1

Permute tends to be an expensive operation and CLPFD actually has some other operations that are perfect for sudoku solving. Note that CLPFD stands for Constraint Limit Programming over Finite Domains. CLPFD is designed to allow you to write down facts about the domains of lots of variables and then attempt to solve all of them at once.

This is in opposition to what you wrote, where each permutation is effectively an independent, imperative statement. This means that it finds a solution for the first row, then the second, ..., until it eventually reaches the columns where it fails and has to do a lot of backtracking and retrial before trying a different combination just for the first row... and then it will try all of the combinations for the remaining rows that already failed. I think you can see how this becomes very expensive very quickly.

Like I said, CLPFD is smarter than this. You can apply lots of loose domain constraining statements to your variables and then attempt to solve them all concurrently using label. It is the epitome of lazy evaluation. To write something similar to how you're using permute, you need the commands in/ins and all_different.

1. in/ins: these let you apply numerical domains to variables (in for single variables, ins for lists). X ins 1..9 tells CLPFD that all members of X must have values between 1 and 9.
2. all_different: constrains the domain of each element of a given list, to be unequal to all other elements of the given list. Basically, every element of the list has gotta be different.

(Third time I'm saying this but it's still very important) Neither of these operations tell the interpreter to do any sort of fancy/on-the-spot computation. They just tell CLPFD to throw some facts about constraints on its variables into its constraint storage, and to hold them there until you ask for an answer at the end.

For sudoku, you want to:

1. Apply X ins 1..9
2. Make a list for each column, row, and square, and apply all_different to each.
3. Use the label(X) to tell CLPFD to stop being so goddamn lazy and start trying to apply values to variables. This final step is pretty much permute, only it does it over the whole sudoku board and takes all constraints into consideration when permuting. So even more simply, it means 'solve'.

I've written the same program in the past so you can seek how I used ins, all_different, and label here. Although I'd ask that you make sure you understand the usage before implementing it yourself.

To better understand how CLPFD, applies all those neat constraints and solves for them I'd recommend the wikibook on it.

Answer 2

Running independent permutations is a very heavy calculation. Open up your system monitor, and look at the CPU usage levels. 100% ?

each independent call to permutation/2 works in separation. We should first create the structure to hold our results - the lists - with shared variables. Then permutations would work on shared structure and duplicates will be refused much earlier, easing the computation.

sudoku( Rows ):-
  Rows = [ [A1,B1,C1,D1,E1,F1,G1, ...],
           [A2,B2,C2,D2,E2,F2,G2, ...],
           [A3,B3,C3,D3,E3,F3,G3, ...] ...],
  Cmns = [ [A1,A2,A3 ...], 
           [B1,B2,B3 ...] ...],
  Boxs = [ [A1,B1,C1,A2,B2,C2,A3,B3,C3],
           [D1,E1,F1,D2,E2,F2,D3,E3,F3] ...],
  findall(X, between(1,9,X), L),
  Rows = [R1,R2,R3 ...],
  Cmns = [K1,K2,K3 ...],
  Boxs = [X1,X2,X3 ...],
  maplist( permutation(L), [R1,X1,R2,X2,K1,R3,X3,K2, ...]).

this will be much faster because failed permutations are refuted earlier in the process.

---

edit: no, it doesn't seem to help much. The overhead of independent permutations is too high. This needs to be much more granular. Using permute instead of permutation,

selecting([], S, S).
selecting([A|B], S, R):- select(A,S,S2), selecting(B,S2,R).

permute(L,X):- partition(var, X, Vs, Ns),
   selecting(Ns,L,L2), permutation(L2,Vs).

seems to help a little bit, but not much. I can get as far now as maplist( permute(L), [X1,X2,R1,R2,R3,X3,K1,K2,K3,X4,R4,K4,X5,X6]) relatively easily, but adding R5 doubles the run time, and after further adding K5 it doesn't finish in 7x that time.