Open in app

Sign in

Write

Sign in

Augmented Reality Sudoku Solver: Solving Puzzle using Algorithm X

Shashank Goyal
13 min readOct 8, 2021

--

In this article, we are going to build a GUI-based AR Sudoku Solver which can be used to solve sudoku in Augmented Reality. We will also be building a game around it to enable us to scan an image of the sudoku and play it.

We aim to solve any sudoku of the N dimension, where N is a non-prime. The project will be implemented in two forms -

  • An option to load an image saved on the system or use the webcam to feed the image to the program and then play the game on the system.
  • An option to use Augmented Reality and solve the sudoku by showing the puzzle to the webcam.

The project uses Dancing Links in the form of Algorithm X to find the solution of the Sudoku puzzle. Sudoku is a well-known NP-Complete problem and Algorithm X is a means of implementing a form of greedy depth-first search to find the appropriate solution. The project will be blogged in 4 parts -

Part I: Solving the Sudoku —

For solving sudoku in the least time possible and to find all the possible solutions we use Algorithm X. Algorithm X is an algorithm for solving the exact cover problem. It is a straightforward recursive, nondeterministic, depth-first, backtracking algorithm used by Donald Knuth to demonstrate an efficient implementation called DLX, which uses the dancing links technique.

Fun Fact: Algorithm X was named as such due to lack of a better name.

Let us first take a look at the Exact Cover Problem -

Given a collection S of subsets of a set X, an exact cover of X is a sub-collection S* of S that satisfies two conditions -

  • The intersection of any two distinct subsets in S* is empty.
  • The union of the subsets in S* is X, i.e., the subsets in S* cover X

Example -

Consider the exact cover problem specified by the universe U = {1, 2, 3, 4, 5, 6, 7} and the collection of sets S = {A, B, C, D, E, F}

A = {1, 4, 7};
B = {1, 4};
C = {4, 5, 7};
D = {3, 5, 6};
E = {2, 3, 6, 7};
F = {2, 7};

Thus, the rows correspond to the collection of sets and columns correspond to the elements of the universe.
Row Representation -

+-----+--------------+
| ROW |   ELEMENTS   |
+-----+--------------+
| A   | {1, 4, 7}    |
| B   | {1, 4}       |
| C   | {4, 5, 7}    |
| D   | {3, 5, 6}    |
| E   | {2, 3, 6, 7} |
| F   | {2, 7}       |
+-----+--------------+

Column Representation -

+--------+----------------------+
| COLUMN |       ELEMENTS       |
+--------+----------------------+
|      1 | {'A', 'B'},          |
|      2 | {'E', 'F'},          |
|      3 | {'D', 'E'},          |
|      4 | {'A', 'B', 'C'},     |
|      5 | {'C', 'D'},          |
|      6 | {'D', 'E'},          |
|      7 | {'A', 'C', 'E', 'F'} |
+--------+----------------------+

Matrix Representation -

The above rows and columns can be represented using a 6x7 incidence matrix.

+-----+---+---+---+---+---+---+---+
|     | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-----+---+---+---+---+---+---+---+
| A   | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
+-----+---+---+---+---+---+---+---+
| B   | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
+-----+---+---+---+---+---+---+---+
| C   | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
+-----+---+---+---+---+---+---+---+
| D   | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
+-----+---+---+---+---+---+---+---+
| E   | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
+-----+---+---+---+---+---+---+---+
| F   | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
+-----+---+---+---+---+---+---+---+

Solution Approach -

  • Step 1: (Level 0)
  1. Find the column with the minimum number ones.
  2. In this case, the column 1 has two ones. [i.e. the smallest index with the min. number of ones]
  3. Add Row A to the solution.

Partial Solution = [A]

+---+---+---+---+---+---+---+---+
|   | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---+---+---+---+---+---+---+---+
| A | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
+---+---+---+---+---+---+---+---+
| B | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+
| C | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
+---+---+---+---+---+---+---+---+
| D | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
+---+---+---+---+---+---+---+---+
| E | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| F | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
+---+---+---+---+---+---+---+---+
  • Step 2: (Level 1)
  1. In row A mark all the columns with ones.
+---+---+---+---+---+---+---+---+
|   | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---+---+---+---+---+---+---+---+
| A | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
+---+---+---+---+---+---+---+---+
| B | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+
| C | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
+---+---+---+---+---+---+---+---+
| D | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
+---+---+---+---+---+---+---+---+
| E | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| F | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
+---+---+---+---+---+---+---+---+

2. Remove all the rows and columns containing a marked one.

