Step 9 : Play and solve the Sudoku

It is really amazing how it is simple to write a program to find one solution or all the solutions of a Sudoku. Here is the pseudo-code to do it :

Function Find_all_solutions (The_Sudoku)

    look for the first empty square in The_sudoku
    if there is no empty square
          you found a solution
          you can now show, store or print The_Sudoku
    else
          for i = 1 to 9
                if you can place i in the empty square of The_Sudoku
                      place i in the empty square
                      call Find_all_solutions(The_Sudoku)
                      place 0 in the empty square

End of Find_all_solutions

You just have to translate this pseudo-code in Java and it works!

But, this code is not the most performant one. We can improve it a lot, particularly with Dancing Links, or DLX, which is a technique suggested by  the famous Donald Knuth. Here are some very interesting resources concerning this technique :

Dancing links
Knuth's Algorithm X
Exact Cover Matrix

Of course, we implemented this excellent technique in our application.

So, now, you just have to play with your Sudoku. But sometimes, the Sudoku is quite hard. Of course, our application can give one solution. And our application can even  say if they are many solutions. But, asking for the solution does not help to know how to solve a Sudoku. So, why not ask just for a hint? If you do, our application will give you the next number it would play. At this point, you can have one of these reactions :

1. Yes, or course; why did not I find this number myself?
2. Why is this number suggested by the application? You check the Sudoku a little bit more and you get it! Now, you learn rapidly to solve a Sudoku
3. I do not know why the application suggests this number but, at least, I can continue

Here is the screen shown when you press the Hint button. Just try it! You will understand it very fast :

What technique do we use to suggest a number when asked to give a hint, for the lines for example? Very simple . . . as usual! We use the function Find_all_solutions  not for all the Sudoku but rather for just the first line; after, for all the solutions found in the first line, we verify if a number is always in the same square; if yes, we suggest this number. If not, we verify the line 2 up to the line 9. If we do not find any number always in the same square, we  say we do not have any clue for the lines.

You want a hint for the columns? Just press the Columns button. And so on.

Enjoy and amusez-vous bien!

Note : You can store the current Sudoku. It is stored in the external storage in the directory named com.rogerlebo.sudokuvision. Of course, you can  also retrieve a Sudoku you stored previously.

Step 8 : Give the numbers

We return the numbers of the Sudoku captured with this very simple Java code :

Uri data = Uri.parse(sudoku_capture);

Intent result = new Intent(null, data);

setResult(RESULT_OK, result);

finish();

Display :

In this step, all the photos give the same result. Below, you can see the final result with 3 different Android phones.

Here are some observations concerning the images :

• the application can be in English or in French depending on which language you set for your phone
• the taller is the height of the phone screen, the more you see new or taller buttons; the same functions of the buttons missing in the first image can be obtained with the menu button

Step 7 : Show numbers on the photo

Process to find grid and numbers


All the numbers are found now. We just have to display.

Display

So, now, we just want to display the numbers on the original photo. The challenge is to give the original perspective to the numbers found and to apply this perspective on the photo. To do that, we use this time the miraculous setPolyToPoly of Matrix class. But, at first, it is not very easy to understand. It took me a lot of time to use the class correctly.That is why we present the exact Java code of our program.

Here are some variables already set :

bitmap : the original 512X512 photo
sudoku_dim : the dimension of the square grid extracted (sudoku_dim = width = height)
(x1,y1), (x2,y2), (x3,y3), (x4,y4) : the coordinates of the 4 corners of the grid in the original photo
sudoku_capture : the 81 numbers recognized (a empty square is represented by a blank)

Here is the complete code :

Bitmap bitmap_to_display = bitmap.copy(Bitmap.Config.RGB_565, true);

    

float orig [] = new float [] {

            0, 0,

            sudoku_dim, 0,

            sudoku_dim, sudoku_dim,

            0, sudoku_dim

            };        

float dest [] = new float [] {

            (float) x1, (float) y1,

            (float) x2, (float) y2,

            (float) x3, (float) y3,

            (float) x4, (float) y4

            };

Matrix matrice = new Matrix();

matrice.setPolyToPoly(orig, 0, dest, 0, 4);

       

Canvas canvas;                  

canvas = new Canvas(bitmap_to_display);

canvas.setMatrix(matrice);

       

int width_square, height_square;                       

width_square = sudoku_dim / 9;

height_square = width_square;

                 

Paint paint_chiffre = new Paint();

paint_chiffre.setTextSize(34);

paint_chiffre.setTypeface(Typeface.DEFAULT_BOLD);

paint_chiffre.setColor(Color.GREEN);

     

String le_nombre;

int iimage, jimage;

int deb_x_square, deb_y_square;

