Seeing and believing: Designing an algorithm

I had always been interested in solving sudoku puzzles, partly because there are too many combinations that make each Sudoku unique. Since my work involves writing and using programming in different scenarios, I thought why not try using my skills on Sudoku. So there I was on a London Underground train to Barbican - looking at a Sudoku puzzle at the back of a morning newspaper, wondering how I can write an algorithm to solve it. I figured out a few simple tricks that I have always used in algorithm design. Here I explain what thoughts I had while designing my very own Sudoku solver and how I transformed those ideas into a working prototype.

First of all lets have a look at a typical Sudoku puzzle and some basic rules:

Sudoku Puzzle

Yes - it has got everything to do with numbers!! lots of numbers!

A Sudoku puzzle typically has 81 boxes where each box can have a number between 1 to 9. However, all these boxes follow some rules that make it all interesting. You may have noticed 3x3 squares grouping the number boxes. A correct solution of Sudoku ensures no repetition of numbers from 1 to 9 inside each of the 3x3 squares, in each horizontal line and each vertical line. When solving a Sudoku puzzle, this is exactly where I look for a solution, and exactly where my thought process starts for my Sudoku solver algorithm.

I formed a set of rules that my algorithm should follow to look for possible solutions. I explain each rule with the thought process.

Rule # 1 - Boxes in a Square

Sudoku 3x3 Square

In a typical Sudoku puzzle some number boxes are already filled in to give the solver some clues. Looking at a 3x3 square we know that it must contain the number 1 to 9 without repetition.

Rule # 2 - Horizontal Lines

Sudoku Horizontal Line

Similar to 3x3 Squares, a horizontal line in a Sudoku puzzle has some clues - where the numbers from 1 to 9 appear without repetition.

Rule # 3 - Vertical Lines

Sudoku Vertical Line

Boxes in vertical line also contain number from 1 to 9 - without repetition. This along with the previous two rules provides the key for the algorithm design.

Notice each of the above rules are clear, concise and can be easily translated into simple algorithm. Can you check what numbers are missing in a line? or a square? Yes - and there could be a number of ways to approach this..

The algorithm

The code I wrote uses the above three rules directly to look for possible solutions within a Sudoku puzzle. Of course, as every algorithm, my Sudoku solver comes with its own limitations. It assumes that at a given stage application of rules 1, 2 and 3 will always result in one or more than one solvable number box(es).

Sudoku Solver working for a given unsolved box

For a given unsolved box, the proposed algorithm applies rule 1, 2 and 3 to collect the available clues. After which, a solution occurs only if there is just one number between 1 to 9 that remains unassigned. The algorithm iterates a few times with this algorithm and thats it!! It essentially does exactly what a typical Sudoku solving person would do - which is fascinating and extremely simple to transform into a working code.

Hashmaps to the rescue

To check for a possible solution I use my own version of hashmaps - this significantly makes the code easier. Instead of collecting all the clues in the three rules - I simply use a hashmap that maps the numbers from 1 to 9 onto a binary array indexed from 1 to 9. For solving each box, this binary hashmap array is first set to zeros - then with each clue the corresponding index mapping in the binary hashmap is set to 1. When all rules have been applied I then take the sum of hashmap - if it is equal to 8 - I have a solution!

Consider if we are looking for a possible solution at the following location

Initially the binary hashmap would be empty

While after application of three rules - it would represent the possible solution(s) - where the mapping of each clue is direct index in the hashmap and the given clues present are set to 1 - while all 0(s) represent the possible solution(s)

The awesome code

Now lets have a look at the code it self:

close all
clear all
clc


% sudoku solver v 1
%% DATA Input
sudokuSolved = [ 5 3 4 6 7 8 9 1 2;
                6 7 2 1 9 5 3 4 8;
                1 9 8 3 4 2 5 6 7;
                8 5 9 7 6 1 4 2 3;
                4 2 6 8 5 3 7 9 1;
                7 1 3 9 2 4 8 5 6;
                9 6 1 5 3 7 2 8 4;
                2 8 7 4 1 9 6 3 5;
                3 4 5 2 8 6 1 7 9];


            
sudokuUnknownValues = [ 0 0 1 1 0 1 1 1 1;
                        0 1 1 0 0 0 1 1 1;
                        1 0 0 1 1 1 1 0 1;
                        0 1 1 1 0 1 1 1 0;
                        0 1 1 0 1 0 1 1 0;
                        0 1 1 1 0 1 1 1 0;
                        1 0 1 1 1 1 0 0 1;
                        1 1 1 0 0 0 1 1 0;
                        1 1 1 1 0 1 1 0 0];
                    
sudokuUnsolved = sudokuSolved .* (~sudokuUnknownValues);
%%
while(sum(sum(sudokuUnsolved)) ~=405)
for i = 1:size(sudokuUnsolved, 2)
    for j = 1:size(sudokuUnsolved,1)
        if(sudokuUnsolved(j, i)==0)
            % if unknown value then perform three checks
            curSolve = zeros(1,9);
            
            % check col
            cCol = sudokuUnsolved(:,i)';
            for c = 1:9
                if(cCol(c) ~= 0)
                    curSolve(cCol(c)) = 1;
                end
            end
            
            % check row
            cRow = sudokuUnsolved(j,:);
            for r = 1:9
                if(cRow(r) ~= 0)
                    curSolve(cRow(r)) = 1;
                end
            end
            
            % check square
            
            cRow = 1+ floor((j-1)/3)*3;
            cCol = 1+ floor((i-1)/3)*3;
            
            for cR = cRow:cRow+2
                for cC = cCol:cCol+2
                    if(sudokuUnsolved(cR, cC) ~= 0)
                        curSolve(sudokuUnsolved(cR, cC)) =1;
                    end
                end
            end
            
            solvedVal = 0;
            if(sum(curSolve) == 8)
                for cC = 1:9
                    if(curSolve(cC) == 0)
                        solvedVal = cC;
                    end
                end
            end
            sudokuUnsolved(j,i) = solvedVal;
        end       
    end
end

sudokuUnsolved

end

and the solution of the above sudoku puzzle:

sudokuUnsolved =

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

sudokuUnsolved =

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

sudokuUnsolved =

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

sudokuUnsolved =

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

sudokuUnsolved =

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

>>

Which we can compare to the actual solution -

Sudoku Example Solution - source Wikipedia

Now the next step is to make a simple character recognition interface that enables a mobile device to automatically look at a puzzle and give solution in real-time.

Source:
Wikipedia Sudoku Page: https://en.wikipedia.org/wiki/Sudoku

Seeing and believing

Pages

Monday, 28 March 2016

Designing an algorithm - from ideas to code