Sudoku solver. C recursive implementation (backtracking technique)

Sudoku programming problem is well known. There are several algorithms that can be implemented. In this article I’ll show one that you’ve probably seen already — recursive solving (with backtracking). This algorithm is Depth-First Search, attempts to solve the branch completely, hence, has exponential time complexity (O(exp(n)) and, in current implementation, will return unsolved puzzle when unsolvable is given.

First, we need a solvable puzzle. Ideally, one that you can solve by hand in order to write tests properly:

Second, we need to introduce vocabulary and rules:

Row — an array of 9 elements of the puzzle located horizontally. (E.g. first row is [1,7,4,0,9,0,6,0,0]).

Column — an array of 9 elements of the puzzle located vertically.
(E.g. first column is [1,0,5,0,8,3,2,0,0])

Square — an array of 9 elements of the puzzle located in shape of 3x3 square stating from first row and column.
(E.g. first square is [1,7,4,0,0,0,5,3,0])

According to rules of traditional Sudoku: element in row | column | square should be unique.

Third, lets pseudocode the solution using backtracking technique:

1. Find empty (0) cell.
  1.1. If there is no empty cells -> return the puzzle.2. Find valid guesses for empty cell.
2.1. Try to recursively solve puzzle with this guess.
2.1.1. If there is no valid guesses, then assign cell value to empty (0) and prune this branch as dead-end. (backtracking)

Current implementation will explore every branch until (a) finds a solution or (b) finds that there is no solutions. Every empty cell is a node, every guess is the branch.

Since this is my first C program, I don’t know any other way to test, but using printf function :)

First, declare functions:

Each function will return 1 as `success` and 0 as `failure` signal.

Next, implement find_empty_cell :

In order to use it we need to declare two variables in caller-function. This function will use pointers to this variables and modify them.

Now, implement valid function:

And now, solve function:

And, finally, complete solution:

Thanks for reading this .

Cheers!