int idx = -1;

for (iimage = 0; iimage < 9; iimage++) {

      deb_y_square = iimage * height_square + 12 + iimage * 2 / 3 ;

      for (jimage = 0; jimage < 9 ; jimage++){

        deb_x_square = jimage * width_square + 2 + jimage / 3; 

        idx++;           

        le_nombre = sudoku_capture.substring(idx,idx + 1);

        if (!le_nombre.equals(" "))

            canvas.drawText(le_nombre,

                        deb_x_square + 8, deb_y_square + 18,
                        paint_chiffre);                         

      }

}

image.setImageBitmap(bitmap_to_display);

And it works!

To show the numbers at any any angle from 0° to 360°, we have to change the points (x,y) accordingly.

In the screen shots of the same photos, we now see the numbers with the right perspective  :

Step 6 : Find numbers and show them on the grid

Process to find grid and numbers

We found the grid and this grid is now square. The objective of step 6 is to find the numbers. They are 3 steps to do this :

1. find the 81 squares
2. find and isolate the number in a square
3. recognize the number in a square

As we have the coordinates of the 4 corners, it is now quite simple to calculate the coordinates of the 81 squares of the Sudoku. We just have to divide the width by 9 and the height by 9.

To find and isolate the number in a square, we use 2 techniques :

1. remove isolated pixel (it is what we call pac-man transformation)
2. famous flood fill

The pac-man transformation comes from the old Pac-Man game. In the square, we first remove all the isolated 1 sticked at a region. And with the useful flood fill technique, we find the largest region which is, by the way, the number. Here is an example for the number 8  :

To recognize the number, there area huge number of techniques. We tested many of them. One we have not yet tested is neural network. We will probably use it in a next version of our application. For now, we use our own technique based on the shape of the number.  And the technique is based again on the fabulous floodfill algorithm.

So, to recognize the number, we still apply the same useful flood fill technique like this:

• flood fill upper left region with 2
• flood fill  lower left region with 3
• flood fill  upper right region with 4
• flood fill  lower right region with 5
• flood fill  all the others regions (holes) with 6 and over
• do not flood fill the first line, the last line, the first column and the last column

We obtain this for the number 8 :

Next, we define a threshold which depends on the height of the number. When :

• the largest region in the upper left < threshold
• the largest region in the lower left < threshold
• the largest region in the upper right < threshold
• the largest region in the lower right < threshold
• the next largest region in the upper part of the number >= threshold
• the next largest region in the lower part of the number >= threshold

we recognize the number 8.

Here is another example. When :

• the largest region in the upper left < threshold
• the largest region in the lower left >= threshold
• the largest region in the upper right >= threshold
• the largest region in the lower right < threshold

we recognize the number 5.

Here are some characteristics of our technique :

1. it is very easy to understand
2. it is very simple to program
3. it is very fast
4. it is almost completly independent of the usual font used in Sudoku grid (we choose a different font for each photo presented below)
5. the recognition rate is quite good

But, we think the recognition rate of the neural network algorithm is probably better. We will test it in a next version.

Now, what do we do to find numbers at any angle from 0° to 360°? Here is the pseudo-code :

Find numbers

If there is 0 number

                Rotate 90°

                Find numbers

                If there are duplicate numbers in lines, columns or grids 3X3

                               Rotate 270°

                               Find numbers

                               If number of duplicate numbers at 90° < number of duplicate numbers at 270°

                                               Give numbers at 90°

                               Else

                                               Give numbers at 270°

                Else

                               Give numbers at 90°

Else

If there are duplicate numbers in lines, columns or grids 3X3

                Rotate 180°

                Find numbers

                If number of duplicate numbers at 0° < number of duplicate numbers at 180°

                               Give number at 0°
                Else

                               Give numbers at 180°

                Else

                               Give numbers at 0°

It is that simple!

By the way, all numbers and letters have normally a height larger than the width. When we find a number where the width is larger than the height, we consider it is not a number. That is why we can have the condition "If there is 0 number".

  

Display

As you certainly remember, we started a thread in step 1 to find the grid and the numbers. So, before we display the next screen, we have to wait for the thread to be finished.

In the screen shots of the same photos, we now see the numbers :

There are 2 steps for demo 5 :

There are 3 steps for demo 6; in step 1, we find 0 number :

Step 5 : Perspective transformation

Process to find grid and numbers

Often, the grid is distorted and it is almost impossible to find numbers if the grid is not square. We need a way to map a distorted grid to a square grid. The miraculous way is to use perspective transformation also called projective mapping or 2D mapping. So, we want to transform the surrounded green grid at left toward the grid at right :