+---+---+---+---+---+
|   | 2 | 3 | 5 | 6 |
+---+---+---+---+---+
| D | 0 | 1 | 1 | 1 |
+---+---+---+---+---+
  • Step 3: (Level 2)
  1. Repeat step 1.
  2. From Step 3–1., we add the row D to the solution.

Partial Solution = [A, D]

3. But, the table is empty now and the solution does not generate a cover, this means we need to return to level 0.

  • Step 4: (Level 0)
  1. Remove D and A from the solution.
  2. Continue from 13., Add B to the solution.

Partial Solution = [B]

+---+---+---+---+---+---+---+---+
|   | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---+---+---+---+---+---+---+---+
| A | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
+---+---+---+---+---+---+---+---+
| B | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+
| C | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
+---+---+---+---+---+---+---+---+
| D | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
+---+---+---+---+---+---+---+---+
| E | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| F | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
+---+---+---+---+---+---+---+---+
  • Step 5: (Level 1)
  1. In row B mark all the columns with ones.
+---+---+---+---+---+---+---+---+
|   | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---+---+---+---+---+---+---+---+
| A | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
+---+---+---+---+---+---+---+---+
| B | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+
| C | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
+---+---+---+---+---+---+---+---+
| D | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
+---+---+---+---+---+---+---+---+
| E | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+
| F | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
+---+---+---+---+---+---+---+---+

2. Remove all the rows and columns containing a marked one.

+---+---+---+---+---+---+
|   | 2 | 3 | 5 | 6 | 7 |
+---+---+---+---+---+---+
| D | 0 | 1 | 1 | 1 | 0 |
+---+---+---+---+---+---+
| E | 1 | 1 | 0 | 1 | 1 |
+---+---+---+---+---+---+
| F | 1 | 0 | 0 | 0 | 1 |
+---+---+---+---+---+---+
  • Step 6: (Level 1)
  1. Repeat Step 1.
  2. In this case the column 5 has a single one.
  3. So we now add D to the solution.

Partial Solution = [B, D]

  • Step 7: (Level 2)
  1. In row D mark all the columns with ones.
+---+---+---+---+---+---+
|   | 2 | 3 | 5 | 6 | 7 |
+---+---+---+---+---+---+
| D | 0 | 1 | 1 | 1 | 0 |
+---+---+---+---+---+---+
| E | 1 | 1 | 0 | 1 | 1 |
+---+---+---+---+---+---+
| F | 1 | 0 | 0 | 0 | 1 |
+---+---+---+---+---+---+

2. Remove all the rows and columns containing a marked one.

+---+---+---+
|   | 2 | 7 |
+---+---+---+
| F | 1 | 1 |
+---+---+---+
  • Step 8: (Level 3)
  1. Repeat step 1.
  2. From Step 8–1., we add the row F to the solution.

Partial Solution = [B, D, F]

3. Again, the table is empty, but now the solution generates a cover. So we end with this solution.

Finally, the solution is -

+---+---+---+---+---+---+---+---+
|   | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---+---+---+---+---+---+---+---+
| B | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+
| D | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
+---+---+---+---+---+---+---+---+
| F | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
+---+---+---+---+---+---+---+---+

Dancing Links -

Dancing links is a technique for reverting the operation of deleting a node from a circular doubly linked list. It is particularly useful for efficiently implementing backtracking algorithms.

Deleting a Node -

Consider, the case of deleting a node x, with the right pointer pointing to the node on the right of x and similarly, the left pointer pointing to the left node. the deletion can be performed by -

x.left.right ← x.right;
x.right.left ← x.left;

Adding the Node -

The Node x can be added back by implementing this -

x.left.right ← x;
x.right.left ← x;

Dancing Steps -

One good way to implement algorithm X is to represent each 1 in the matrix A as a data object x with five fields L[x], R[x], U [x], D[x], C[x]. Rows of the matrix are doubly linked as circular lists via the L and R fields (“left” and “right”); columns are doubly linked as circular lists via the U and D fields (“up” and “down”). Each column list also includes a special data object called its list header.

To read more about Dancing Links, check out this PDF.
So without further ado, let’s start with the code ….

Class Sudoku -

Here, we first initialize the class with the following variables -

  • Matrix: NxN Matrix with the sudoku values with ‘0’ in place of blanks.
  • Init_Matrix: Since the solution modifications happen in place, this serves as a backup copy.
  • Box_Row: This is the number of rows in a box of the sudoku.
  • Box_Col: This is the number of columns in a box of the sudoku.
  • N: This is the total number of cells in a row or column of the sudoku.

To understand Box_Row and Box_Col, see images below -

Here, the Box_Row = 2 and Box_Col = 3
Here, the Box_Row = 2 and Box_Col = 4

