Sudoku solver evaluation function

So I'm trying to write a simple genetic algorithm for solving a sudoku (not the most efficient way, I know, but it's just to practice evolutionary algorithms). I'm having some problems coming up with an efficient evaluation function to test if the puzzle is solved or not and how many errors there are. My first instin开发者_开发百科ct would be to check if each row and column of the matrix (doing it in octave, which is similar to matlab) have unique elements by ordering them, checking for duplicates and then putting them back the way they were, which seems long winded. Any thoughts?

Sorry if this has been asked before...

Speedups:
Use bitwise operations instead of sorting.

I made 100 line sudoku solver in c it reasonably fast. For or super speed you need to implement DLX algorhitm, there is also some file on matlab exchange for that.
http://en.wikipedia.org/wiki/Exact_cover
http://en.wikipedia.org/wiki/Dancing_Links
http://en.wikipedia.org/wiki/Knuth's_Algorithm_X

#include "stdio.h"
int rec_sudoku(int (&mat)[9][9],int depth)
{
    int sol[9][9][10]; //for eliminating
    if(depth == 0) return 1;
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
        {
            sol[i][j][9]=9;
            for(int k=0;k<9;k++)
            {
                if(mat[i][j]) sol[i][j][k]=0;
                else sol[i][j][k]=1;
            }
        }
    }
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
        {
            if(mat[i][j] == 0) continue;
            for(int k=0;k<9;k++)
            {
                if(sol[i][k][mat[i][j]-1])
                {
                    if(--sol[i][k][9]==0) return 0;
                    sol[i][k][mat[i][j]-1]=0;
                }
                if(sol[k][j][mat[i][j]-1])
                {
                    if(--sol[k][j][9]==0) return 0;
                    sol[k][j][mat[i][j]-1]=0;
                }
            }
            for(int k=(i/3)*3;k<(i/3+1)*3;k++)
            {
                for(int kk=(j/3)*3;kk<(j/3+1)*3;kk++)
                {
                    if(sol[k][kk][mat[i][j]-1])
                    {
                        if(--sol[k][kk][9]==0) return 0;
                        sol[k][kk][mat[i][j]-1]=0;
                    }
                }
            }
        }
    }
    for(int c=1;c<=9;c++)
    {
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(sol[i][j][9] != c) continue;
                for(int k=0;k<9;k++)
                {
                    if(sol[i][j][k] != 1) continue;
                    mat[i][j]=k+1;
                    if(rec_sudoku(mat,depth-1)) return 1;
                    mat[i][j]=0;
                }
                return 0;
            }
        }
    }
    return 0;
}
int main(void)
{
    int matrix[9][9] =
    {
        {1,0,0,0,0,7,0,9,0},
        {0,3,0,0,2,0,0,0,8},
        {0,0,9,6,0,0,5,0,0},
        {0,0,5,3,0,0,9,0,0},
        {0,1,0,0,8,0,0,0,2},
        {6,0,0,0,0,4,0,0,0},
        {3,0,0,0,0,0,0,1,0},
        {0,4,0,0,0,0,0,0,7},
        {0,0,7,0,0,0,3,0,0}
    };
    int d=0;
    for(int i=0;i<9;i++) for(int j=0;j<9;j++) if(matrix[i][j] == 0) d++;
    if(rec_sudoku(matrix,d)==0)
    {
        printf("no solution");
        return 0;
    }
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
        {
            printf("%i ",matrix[i][j]);
        }
        printf("\n");
    }
    return 1;
}

The check is easy, you'll create sets for rows, columns, and 3x3's adding a number if it does not exist and altering your fitness accordingly if it does not.

The real trick however is "altering your fitness" accordingly. Some problems seem well suited to GA and ES (evolution strategies), that is we look for a solution in tolerance, sudoku has an exact answer... tricky.

My first crack would probably be creating solutions with variable length chromosomes (well they could be fixed length but 9x9's with blanks). The fitness function should be able to determine which part of the solution is guaranteed and which part is not (sometimes you must take a guess in the dark in a really tough sudoku game and then back track if it does not work out), it would be a good idea to create children for each possible branch.

This then is a recursive solution. However you could start scanning from different positions on the board. Recombination would combine solutions which combine unverified portions which have overlapping solutions.

Just thinking about it in this high level easy going fashion I can see how mind bending this will be to implement!

Mutation would only be applied when there is more than one path to take, after all a mutation is a kind of guess.

Sounds good, except for the 'putting them back' part. You can just put the numbers from any line, column or square in the puzzle in a list and check for doubles any way you want. If there are doubles, there is an error. If all numbers are unique there's not. You don't need to take the actual numbers out of the puzzle, so there is no need for putting them back either.

Besides, if you're writing a solver, it should not make any invalid move, so this check would not be needed at all.

I would use the grid's numbers as an index, and increment an 9 elements length array's respective element => s_array[x]++ where x is the number taken from the grid. Each and every element must be 1 in the array at the end of checking one row. If 0 occurs somewhere in the array, that line is wrong.

However this is just a simple sanity check if there are no problems, line-wise.

PS: if it were 10 years ago, I would suggest an assembly solution with bit manipulation (1st bit, 2nd bit, 3rd bit, etc. for the values 1,2 or 3) and check if the result is 2^10-1.

When I solved this problem, I just counted the number of duplicates in each row, column and sub-grid (in fact I only had to count duplicates in columns and sub-grids as my evolutionary operators were designed never to introduce duplicates into rows). I just used a HashSet to detect duplicates. There are faster ways but this was quick enough for me.

You can see this visualised in my Java applet (if it's too fast, increase the population size to slow it down). The coloured squares are duplicates. Yellow squares conflict with one other square, orange with two other squares and red with three or more.

Here is my solution. Sudoku solving solution in C++

Here is my solution using set. If for a line, a block or a column you get a set length of (let say) 7, your fitness would be 9 - 7.

1. If you are operating on a small set of integers sorting can be done in O(n) using bucket sorting.

2. You can use tmp arrays to do this task in matlab:

   function tf = checkSubSet( board, sel ) % % given a 9x9 board and a selection (using logical 9x9 sel matrix) % verify that board(sel) has 9 unique elements % % assumptions made: % - board is 9x9 with numbers 1,2,...,9 % - sel has only 9 "true" entries: nnz(sel) = 9 % tmp = zeros(1,9); tmp( board( sel ) ) = 1; % poor man's bucket sorting tf = all( tmp == 1 ) && nnz(sel) == 9 && numel(tmp) == 9; % check validity

Now we can use checkSubSet to verify the board is correct

function isCorrect = checkSudokuBoard( board )
%
% assuming board is 9x9 matrix with entries 1,2,...,9
%

isCorrect = true;
% check rows and columns
for ii = 1:9
    sel = false( 9 );
    sel(:,ii) = true;
    isCorrect = checkSubSet( board, sel );
    if ~isCorrect
        return;
    end
    sel = false( 9 );
    sel( ii, : ) = true;
    isCorrect = checkSubSet( board, sel );
    if ~isCorrect
        return;
    end
end
% check all 3x3 
for ii=1:3:9
    for jj=1:3:9
        sel = false( 9 );
        sel( ii + (0:2) , jj + (0:2) ) = true;
        isCorrect = checkSubSet( board, sel );
        if ~isCorrect
            return;
        end
    end
end