To use perspective transformation, there is a method named setPolyToPoly in Android Matrix class. But, sometimes, part of the corners of the grid are lost and, consequently, some numbers can be lost. So,  we decided to write our own pure Java code to do the perspective transformation.

But, where can we find all the information we needed to do that? For sure, now, you know the answer . . . in the Burger and Burge's marvellous book . . . of course. This is very clearly explained in chapter 16 page 380. It is named projective mapping in the book. As usual, you could find Java code here :

Chapter 16 Geometric Operations

You can find also a piece of Java code below.

Display

In the screen shots of the same 4 photos, we see the perspective transformations. Note the fourth one where we did not have the 4 corners in the original photo :

Java code

Here are the elements presented :

1. The image to analyze

2. A sample of source image in Excel : image1

3. A sample of target image in Excel : image2

4. Global variables to set before calling the perspective transformation function

5. Perspective transformation function not optimized but running fine

6. Perspective transformation function optimized and running fine

7. How to log image1 and image2 and import them in Excel

I hope it helps!

      

      

1. The image to analyze

2. A sample of source image in Excel : image1

3. A sample of target image in Excel : image2 

      

4. Global variables to set before calling the perspective transformation function

// SOURCE * * * * :          

// image1 : source image

// largueur : width  always set to 512 for my application

// hauteur : height always set to 512 for my application

// (x1p,y1p), (x2p,y2p), (x3p,y3p), (x4p,y4p) :

//              the coordinates of the 4 corners of the grid in the source image

// for the example image :

// x1p = -3.0, y1p = 157.0, x2p = 431.0, y2p = 49.0, x3p = 488.0, y3p = 450.0, x4p = 97.0, y4p = 505.0

// each cell contains 0 (black) or 1 (white)

// TARGET * * * * :

// image2 : target image

// sudoku_dim : width and height always set to 486 for my application

// each cell contains 0 (black) or 1 (white)

// SOURCE * * * * :

int largueur = 512;

int hauteur = 512;

short image1[][] = new short [hauteur][largueur]; // to set

double x1p, x2p, x3p, x4p, y1p, y2p, y3p, y4p; // to set

// TARGET * * * * :

int sudoku_dim = 486;

short image2[][] = new short [sudoku_dim][sudoku_dim];

5. Perspective transformation function not optimized but running fine

public void travaille_5_perspective_transformer_not_optimized() {

      

// There are many multiplications in the loop

// Average response time after many runs of 100 calls :

// 0,06 second on Samsung Galaxy S III : Dual core, 1500 MHz, Snapdragon S4 Krait, 2048 MB RAM with Android 4.0.4

// 0,21 second on Google Nexus S with Android 4.1.1

// 0,12 second on Google Nexus One with Android 2.3.4

      

       int x, y; // x, y on page 380

       int xp, yp; // x prime, y prime on page 380

        

       double a11, a12, a13, a21, a22, a23, a31, a32, a33; // on page 383

     

       // formula 16.28 on page 383

       a31 = ((x1p-x2p+x3p-x4p)*(y4p-y3p)-(y1p-y2p+y3p-y4p)*(x4p-x3p))/((x2p-x3p)*(y4p-y3p)-(x4p-x3p)*(y2p-y3p));

    

       // formula 16.29 on page 383

       a32 = ((y1p-y2p+y3p-y4p)*(x2p-x3p)-(x1p-x2p+x3p-x4p)*(y2p-y3p))/((x2p-x3p)*(y4p-y3p)-(x4p-x3p)*(y2p-y3p));

    

       // formula 16.17 on page 380

       a33 = 1;

    

       // formula 16.30 on page 383

       a11 = x2p-x1p+a31*x2p;

       a12 = x4p-x1p+a32*x4p;

       a13 = x1p;

    

       // formula 16.31 on page 383

       a21 = y2p-y1p+a31*y2p;

       a22 = y4p-y1p+a32*y4p;

       a23 = y1p;

       // Projective mapping via the unit square on page 382 : unit square to image2 dimension

       a31 = a31 / sudoku_dim;

       a32 = a32 / sudoku_dim;

       a11 = a11 / sudoku_dim;

       a12 = a12 / sudoku_dim;

       a21 = a21 / sudoku_dim;

       a22 = a22 / sudoku_dim;

        

       // for each point (x, y) in image2,

       //      we calculate (xp, yp) in image1 using formula 16.18 and 16.19 on page 380

       // the formulas are the ones presented in the book

           

       for (y = 0; y < sudoku_dim; y++)

           for (x = 0; x < sudoku_dim; x++) {

                

                xp = (int) ((a11*x +a12*y + a13) / (a31*x + a32*y + 1)); // formula 16.18 on page 380

                yp = (int) ((a21*x +a22*y + a23) / (a31*x + a32*y + 1)); // formula 16.19 on page 380

                

                if (yp >= 0 && yp < hauteur && xp >= 0 && xp < largueur)

                       image2[y][x] = image1[yp][xp];

                else

                       image2[y][x] = 0;

             

           }

    

}

