A Faster Sudoku Solver

This code requires the Exact Cover package. It is slightly faster, but requires much more memory than Sudoku Solver.

/*
A Sudoku puzzle consists of a 9x9 matrix divided into nine 3x3 submatrices.
Some cells have already been allocated numbers, and empty cells are
represented by 0.  These empty cells have to be replaced by numbers between
1 and 9 in such a way that each row, column and submatrix contains each of
the numbers 1 to 9 exactly once.

e.g. go([0,0,0, 0,0,0, 0,0,1,
         4,0,0, 5,0,0, 0,2,0,
         2,0,0, 4,0,0, 6,0,0,

         0,0,5, 6,4,0, 0,0,0,
         9,0,0, 0,0,0, 0,0,8,
         0,0,0, 0,7,1, 3,0,0,

         0,0,1, 0,0,6, 0,0,9,
         0,6,0, 0,0,3, 0,0,5,
         8,0,0, 0,0,0, 0,0,0], X) gives

    X = [3,7,9, 8,6,2, 5,4,1,
         4,1,6, 5,3,9, 8,2,7,
         2,5,8, 4,1,7, 6,9,3,

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

         5,2,1, 7,8,6, 4,3,9,
         7,6,4, 1,9,3, 2,8,5,
         8,9,3, 2,5,4, 7,1,6]
*/

% Executing this goal will display all solutions to the given problem.
sudoku:-
  go([0,0,0,0,0,0,0,0,1,4,0,0,5,0,0,0,2,0,2,0,0,4,0,0,6,0,0,
      0,0,5,6,4,0,0,0,0,9,0,0,0,0,0,0,0,8,0,0,0,0,7,1,3,0,0,
      0,0,1,0,0,6,0,0,9,0,6,0,0,0,3,0,0,5,8,0,0,0,0,0,0,0,0]).

% All solutions are displayed.
go(Problem):-
  length(Problem, N4),
  N is sqrt(sqrt(N4)),
  go(Problem, Solution),
  show(Solution, 1, N),
  fail.
go(_).  

% All solutions are found on backtracking.
% e.g. go([0,0,2,4,0,0,0,0,0,0,0,0,3,2,0,0], X) gives
%       X=[1,3,2,4,2,4,1,3,4,1,3,2,3,2,4,1]
% e.g. go([0,0,0,0,0,0,0,2,4,0,0,0,0,1,0,3], X)
%       X=[1,2,3,4,3,4,1,2,4,3,2,1,2,1,4,3]
%   and X=[3,2,1,4,1,4,3,2,4,3,2,1,2,1,4,3]
go(Problem, Solution):-
  length(Problem, N4),
  N2 is sqrt(N4),
  N4 =:= N2*N2,
  N is sqrt(N2),
  N =< 3,
  N2 =:= N*N, % The length of the input is a perfect fourth power
  init_values(Problem, 0, N2, Gss),
  findall(X, sudoku_1(N2, N4, X), Set),       % The column headers
  findall(Ys, sudoku_2(N, Gss, Ys), Subsets), % The rows
  excov(Set, Subsets, Cover),
  sort(Cover, Cover1),
  sudoku_4(Cover1, N2, Solution).

% Generates a column header.  On backtracking, generates all column headers.
sudoku_1(N2, _,  H):-for(1, N2, R), for(1, N2, C), H is N2*(R-1)+C-1.
sudoku_1(N2, N4, H):-for(1, N2, V), for(1, N2, R), H is N4+N2*(V-1)+R-1.
sudoku_1(N2, N4, H):-for(1, N2, V), for(1, N2, C), H is 2*N4+N2*(V-1)+C-1.
sudoku_1(N2, N4, H):-for(1, N2, V), for(1, N2, B), H is 3*N4+N2*(V-1)+B-1.

% Generates the rows for one cell.  On backtracking generates the rows for
%   all cells.
sudoku_2(N, Gss, Ys):-
  N2 is N*N,
  for(1, N2, R),
  RowB is (R-1) // N,
  for(1, N2, C),
  ColB is (C-1) // N,
  B is N*RowB+ColB+1,
  N4 is N2 * N2,
  sudoku_3(Gss, N2, N4, R, C, B, Ys).

% Generates one row for a given value in a cell, or N^2 rows for an empty cell
sudoku_3(Gss, N2, N4, R, C, B, [RC,VR,VC,VB]):-
  member([R,C,V], Gss), !,
  RC is N2*(R-1)+C-1,
  VR is N4+N2*(V-1)+R-1,
  VC is 2*N4+N2*(V-1)+C-1,
  VB is 3*N4+N2*(V-1)+B-1.
sudoku_3(_, N2, N4, R, C, B, [RC,VR,VC,VB]):-
  for(1, N2, V),
  RC is N2*(R-1)+C-1,
  VR is N4+N2*(V-1)+R-1,
  VC is 2*N4+N2*(V-1)+C-1,
  VB is 3*N4+N2*(V-1)+B-1.

% Extracts the solution
sudoku_4([], _, []).
sudoku_4([[_,VR|_]|Zss], N2, [X|Xs]):-
  X is ((VR - N2*N2) // N2) + 1,
  sudoku_4(Zss, N2, Xs).

% Extracts the positions and values of the given data
% e.g. init_values([0,0,2,4,0,0,0,0,0,0,0,0,3,2,0,0], 0, 4, X)
%   gives X=[[1,3,2],[1,4,4],[4,1,3],[4,2,2]]
init_values([], _, _, []).
init_values([0|Vs], X, N2, VVs):-!,
  X1 is X + 1,
  init_values(Vs, X1, N2, VVs).
init_values([V|Vs], X, N2, [[R,C,V]|VVs]):-
  R is (X // N2)+1,
  C is (X mod N2)+1,
  X1 is X + 1,
  init_values(Vs, X1, N2, VVs).

% Displays formatted output
show([], _, _):-!, 
  nl.
show([X|Xs], I, N):-
  I mod (N * N * N) =:= 0, !,
  write(X), nl, nl,     % Horizontal gap
  I1 is I + 1,
  show(Xs, I1, N).
show([X|Xs], I, N):-
  I mod (N * N) =:= 0, !,
  write(X), nl,         % End of line
  I1 is I + 1,
  show(Xs, I1, N).
show([X|Xs], I, N):-
  I mod N =:= 0, !,
  write(X), write(' '), % Vertical gap
  I1 is I + 1,
  show(Xs, I1, N).
show([X|Xs], I, N):-
  write(X),
  I1 is I + 1,
  show(Xs, I1, N).
  
/* length(Xs, L) is true if L is the number of elements in the list Xs.      */
%length(Xs, L):-length_1(Xs, 0, L).

/* length_1(Xs, L0, L) is true if L is equal to L0 plus the number of        */
/*   elements in the list Xs.                                                */
%length_1([], L, L).
%length_1([_|Xs], L0, L):-L1 is L0 + 1, length_1(Xs, L1, L).

/* member(X, Xs) is true if the element X is contained in the list Xs.       */
%member(X, [X|_]).
%member(X, [_|Xs]):-member(X, Xs).

LPA Index     Home Page

Valid HTML 4.0!