Sudoku kata

Introduction

Sudoku is a very popular number-placement puzzle.

The objective is to fill a 9 × 9 grid with digits so that each column, each row, and each of the nine 3 × 3 regions that compose the grid contain all of the digits from 1 to 9.

The starting point is a partially completed grid:

sudoku

The final one would like this:

Rules

  • Every number in the range should be present in every row, column and region
  • Within a row, column and region there can be no repeated number

The following are examples of violations:

sudoku - wrong row

sudoku - wrong column

sudoku - wrong region

Neither one of these can be present in a valid solution.

Instructions

This kata is divided into three levels of increasing difficulty. Start with the first and work your way up.

First level

Create an application capable of determining whether a proposed solution is valid for a given initial grid.

The input is the path to two CSV files containing N rows and N numbers per row.

Keep in mind that N has to be a square of an integer (4, 9, 16, 25,...)

Example:

5,3,,,7,,,,
6,,,1,9,5,,,
,9,8,,,,,6,
8,,,,6,,,,3
4,,,8,,3,,,1
7,,,,2,,,,6
,6,,,,,2,8,
,,,4,1,9,,,5
,,,,8,,,7,9

 

The first file defines the initial grid and the second the proposed solution.

In this example, if the contents of the second file were:

5,3,,,7,,,,
6,,,1,9,5,,,
,9,8,,,,,6,
8,,,,6,,,,3
4,,,8,7,3,,,1
7,,,,2,,,,6
,6,,,,,2,8,
,,,4,1,9,,,5
,1,,,8,,,7,9

 

The output should be

The proposed solution is incorrect

Whereas if the contents were

5,3,4,6,7,8,9,1,2
6,7,2,1,9,5,3,4,8
1,9,8,3,4,2,5,6,7
8,5,9,7,6,1,4,2,3
4,2,6,8,5,3,7,9,1
7,1,3,9,2,4,8,5,6
9,6,1,5,3,7,2,8,4
2,8,7,4,1,9,6,3,5
3,4,5,2,8,6,1,7,9

The output should be

The proposed solution is correct

Second level

Create an application to provide a valid solution given the initial grid or a message in case the Sudoku is not solvable.

The input is CSV file with the same format as in the first level and the output is a CSV string containing the solution found in case it exists.

Example: 

For an input like 

5,3,,,7,,,,
6,,,1,9,5,,,
,9,8,,,,,6,
8,,,,6,,,,3
4,,,8,,3,,,1
7,,,,2,,,,6
,6,,,,,2,8,
,,,4,1,9,,,5
,,,,8,,,7,9

The output should be

5,3,4,6,7,8,9,1,2
6,7,2,1,9,5,3,4,8
1,9,8,3,4,2,5,6,7
8,5,9,7,6,1,4,2,3
4,2,6,8,5,3,7,9,1
7,1,3,9,2,4,8,5,6
9,6,1,5,3,7,2,8,4
2,8,7,4,1,9,6,3,5
3,4,5,2,8,6,1,7,9

And for an input like 

5,3,,,7,,,,
6,,,1,9,5,,,
,9,8,,,,,6,
8,,,,6,,,,3
4,,,8,,3,,,1
7,,,,2,,,,6
6,,,,,,2,8,
,,,4,1,9,,,5
,,,,8,,,7,9

The output should be

The Sudoku is not solvable

Hints:

  • Start assuming the grid is 4x4 and then generalize the solution
  • Don't try to come up with the most efficient algorithm at first. Build a strong test suite and then refactor the algorithm
  • Use the solution to level one if it helps
  • There might be situations where the Sudoku's unsolvability isn't obvious at first sight, for instance:
1,,3,4,
3,4,1,2,
,3,2,1,
4,1,,3,

Third level

Create an application which can produce a solvable NxN initial grid.

In this case the input is the grid dimension and the initial number of blank spaces.

The output is a CSV string with the format discussed in the previous cases or a message stating that the requirements are not satisfiable.

Example:

For an input like:

3 51

The output should be something like:

5,3,,,7,,,,
6,,,1,9,5,,,
,9,8,,,,,6,
8,,,,6,,,,3
4,,,8,,3,,,1
7,,,,2,,,,6
,6,,,,,2,8,
,,,4,1,9,,,5
,,,,8,,,7,9

Hints:

  • Try to re-use the solutions to levels 1 and 2