# 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:

- Make a list of all the empty places
- Select a position and place a number between 1 and n, and validate the grid
- If the constraints fails – abandon the candidate and go back to step 2 with another number

- 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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 |
#include <iostream> constexpr int UNSET = 0; constexpr int N = 9; class Sudoku { public: int grid[N][N] = {}; Sudoku(int _grid[N][N]) { for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) grid[i][j] = _grid[i][j]; } bool solve() { int row, col; // if no more unset places, we're done if (!findNextEmpty(row, col)) return true; for (int num = 1; num <= 9; num++) { if (isLegalMove(row, col, num)) { // assign the num to that location grid[row][col] = num; if (solve()) return true; // failure, invalidate and check next number grid[row][col] = UNSET; } } return false; } bool isLegalMove(int row, int col, int num) { return grid[row][col] == UNSET && false == alreadyInRow(row, num) && false == alreadyInCol(col, num) && false == alreadyInBox(row - row % 3, col - col % 3, num) ; } void display() { for (int row = 0; row < N; row++) { for (int col = 0; col < N; col++) { std::cout << grid[row][col] << " "; } std::cout << std::endl; } } bool findNextEmpty(int &row, int &col) { for (row = 0; row < N; row++) for (col = 0; col < N; col++) if (grid[row][col] == UNSET) return true; return false; } private: bool alreadyInRow(int row, int num) { for (int col = 0; col < N; col++) if (grid[row][col] == num) return true; return false; } bool alreadyInCol(int col, int num) { for (int row = 0; row < N; row++) if (grid[row][col] == num) return true; return false; } bool alreadyInBox(int box_row, int box_col, int num) { for (int row = 0; row < 3; row++) for (int col = 0; col < 3; col++) if (grid[row + box_row][col + box_col] == num) return true; return false; } }; int main() { int grid[N][N] = { { 9, 3, 0, 0, 0, 4, 2, 0, 0 }, { 5, 0, 1, 6, 2, 0, 0, 8, 0 }, { 0, 0, 2, 0, 9, 0, 4, 5, 1 }, { 2, 0, 3, 0, 0, 0, 0, 0, 8 }, { 0, 1, 0, 0, 0, 0, 0, 3, 0 }, { 8, 0, 0, 0, 0, 0, 7, 0, 5 }, { 4, 5, 9, 0, 3, 0, 6, 0, 0 }, { 0, 8, 0, 0, 4, 6, 5, 0, 2 }, { 0, 0, 6, 9, 0, 0, 0, 4, 3 } }; Sudoku sudoku(grid); if (sudoku.solve() == true) sudoku.display(); else std::cout << "There is no solution"; std::cin.get(); return 0; } |