1 ## Copyright (C) 2009 Jaroslav Hajek <highegg@gmail.com>
3 ## This program is free software; you can redistribute it and/or modify it under
4 ## the terms of the GNU General Public License as published by the Free Software
5 ## Foundation; either version 3 of the License, or (at your option) any later
8 ## This program is distributed in the hope that it will be useful, but WITHOUT
9 ## ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
10 ## FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
13 ## You should have received a copy of the GNU General Public License along with
14 ## this program; if not, see <http://www.gnu.org/licenses/>.
17 ## @deftypefn{Function File} [@var{x}, @var{ntrial}] = solvesudoku (@var{s})
18 ## Solves a classical 9x9 sudoku. @var{s} should be a 9x9 array with
19 ## numbers from 0:9. 0 indicates empty field.
20 ## Returns the filled table or empty matrix if no solution exists.
21 ## If requested, @var{ntrial} returns the number of trial-and-error steps needed.
24 ## This uses a recursive backtracking technique combined with revealing new singleton
25 ## fields by logic. The beauty of it is that it is completely vectorized.
27 function [x, ntrial] = solvesudoku (s)
33 if (! (ismatrix (s) && ndims (s) == 2 && all (size (s) == [9, 9])))
34 error ("needs a 9x9 matrix");
37 if (! ismember (unique (s(:)), 0:9))
38 error ("matrix must contain values from 0:9");
41 if (! verifysudoku (s))
42 error ("matrix is not a valid sudoku grid");
45 [x, ntrial] = solvesudoku_rec (s);
49 function ok = verifysudoku (s)
52 b(sub2ind ([9, 9, 9], i, j, k)) = true;
53 okc = sum (b, 1) <= 1;
54 okr = sum (b, 2) <= 1;
55 b = reshape (b, [3, 3, 3, 3, 9]);
56 ok3 = sum (sum (b, 1), 3) <= 1;
57 ok = all (okc(:) & okr(:) & ok3(:));
60 function [x, ntrial] = solvesudoku_rec (s)
65 ## Run until the logic is exhausted.
69 x = getsingletons (b, x);
70 finished = isempty (x) || all (x(:));
71 until (finished || all ((x == s)(:)));
75 ## Find the field with minimum possibilities.
78 [msb, i] = min (sb(:));
79 [i, j] = ind2sub ([9, 9], i);
81 for k = find (b(i,j,:))'
83 [x, ntrial1] = solvesudoku_rec (s);
84 ntrial += 1 + ntrial1;
95 ## Given a 9x9x9 logical array of allowed values, get the logical singletons.
96 function s = getsingletons (b, s)
100 ## Check for fields with only one option.
102 if (any (sb(:) == 0))
107 ## We want to return as soon as some new singletons are found.
108 [s(s1), xx] = find (reshape (b, [], 9)(s1, :).');
109 if (sum (s(:) != 0) > n0)
114 ## Check for columns where a number has only one field left.
115 sb = squeeze (sum (b, 1));
116 if (any (sb(:) == 0))
122 [i, xx] = find (b(:, s1));
123 s(sub2ind ([9, 9], i, j)) = k;
124 if (sum (s(:) != 0) > n0)
130 sb = squeeze (sum (b, 2));
131 if (any (sb(:) == 0))
137 [j, xx] = find (permute (b, [2, 1, 3])(:, s1));
138 s(sub2ind ([9, 9], i, j)) = k;
139 if (sum (s(:) != 0) > n0)
145 bb = reshape (b, [3, 3, 3, 3, 9]);
146 sb = squeeze (sum (sum (bb, 1), 3));
147 if (any (sb(:) == 0))
151 s1 = reshape (sb == 1, 9, 9);
153 [i, xx] = find (reshape (permute (bb, [1, 3, 2, 4, 5]), 9, 9*9)(:, s1));
154 [i1, i2] = ind2sub ([3, 3], i);
155 [j1, j2] = ind2sub ([3, 3], j);
156 s(sub2ind ([3, 3, 3, 3], i1, j1, i2, j2)) = k;
157 if (sum (s(:) != 0) > n0)
164 ## Given known values (singletons), calculate options.
165 function b = getoptions (s)
168 [i, j, s] = find (s);
171 bc(:, sub2ind ([9, 9], j, s)) = false;
174 br(:, sub2ind ([9, 9], i, s)) = false;
176 b3 = true (3, 3, 3, 3, 9);
177 b3(:, :, sub2ind ([3, 3, 9], ceil (i/3), ceil (j/3), s)) = false;
178 ## Permute elements to correct order.
179 br = permute (br, [2, 1, 3]);
180 b3 = reshape (permute (b3, [1, 3, 2, 4, 5]), [9, 9, 9]);
181 ## The singleton fields themselves.
183 bb(sub2ind ([9, 9], i, j), :) = false;
184 bb = reshape (bb, [9, 9, 9]);
186 b = bc & br & b3 & bb;
187 ## Correct singleton fields.
188 b = reshape (b, 9, 9, 9);
189 b(sub2ind ([9, 9, 9], i, j, s)) = true;