Sudoku/sudoku_solver.py
2021-01-08 18:23:03 +01:00

180 lines
4.9 KiB
Python

#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""
:mod:`sudoku_solver` module
:author: `Éric W`
:date: 2016, october
:Provides:
* a function `solve` to solve sudoku grids
:Example: with the following sudoku grid
.. code-block:: text
+-------+-------+-------+
| 9 . 6 | . 2 8 | . . 3 |
| . 4 . | 5 . . | . . 1 |
| . 8 . | 9 . . | . 4 . |
+-------+-------+-------+
| 6 . . | . . . | . 7 . |
| . . 8 | 2 . 6 | 9 . . |
| . 3 . | . . . | . . 5 |
+-------+-------+-------+
| . 5 . | . . 3 | . 6 . |
| 1 . . | . . 2 | . 8 . |
| 2 . . | 8 7 . | 5 . . |
+-------+-------+-------+
and second with the grid
.. code-block:: text
+-------+-------+-------+
| 9 . 6 | . 2 8 | . . 3 |
| . 4 . | 5 . . | . . 1 |
| . 8 . | 9 . . | . 4 . |
+-------+-------+-------+
| 6 . . | . . . | . 7 . |
| . . 8 | 2 . 6 | 9 . . |
| . 3 . | . . . | . . 5 |
+-------+-------+-------+
| . 5 . | . . 3 | . 6 . |
| 1 . . | . . 2 | . 8 . |
| 2 . . | 8 7 . | . . . |
+-------+-------+-------+
>>> from sudoku_grid import SudokuGrid
>>> strgrid = '906028003040500001080900040600000070008206900030000005050003060100002080200870500'
>>> grid = SudokuGrid(strgrid)
>>> solved_grid = solve(grid)
>>> len(solved_grid)
1
>>> solved_grid[0].pretty_print()
+-------+-------+-------+
| 9 1 6 | 4 2 8 | 7 5 3 |
| 3 4 2 | 5 6 7 | 8 9 1 |
| 7 8 5 | 9 3 1 | 2 4 6 |
+-------+-------+-------+
| 6 2 9 | 3 4 5 | 1 7 8 |
| 5 7 8 | 2 1 6 | 9 3 4 |
| 4 3 1 | 7 8 9 | 6 2 5 |
+-------+-------+-------+
| 8 5 7 | 1 9 3 | 4 6 2 |
| 1 9 4 | 6 5 2 | 3 8 7 |
| 2 6 3 | 8 7 4 | 5 1 9 |
+-------+-------+-------+
"""
import time
from sudoku_grid import SudokuGrid, EMPTY_SYMBOL
def __possible_values(s):
"""
:param s:
:type s: str
:return: a substring of '123456789' containing no character in s
:rtype: str
"""
return "".join(c for c in '123456789' if c not in s)
def __grid_exam(grid):
"""
:param grid: a Sudoku grid
:type grid: SudokuGrid
:return: a tuple (s, coord) where
* coord is a tuple of coordinate of a case
* poss is a string containing value's candidates for the case
no other case has less possibilities
:rtype: tuple
"""
ROWS = [grid.get_row(row) for row in range(9)]
COLS = [grid.get_col(col) for col in range(9)]
SQUARES = [grid.get_square(3*c, 3*r) for r in range(3) for c in range(3)]
poss_min, coord_min = '0123456789', (-1, -1)
for row in range(9):
for col in range(9):
if grid.is_empty_cell(col, row):
poss = __possible_values(ROWS[row] + COLS[col] + SQUARES[3 * (row // 3) + (col // 3)])
if len(poss) < len(poss_min):
poss_min = poss
coord_min = (col, row)
return poss_min, coord_min
def __is_solved(grid):
"""
:param grid: a Sudoku grid
:typr grid: sudoku_grid.grid
:return: `True` if the grid is solved, `False` otherwise
:rtype: bool
:UC: none
"""
return not any(grid.is_empty_cell(col, row) for row in range(9) for col in range(9))
def solve(grid, out_channel=None, node=None):
"""
:param grid: a Sudoku grid to solve
:type grid: SudokuGrid
:return: list of solutions (solved grids)
:rtype: list
:UC: none
"""
if __is_solved(grid):
if not out_channel is None:
out_channel.write('\t"{:s}"[shape=hexagon, fillcolor="#00FF00"];\n'.format(node))
return [grid.copy()]
else:
maybe, (col, row) = __grid_exam(grid)
res = []
for val in maybe:
if not out_channel is None:
label = str((val, col, row))
next_node = node + '{:s}{:d}{:d}'.format(val, col, row)
out_channel.write('\t"{:s}"[label="{:s}"];\n'.format(next_node, label))
out_channel.write('\t"{:s}" -> "{:s}";\n'.format(node, next_node))
else:
next_node = None
grid[col, row] = val
res += solve(grid, out_channel, next_node)
grid[col, row] = EMPTY_SYMBOL
return res
def solve_one(grid, pause=0, out_channel=None):
"""
:param grid: a Sudoku grid to solve
:type grid: sudoku_grid.grid
:param pause: delay between two steps of resolution
:type pause: float
:return: a solution of grid
:rtype: sudoku_grid.grid
:UC: none
"""
time.sleep(pause)
print("\x1b[2J", end='')
grid.pretty_print()
if out_channel:
out_channel.write(str(grid)+'\n')
if __is_solved(grid):
return [grid]
else:
maybe, (col, row) = __grid_exam(grid)
res = None
for val in maybe:
grid[col, row] = val
res = solve_one(grid, pause, out_channel)
grid[col, row] = EMPTY_SYMBOL
if not res is None:
return res
return res
if __name__ == '__main__':
import doctest
doctest.testmod ()