Sudoku/sudoku_solver.py

#!/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 ()