Algorithms – Backtracking – Sudoku

Sudoku is a number placement puzzle, where the objective is to fill a square grid of size n, with numbers between 1 to n. As constraints, each row, column, and sub-grids should contain empty spaces or unique numbers from 1 to n.

Step-by-step algorithm

With backtracking, we try to add digits one by one. When we find that a digit cannot lead to a solution, we backtrack (remove it) and try the next digit.

Steps:

  1. Make a list of all the empty places
  2. Select a position and place a number between 1 and n, and validate the grid
    1. If the constraints fails – abandon the candidate and go back to step 2 with another number
  3. Until the solution is not found – repeat steps 2-3

Iteration 1

Let’s only look on the bottom-right grid first.

Each square contains all the digits from 1 to 9.

We see that we have 4 empty places, and 4 digits that are not there (4, 6, 7, 8) One of the constrains is to have unique digits in a sub-grid such as this one, so we have to use those digits to fill the empty spaces.

Iteration 2

We start with the first available position, and iterate through all digits.

We write 1 in the empty place, and then we check the constraints: We fail the constraints, because we already have the digit 1 in the same sub-grid. Therefore, we continue with the next digit.

Iteration 3

We write 2 in the empty place, and then we check the constraints:

=> We fail the constraints, because we already have the digit 2 in the same sub-grid. Therefore, we continue with the next digit.

Same goes for 3 (exists in sub-grid), 4 (exists in same row), 5 (exists in sub-grid), 6 (exists in same col).

7 is valid, because it doesn’t break the constraints.

Therefore, we write 7 and check the next empty-space.

Iteration 4

1,2,3 are in the same sub-grid, so they fail the constraints, but 4 is ok so we write it and check the next empty-space.

Iteration 5

1,2,3,4,5 are in the same sub-grid, but 6 doesn’t break constraints, so we write it and check the next empty space.

Iteration 6

8 is the only remaining digit that doesn’t exist in sub-grid. We write 8 in the empty-space, but we see that the constraints are broken (same column).

Because the constraints are broken, we clear the value and continue to the next digit. Since we don’t have any remaining digit (9 in same sub-grid), we return to the previously written digit and continue to the next available digit.

Iteration 7

We write the digit 8, but the constraints are again broken (already exists in the same column), and 9 already is in the same sub-grid, so we set as empty space and go one more step back to the previously written digit and continue to the next available digit.

Iteration 8

We continue from the current digit (4):

  • 5 is invalid (same sub-grid)
  • 6 is invalid (same row)
  • 7 is invalid (same sub-grid)
  • 8 is invalid (same column)
  • 9 is invalid (same sub-grid)

=> We set as empty space and go one more step back to the previously written digit and continue to the next available digit.

Iteration 9

We continue from the current digit (7):

  • 8 is valid, no constraints are broken

=> We write 8 and check the next empty space

… and so on.

Code implementation

You may also like...

Leave a Reply