Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes) >>> sudoku(initial_grid) # doctest: +NORMALIZE_WHITESPACE [[3, 1, 6, 5, 7, 8,
(grid: Matrix)
| 73 | |
| 74 | |
| 75 | def sudoku(grid: Matrix) -> Matrix | None: |
| 76 | """ |
| 77 | Takes a partially filled-in grid and attempts to assign values to |
| 78 | all unassigned locations in such a way to meet the requirements |
| 79 | for Sudoku solution (non-duplication across rows, columns, and boxes) |
| 80 | |
| 81 | >>> sudoku(initial_grid) # doctest: +NORMALIZE_WHITESPACE |
| 82 | [[3, 1, 6, 5, 7, 8, 4, 9, 2], |
| 83 | [5, 2, 9, 1, 3, 4, 7, 6, 8], |
| 84 | [4, 8, 7, 6, 2, 9, 5, 3, 1], |
| 85 | [2, 6, 3, 4, 1, 5, 9, 8, 7], |
| 86 | [9, 7, 4, 8, 6, 3, 1, 2, 5], |
| 87 | [8, 5, 1, 7, 9, 2, 6, 4, 3], |
| 88 | [1, 3, 8, 9, 4, 7, 2, 5, 6], |
| 89 | [6, 9, 2, 3, 5, 1, 8, 7, 4], |
| 90 | [7, 4, 5, 2, 8, 6, 3, 1, 9]] |
| 91 | >>> sudoku(no_solution) is None |
| 92 | True |
| 93 | """ |
| 94 | if location := find_empty_location(grid): |
| 95 | row, column = location |
| 96 | else: |
| 97 | # If the location is ``None``, then the grid is solved. |
| 98 | return grid |
| 99 | |
| 100 | for digit in range(1, 10): |
| 101 | if is_safe(grid, row, column, digit): |
| 102 | grid[row][column] = digit |
| 103 | |
| 104 | if sudoku(grid) is not None: |
| 105 | return grid |
| 106 | |
| 107 | grid[row][column] = 0 |
| 108 | |
| 109 | return None |
| 110 | |
| 111 | |
| 112 | def print_solution(grid: Matrix) -> None: |
no test coverage detected