4_sudoku module

Sudoku Solver

Note

A description of the sudoku puzzle can be found at: https://en.wikipedia.org/wiki/Sudoku.

Given a string in SDM format, described below, write a program to find and return the solution for the sudoku puzzle in the string. The solution should be returned in the same SDM format as the input.

Some puzzles will not be solvable. In that case, return the string "Unsolvable".

The general SDM format is described here: http://www.sudocue.net/fileformats.php.

For our purposes, each SDM string will be a sequence of 81 digits, one for each position on the sudoku puzzle. Known numbers will be given, and unknown positions will have a zero value.

For example, assume you’re given this string of digits:

004006079000000602056092300078061030509000406020540890007410920105000000840600100

The string represents this starting sudoku puzzle:

0 0 4   0 0 6   0 7 9
0 0 0   0 0 0   6 0 2
0 5 6   0 9 2   3 0 0

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

0 0 7   4 1 0   9 2 0
1 0 5   0 0 0   0 0 0
8 4 0   6 0 0   1 0 0

4_sudoku.puzzle_from_sdm(sdm_file: pathlib.Path) → Generator[str, None, None]

Read the puzzles from a file in .sdm format.

Parameters

sdm_file (pathlib.Path) – file with Sudoku puzzles.

Returns

generator holding the string of a puzzle.

Return type

typing.Generator[str, None, None]

4_sudoku.sdm_to_array(sdm_string: str) → numpy.ndarray

Parse the sdm string to a Numpy ndarray, assuming a 9x9 puzzle.

Parameters

sdm_string (str) – sdm string with the puzzle.

Returns

puzzle converted to Numpy ndarray.

Return type

np.ndarray

4_sudoku.solve_puzzle(sudoku_puzzle: numpy.ndarray) → Optional[numpy.ndarray]

Recursive function to solve te Sudoku.

For each cell, search all the digits which could fit in it. When a cell has a unique valid digit, update the puzzle with that digit and recall this function.

If no cell with a single digit is found across the whole Sudoku, look for a unique digit among all the valid ones in each row, column or region.

If no other digit is found, the puzzle may have multiple solutions and recursion stops.

Parameters

sudoku_puzzle (np.ndarray) – puzzle data.

Returns

the puzzle updated with new digits until a solution is found or None when multiple solutions are possible.

Return type

typing.Optional[np.ndarray]