A Sudoku Image Recognition Program                                                

Newspaper image capture

It is amazing to me, that the eye can recognize objects so quickly and apparently so easily. I suspect that a significant amount of parallel processing occurs locally in the eye that helps with edge and surface detection. The conscious brain is usually not even aware of what must be the huge amount of computing to make sense of the morning newspaper. I get a glimpse of the enormity of the problem when I open one of those multi language instruction booklets and it takes me a few moments to realize that I’m trying to read German.

A computer is far worse off because the only thing it “knows” is what is going on at a single given pixel. In one image there are a lot of pixels (640x480=307,200) and as the “attention” moves to the next pixel, it forgets what it had just seen. I write algorithms for computers as if I were making instructions for someone with extreme tunnel vision who has little ability to make long term memories.

Gray-scale conversion

But first I must capture a USB camera bitmaped image in the computer. Some kind soul, made this relatively easy in VB6, by writing a short module that utilizes the SendMessage command of the USER32 API. Download at: USBCammod.bas

Then by using simple commands, the USB cam is turned on and images are continuously sent to the windows clipboard. The clipboard data is constantly copied to a VB6 picturebox and you see a live video image in the form’s picturebox. Still images are captured from the clipboard in the same way.

  

mCapHwnd = capCreateCaptureWindow("WebcamCapture", 0, 0, 0, 640, 480, H, 0)

 DoEvents

 SendMessage mCapHwnd, CONNECT, 0, 0

 CamRunning = True

 Do While CamRunning

     SendMessage mCapHwnd, GET_FRAME, 0, 0

     SendMessage mCapHwnd, COPY, 0, 0

     PIC.Picture = Clipboard.GetData

     DoEvents

 Loop

Monochromatic image

A bitmapped color image can be converted to a gray-scale image by averaging each RGB pixel value and then writing the average back into each of the RGB pixel locations. A RGB color value of (10, 9, 2) is converted to gray- scale value of (7, 7, 7). Gray-scale images can be converted into two toned (monochromatic) images by comparing to a cutoff value. Gray-scale values above the cutoff produce white points and values below the cutoff are black points.

Background cutoff values

The trick of making a decent monochrome image is to find where  to set the cutoff. The cutoff needs to be set to unique values in different areas of an image. I used an algorithm that looked at local blocks of 96x96 pixels that found the gray-scale distribution. The highest distribution peek of a newsprint image is always the white background color. I defined the local cutoff value to be the first low (1/4 peek value) distribution area on the dark side of the peek. So now, the gray-scale values of the image are graded against the local cutoff and a strong monochromatic image is produced. I also copy these monochromatic values into a 640x480 byte array because VB6 can do calculations on array data faster than it can draw or read pixel values from an image.

So starting with a monochromatic image of a newspaper, I need to identify the Sudoku grid and determine the beginning values. Here is the algorithm that I used:

Detection of horizontal & vertical lines

    1.    Look for relatively horizontal and vertical lines in the image and overwrite the monochromatic image with these red lines. It  is relatively easy to look at the points along possible lines and grade how many black points are intercepted. If the number of black points passes a threshold, then draw the line.

Cleaned up image

    2.    Cleanup the image by removing all red pixels that had not overwritten monochromatic black.

Flood-fill with yellow

    3.    Starting from the image edges, flood-fill all white or black pixels with the color yellow. The yellow flood does not cross the solid red lined boarder of the Sudoku grid and leaves it’s interior cells white with black numbers.

    4.    Record the coordinates of the four corners of the Sudoku grid by detecting the first white pixels found, while working diagonally inward from the image corners. I had to made a test that eliminated corner detection false alarms (small islands of white in the sea of yellow).

Corner detection & parsing

    5.    Using the four Sudoku corner coordinates, calculate the coordinates of all 81 cell corners (marked by blue dots).

    6.    Parse each Sudoku cell by grading the number of pixels that match an idealized cartoon of the numbers 1 to 9 and a blank. The cartoon image corners are stretched to match up with each of the Sudoku cell corners. The cartoon is then jiggled around a bit, left & right, up & down, to find the best fit to the monochrome image. The highest scoring cartoon should be the correct cell value. Draw in the cell value (overwrites in red).

Puzzle solved

    7.    Solve the puzzle by repeatedly applying the LookForSingles and the LookForPairs algorithms. Draw in the cell value.

    8.    Write the solution and cell coordinates to a text file stored on the hard drive. (To be used in a future project)

The program is long, gangly and uses 50% of the CPU power for 37 seconds to visual recognize a Sudoku puzzle and parse the starting numbers. The puzzle solving part  takes less than a second. I include here, a captured screen video of the program running. The video capture software heavily uses the CPU and slows the Sudoku recognition considerably. In the video, it takes 108 seconds to identify and solve the puzzle.

Sudoku Solving Program                                                                          

Newspaper Sudoku

Well I got so discussed with the Stirling engine project that my mind started looking for diversions and, before I knew it, I was writing another image recognition program.

Sudoku solving program

A couple of years ago, I wrote a Sudoku VB6 program where I could enter the starting numbers into a 9x9 grid and the computer would fill in the remaining blank cells with the solution. I used the program to find out where I went wrong when I made a mistake doing a Sudoku, so I could back track and finish the puzzle. When writing the program, I realized right away that using a brute–force approach of looking for all possible puzzle number combinations was not going to work, due to the very high number of possibilities (Wiki says 6.67×10²¹⁾. In the program, I used the same algorithms that I apply when solving a puzzle.  I am not sure if all puzzles can be completely solved by these two algorithms but the program routinely solves the daily puzzles from the newspaper in a few tenths of a second.

Sudoku single

The Look-For-Singles algorithm finds what I call give-away-cells; cells that could only be filled by a single number.  Say a row contained the numbers 12345678. The empty cell could only be a nine. The way the algorithm detects this cell is by first filling all 81 cells of a grid with the string “123456789”,  then as each new answer is entered in the grid, that digit is removed from each cell string in that row, in that column and in that block. If any of the resulting cell strings diminish to the length of one character then a new result has been found.

Another Sudoku single

 In addition, any row, column or block that contains only one instance of a number, is also a solution. These processes are repeated until no new results are found. Newspaper Sudoku puzzles with one, two or three star difficulty ratings can usually be solved using this algorithm alone.

Sudoku Pair

If the Singles algorithm leaves some cells unsolved then the Look-For-Pairs algorithm is used. It looks for pairs of cells where the same two numbers are only possible in each. Say the top row contained the numbers BBB4567BB (B = a blank cell) and the top left block also contained the numbers 8 & 9. Each of the two empty cells at the end of the top row could only contain an eight or a nine. You still don't know which of those two cells contains the 8 & 9, but you can eliminate all other possible solutions. When the other solutions are eliminated from paired cells, it sometimes leaves adjacent rows, columns or blocks with new single solutions that the Look-For-Singles algorithm can find. 

So these two algorithms are repeatedly run until no additional answers are found. Newspaper Sudoku puzzles with four or five star difficulty ratings can usually be solved using one to three passes of these algorithms.

When I find that I’ve gone wrong solving a Sudoku puzzle, I get pretty irritated. Then I go to the puzzle solver program and get even more irritated tediously entering the 20 to 30 starting  numbers to find I’ve made a mistake doing that too. I kept thinking that the damn computer should be able to read the damn puzzle and solve it. So I wrote a program to do just that!