The representation I chose is a bit different from the ones I have seen in class and in the Internet. It is neither an array (Prolog emulation of an array using arg/3) of numbers, nor a plain list of numbers. It is a list of triples of the form X/Y/Value, where X and Y are the horizontal/vertical coordinates, and Value the number in the square. At first such a representation may seem a bit strange. However, it allows us (for example) to extract whole columns and rows through unification, which simplifies things a bit.

I have written the whole program with readability and conceptual simplicity in mind. This means it is not very efficient. I planned it to be as general as possible, so in principle it should be able to sort 27x27 sudoku. However, due to the lack of efficiency this may take quite a long time (provided you had a 27x27 grid partially filled with integers from 1 to 81, of course).

%

% all the elements in a column, row, 3x3 box.

%

column(X/_, Sudoku, Column) :-

findall(X/Y/Z , (member(X/Y/Z, Sudoku), nonvar(Z)), Column).

row(_/Y, Sudoku, Row) :-

findall(X/Y/Z, (member(X/Y/Z, Sudoku), nonvar(Z)), Row).

% believe me or not, this was the most difficult predicate to write.

box(Base, X/Y, Sudoku, Box) :- % Base: size of the puzzle

DiffX is (X-1) mod (Base/3),

DiffY is (Y-1) mod (Base/3),

StartX is X - DiffX,

StartY is Y - DiffY,

EndX is StartX + (Base/3) - 1,

EndY is StartY + (Base/3)-1,

findall(X1/Y1/Z,

(

between(StartX,EndX,X1),

between(StartY, EndY, Y1),

member(X1/Y1/Z, Sudoku),

nonvar(Z)

),

Box).

%

% We can assign the value Possible to X/Y without

% violating the rules of the sudoku.

%

possible(_,X/Y/Possible, Sudoku) :-

member(X/Y/Possible, Sudoku),

nonvar(Possible), !.

possible(Base, X/Y/Possible, Sudoku) :-

column(X/Y, Sudoku, Column),

row(X/Y, Sudoku, Row),

box(Base, X/Y, Sudoku, Box),

between(1,Base, Possible),

\+member(_/_/Possible, Column),

\+member(_/_/Possible, Row),

\+member(_/_/Possible, Box).

% solve the puzzle, iterating through each grid

solve(_,N,N,_).

solve(Base,N,K,Solution) :-

nth1(N, Solution, X/Y/Z),

possible(Base, X/Y/Z, Solution),

NewN is N+1,

solve(Base, NewN, K, Solution).

solve(Base,Solution) :-

N is Base*Base+1,

solve(Base,1, N, Solution).

% the main predicate

%

sudoku(Base,Constraints, Solution) :-

findall(X/Y/_, (between(1,Base,X), between(1,Base,Y)), Solution),

subset(Constraints, Solution),

solve(Base,Solution).

/*

And some example puzzles to solve:

*/

s3([3/1/3, 2/2/8,

5/1/4, 4/2/6, 6/2/3, 4/3/5,

8/1/9, 8/3/4,

1/4/5, 1/6/2, 3/6/7,

4/4/9, 5/4/1, 4/5/2, 6/5/7, 5/6/8, 6/6/6,

7/4/3, 9/4/7, 9/6/5,

2/7/3, 2/9/5,

4/8/7, 5/9/6, 6/7/5, 6/8/1,

7/9/4, 8/8/5]).

% the sudoku from class

s1([1/4/2, 1/5/3, 1/9/5,

2/2/4, 2/3/2, 2/5/9, 2/9/3,

3/1/3, 3/6/8, 3/7/7,

4/3/7, 4/8/5, 4/9/6,

5/2/9, 5/4/7, 5/5/2, 5/8/1, 5/9/4,

6/1/5, 6/4/9,

7/1/6, 7/6/2, 7/7/8, 7/8/4, 7/9/9,

8/3/8, 8/6/1, 8/9/7,

9/1/2, 9/2/5, 9/6/9, 9/7/6]).

s2([4/1/2, 5/1/3, 9/1/5,

2/2/4, 3/2/2, 5/2/9, 9/2/3,

1/3/3, 6/3/8, 7/3/7,

3/4/7, 8/4/5, 9/4/6,

2/5/9, 4/5/7, 5/5/2, 8/5/1, 9/5/4,

1/6/5, 4/6/9,

1/7/6, 6/7/2, 7/7/8, 8/7/4, 9/7/9,

3/8/8, 6/8/1, 9/8/7,

1/9/2, 2/9/5, 6/9/9, 7/9/6]).

I also wrote print_su/1, a sudoku pretty-printer. It is not very interesting, and I used findall/3 to iterate through a list and print its elements (which may be considered abusive), so I decided not to publish it here :).

Now, we can use Prolog to run the following query:

?- s1(Constraints),sudoku(9,Constraints,Sudoku), print_su(Sudoku).

1 7 3 || 4 8 5 || 6 9 2

8 4 6 || 2 9 1 || 7 3 5

9 2 5 || 7 6 3 || 1 8 4

==============================

2 5 4 || 1 7 9 || 3 6 8

3 9 1 || 8 2 6 || 5 4 7

7 6 8 || 3 5 4 || 2 1 9

==============================

4 1 7 || 9 3 2 || 8 5 6

6 8 9 || 5 1 7 || 4 2 3

5 3 2 || 6 4 8 || 9 7 1

Constraints = [1/4/2, 1/5/3, 1/9/5, 2/2/4, 2/3/2, 2/5/9, 2/9/3, ... /... /3, ... /...|...]

Sudoku = [1/1/1, 1/2/8, 1/3/9, 1/4/2, 1/5/3, 1/6/7, 1/7/4, ... /... /6, ... /...|...]

and voilĂ , your sudoku is ready!

(I think that it may be sensible using constraint logic programming for solving sudoku... However, I haven't reached the chapter about CLP in my book yet, so I didn't use it. ;-))

## 1 comment:

Post a Comment