In this kata, we are going to write a Sodoku solver. The rules for Sudoku are:
- Every square has to contain a single number.
- Only the numbers from 1 through to 9 can be used.
- Each 3×3 box can only contain a number from 1 to 9 once and only once.
- Each vertical column can only contain each number from 1 to 9 once.
Practicing this kata pays off the most when it is done multiple times in multiple different ways. Many people have already written about such approaches:
- Solving every Sudoku puzzle by Peter Norvig and references contained therein.
- TDD Practice #2: The Sudoku Example in Clojure – Starting the Unit Testing outlines a strict TDD approach using the Transformation Priority Premise. This approach clearly shows how to incrementally develop a recursive algorithm.
- Brute force approaches often rely on some form of backtracking. The idea is to let the computer solve Sudoku puzzles using a brute-force approach. However, by using backtracking, we ensure that invalid branches are pruned early.
In the Java and Python versions (i.e. based on the OO paradigm), there is an option to exercise with the data clumping refactoring that is applicable to the pervasive grouping of the row and column parameters.