6. Perspective transformation function optimized and running fine

public void travaille_5_perspective_transformer_optimized() {

      

 // Multiplications replaced by additions in the loop

 // Average response time after many runs of 100 calls :     

 // 0,03 second on Samsung Galaxy S III : Dual core, 1500 MHz, Snapdragon S4 Krait, 2048 MB RAM with Android 4.0.4

 // 0,10 second on Google Nexus S with Android 4.1.1

 // 0,07 second on Google Nexus One with Android 2.3.4

            

       int x, y; // x, y on page 380

       int xp, yp; // x prime, y prime on page 380

        

       double a11, a12, a13, a21, a22, a23, a31, a32, a33; // on page 383

   

       double numerateur_x = 0; // to improve performance

       double numerateur_y = 0; // to improve performance

       double denominateur = 0; // to improve performance  

        

       double numerateur_x_i = 0; // to improve performance

       double numerateur_y_i = 0; // to improve performance

       double denominateur_i = 0; // to improve performance  

               

       short la_ligne []; // to improve performance

     

       // formula 16.28 on page 383

       a31 = ((x1p-x2p+x3p-x4p)*(y4p-y3p)-(y1p-y2p+y3p-y4p)*(x4p-x3p))/((x2p-x3p)*(y4p-y3p)-(x4p-x3p)*(y2p-y3p));

    

       // formula 16.29 on page 383

       a32 = ((y1p-y2p+y3p-y4p)*(x2p-x3p)-(x1p-x2p+x3p-x4p)*(y2p-y3p))/((x2p-x3p)*(y4p-y3p)-(x4p-x3p)*(y2p-y3p));

    

       // formula 16.17 on page 380

       a33 = 1;

    

       // formula 16.30 on page 383

       a11 = x2p-x1p+a31*x2p;

       a12 = x4p-x1p+a32*x4p;

       a13 = x1p;

    

       // formula 16.31 on page 383

       a21 = y2p-y1p+a31*y2p;

       a22 = y4p-y1p+a32*y4p;

       a23 = y1p;

       // Projective mapping via the unit square on page 382 : unit square to image2 dimension

       a31 = a31 / sudoku_dim;

       a32 = a32 / sudoku_dim;

       a11 = a11 / sudoku_dim;

       a12 = a12 / sudoku_dim;

       a21 = a21 / sudoku_dim;

       a22 = a22 / sudoku_dim;

       

       // for each point (x, y) in image2,

       //      we calculate (xp, yp) in image1 using formula 16.18 and 16.19 on page 380

       // the formulas are transformed a bit to improve performance by avoiding many multiplications

    

       numerateur_x_i = a13;

       numerateur_y_i = a23;

       denominateur_i = a33;

          

       for (y = 0; y < sudoku_dim; y++) {

        

             numerateur_x = numerateur_x_i;

             numerateur_y = numerateur_y_i;

             denominateur = denominateur_i;

               

             la_ligne = image2[y]; // to improve performance

             for (x = 0; x < sudoku_dim; x++) {

                    xp = (int) (numerateur_x/denominateur + 0.5); // formula 16.18 on page 380

                    yp = (int) (numerateur_y/denominateur + 0.5); // formula 16.19 on page 380

                    if (yp >= 0 && yp < hauteur && xp >= 0 && xp < largueur)

                           la_ligne[x] = image1[yp][xp];

                    else

                           la_ligne[x] = 0;

             

                    numerateur_x += a11;

                    numerateur_y += a21;

                    denominateur += a31;

             }

        

             numerateur_x_i += a12;

             numerateur_y_i += a22;

             denominateur_i += a32;

               

       }

          

}     

7. How to log image1 and image2 and import them to Excel

7.1 Place this example code for image1 at the end of the optimized or not optimized function

      

       int i, j;

       String ligne;

       ligne = ", ";

       for (j = 0; j < image1[0].length; j++)

             ligne = ligne + "," + j;

       Log.i("Entete", ligne);

       for (i = 0 ; i < image1.length; i++) {

             ligne = "," + i;

            

             for (j = 0; j < image1[0].length; j++)

                    ligne = ligne + "," + image1[i][j];

                   

             Log.i("Ligne " + i, ligne);                   

       }    

    

7.2 Copy log and paste it in Excel

7.3 Select column A and use Data->Text to columns in Excel using comma as delimiter

7.4 Delete column A