Sudoku, Final Analysis

by Lucio Cetto

When designing the test suite for the Sudoku Contest, we tried to estimate what the best score would ultimately be. This is important for tuning our grading function that weights the score and elapsed time. One of the reasons we use this formula is to make sure the problem is complex enough to last for an entire week. Even so, for this contest it only took one day for entries to outperform our estimate.

Sixty four percent of the problems in our test suite were taken from real Sudoku puzzles. We blurred the numbers and changed their distribution a little. This means that in theory, it was possible to get an almost perfect solution. Of course, we made some other permutations of the boxes to hide the solution, and did our best to make these problems look like the others in the test suite. My intention was to show our contestants some of the perfect solutions during the mid-contest analysis. I was surprised to find that current entries outperformed my 'perfect' solutions after the twilight phase. Later I discovered that my blurring factor was too high. The following figure shows the achieved scores by the winning solution and the estimated scores we incorrectly anticipated. Observe that most of the dots are below the identity line, this means that the solver achieved a score below our estimate. 

load alltestsuites.mat
h = find(~cellfun('isempty',{s{1}.solution}));
bks = [s{1}(h).bestResult]';
r = zeros(64,2);
for i = 1:64
    [G,r(i,1)] = solver_23706(s{1}(h(i)).puzzle,s{1}(h(i)).list);
    [G,r(i,2)] = solver_25905(s{1}(h(i)).puzzle,s{1}(h(i)).list);
end
plot(bks,r(:,1),'b.',bks,r(:,2),'r.',[0 50],[0 50],'k-')
axis([0 60 0 50])
xlabel('Incorrect estimated best score')
ylabel('Solver score')
title('64 puzzles in which we though we knew the best solution')
legend('Darkness winner','Contest winner')

Even though we failed to predict the bounds of the solvers, it is interesting to evaluate the power of our winning entry. Here we test the winning solver with some problems for which we know the solution. First I will try a Sudoku puzzle with integer numbers: 

[Puzzle,Solution] = createintsudoku(3)
[Guess,Score] = solver_25905(Puzzle,Solution(Puzzle==0)')

Puzzle =
     0     0     0     0     0     8     5     0     0
     0     0     5     0     0     0     0     0     8
     0     0     4     0     0     5     0     6     0
     1     6     0     0     7     0     0     0     0
     0     8     0     5     0     0     0     0     9
     0     0     0     0     6     0     7     0     4
     7     0     0     3     0     0     0     0     0
     3     0     0     0     1     6     0     0     0
     0     1     0     0     0     0     2     5     0
Solution =
     6     9     1     7     4     8     5     3     2
     2     3     5     6     9     1     4     7     8
     8     7     4     2     3     5     9     6     1
     1     6     9     8     7     4     3     2     5
     4     8     7     5     2     3     6     1     9
     5     2     3     1     6     9     7     8     4
     7     4     8     3     5     2     1     9     6
     3     5     2     9     1     6     8     4     7
     9     1     6     4     8     7     2     5     3
Guess =
     9     1     9     6     4     8     5     1     2
     4     3     5     3     8     1     6     7     8
     8     2     4     1     9     5     3     6     7
     1     6     5     8     7     3     2     8     5
     3     8     7     5     5     2     4     2     9
     1     8     6     2     6     7     7     4     4
     7     7     2     3     2     4     9     6     5
     3     9     4     8     1     6     7     6     1
     9     1     3     9     3     9     2     5     4
Score =
     0

Observe that the Guess returned by the winning entry rarely returns a value that matches the correct solution, although the local minima in which it was trapped resulted in a small value.

Now, I will try with a blurred problem. This time I have made the blurring factor very small.

[Blurred_Puzzle,list,Blurred_Solution,Best_knwon_score] ...
    = sudokublurring(Puzzle,Solution);
Best_knwon_score = Best_knwon_score
[Guess,Score] = solver_25905(Blurred_Puzzle,sort(list))

Best_knwon_score =
    3.8512
Guess =
   15.9   11.8   59.7   74.3   23.1   98.1   62.3    1.6   94.1
   46.6   97.2   13.0   13.8   61.9    0.1   94.3   39.3   72.9
   83.0   13.8   98.7   95.2   71.9    1.6   16.3   35.1   24.4
   61.6   35.3   76.5   50.8   37.6   27.8    2.8   60.6   86.3
   94.6   19.9   37.3   75.1    1.7   56.9   68.1   71.5   14.4
    0.6   98.8   15.3   23.2   81.9   84.5   37.8   48.0   49.7
   73.6   58.2   50.1   22.1   50.6    0.6   83.7   99.8    1.3
    1.1   82.7   16.9   49.0   85.1   84.4   24.7   36.9   59.4
   62.7   23.8   70.9   35.8   25.9   85.6   49.7   46.8   37.2
Score =
   11.4303

Now I will create 100 problems and see if one of them can be solved by our winning entry:

n = 100;
bks = zeros(n,1);
s = zeros(n,1);
for i = 1:n
    [P,S] = createintsudoku(3);
    [BP,list,BS,bks(i)] = sudokublurring(P,S);
    [G,s(i)] = solver_25905(BP,sort(list));
end

plot(bks,s,'r.',[0 8],[0 8],'k-')
xlabel('Best known score')
ylabel('Solver 25905 score')
title(['Running solver for 100 puzzles ' ...
    'in which we know the best solution')

None of the solutions is close to the our best known score. Usually it scores twice as much.

I believe that solutions to problems like this have some real applications. In biology and bioinformatics, for example, researchers are trying to find hidden machinery with simple, discrete and straightforward relationships, for which one needs to sift through noisy data and an enormous combinatorial quantity of likely solutions. For example: finding the protein and gene interactions for an unknown biological pathway, or finding the most likely phylogenetic reconstruction of a group of species. In our Sudoku problem, we also had a limited number of values that needed to be arranged into a simple system of equations, but trying all possible combinations was computationally inefficient.

Part of the winning solution uses a simulating annealing approach, which is an optimization technique inspired on the annealing of the metals. The technique uses a process of successive updating steps which are regulated by a parameter that plays the role of the temperature; when it is high the updating steps are significant, increasing the chances to jump across different local minimal areas, and when it is low the updated steps are small, improving the stability of the solution.

Before the contest started, I thought that some sort of genetic algorithm would be able to find a good solution. However, later I noticed it might prove difficult since one cannot systematically approach to the minimum of the objective function. I mean that just by changing a pair of boxes, the objective function can change from the correct result to a very poor result. This is probably why the simulating annealing approach is trapped into local minima.


Published with MATLAB® 7.1