Initialize Row and Column Pointers -

The rows and columns here act as the doubly linked lists, which we have understood above.
The rows consist of each possible cell position value — list pair i.e. -

rows => {
    (0,0,1) : [
        ("row-col", (0, 0)), ("row-num", (0, 1)), 
        ("col-num", (0, 1)), ("box-num", (0, 1))],
    (0,0,2) : [
        ("row-col", (0, 0)), ("row-num", (0, 2)), 
        ("col-num", (0, 2)), ("box-num", (0, 2))], 
                          .
                          .
                          .
    (4,6,3) : [
        ("row-col", (4, 6)), ("row-num", (4, 3)), 
        ("col-num", (6, 3)), ("box-num", (6, 3))],
                          .
                          .
                          .    
    (8,8,8) : [
        ("row-col", (8, 8)), ("row-num", (8, 8)), 
        ("col-num", (8, 8)), ("box-num", (9, 8))]
    (8,8,9) : [
        ("row-col", (8, 8)), ("row-num", (8, 9)), 
        ("col-num", (8, 9)), ("box-num", (9, 9))]
}

Similarly, the column dictionary is -

columns = {
    ("row-col", (0, 0)): {(0,0,0), (0,0,1), ..... (0,0,9)},
    ("row-num", (0, 1)): {(0,0,1), (0,1,1), ..... (0,8,1)},
    ("col-num", (0, 1)): {(0,0,1), (1,0,1), ..... (8,0,1)},
    ("box-num", (0, 1)): {(0,0,1), (0,1,1), ..... (2,2,1)},
                                .
                                .
                                .
    ("row-col", (8, 8)): {(8,8,0), (8,8,1), ..... (8,8,9)},
    ("row-num", (8, 9)): {(8,0,9), (8,1,9), ..... (8,8,9)},
    ("col-num", (8, 9)): {(0,8,9), (1,8,9), ..... (8,8,9)},
    ("box-num", (8, 9)): {(6,6,9), (6,7,9), ..... (8,8,9)}
}

Solve -

So, just like the exact cover example above for solving, first, we find the column with the minimum number of links. We then iterate through the cell values for that column and include that in the solution (“partial_solution.append(values)”). We then “cover” the values in that column (Covering will be explained in the next step). We then recursively call the same function again with the existing partial solution to move further. This recursive calling proceeds until the columns dictionary is empty that is the problem has been covered. We then “uncover” the column and move on with another column to find more solutions.

Cover Column -

The idea behind covering a column is essentially iterating through all rows with the current column value, then iterating through all columns having values with the current row, and then finally iterating through all the rows having a common value with the latest column. This is the same as Steps 5, 6, and 7 from the above. This is faster than brute force because it follows the same principle as deletion of a node in dancing links, i.e. the operation is of constant time.

Uncover Column -

This is the exact opposite of the cover column operation and works on the principle of the addition of a node from dancing links.

Get Solution -

This is the driver method for the class. It first covers all columns with values that are already present in the sudoku. Then it iterates through the solutions from the “self.solve” method. It then copies the solution values to the matrix and appends them to the solution list.

Element Possible -

This is a helper method and has no use in finding the solution of the sudoku. But it is used to check whether a value is valid for a certain position in the sudoku.

Main -

This is the main function where we call the Sudoku class and find the solution. Overall the solution may seem a little complex at first, but it is better than the backtracking approach for two reasons -

  • It is faster due to constant time inclusion and exclusion operation.
  • Unlike Backtracking, it gives all possible solutions together.

Output -

Solution Number 1 -9 8 7 | 6 5 4 | 3 2 1
2 4 6 | 1 7 3 | 9 8 5
3 5 1 | 9 2 8 | 7 4 6
----------------------
1 2 8 | 5 3 7 | 6 9 4
6 3 4 | 8 9 2 | 1 5 7
7 9 5 | 4 6 1 | 8 3 2
----------------------
5 1 9 | 2 8 6 | 4 7 3
4 7 2 | 3 1 9 | 5 6 8
8 6 3 | 7 4 5 | 2 1 9Solved in 0.0046 s

You can find the complete python implementation here. If you found this article helpful, please follow me on Medium and GitHub and star the Project Repository.

Do check out other parts of this article series -

Sudoku Solver
Computer Vision
Algorithms
Machine Learning
Augmented Reality

--

--

Shashank Goyal

Written by Shashank Goyal

32 Followers

I'm Shashank Goyal, a passionate Dual Master's student at Johns Hopkins University, pursuing degrees in Computer Science and Robotics.

Help

Status

About

Careers

Press

Blog

Privacy

Terms

Text to speech

Teams