Solve soduku like human without backtracking. https://4ft35t.github.io/post/solve-soduku-like-human-without-backtracking/

sudoku.py

#!/usr/bin/env python3
# coding: utf-8
# @2024-07-25 22:54:41
# vim: set expandtab tabstop=4 shiftwidth=4 softtabstop=4:

'''
resolve sudoku
'''

from copy import deepcopy

class Cell:
    def __init__(self, x, y, value=None):
        self.x = x
        self.y = y
        self.init_value(value)

    def init_value(self, value):
        self.value = 0
        if value:
            self.values = [value]
        else:
            # possible values of cell
            self.values = list(range(1, 10))

    def get_near_cells(self, all_cells):
        '''
        (0,0) ... (8,0)
        ...
        (0,8) ... (8,8)
        9*9 cells
        '''
        row = [i for i in all_cells if i.y == self.y]
        col = [i for i in all_cells if i.x == self.x]
        block = [i for i in all_cells if i.x // 3 == self.x // 3 and i.y // 3 == self.y // 3]

        return row + col + block

    def del_near_value(self, all_cells):
        '''delete current cell value from near cells'''
        near_cells = self.get_near_cells(all_cells)
        for cell in near_cells:
            if self.value in cell.values:
                cell.values.remove(self.value)

    def set_value(self, all_cells):
        '''cell has only one value, set it'''
        value = self.values[0]
        self.value = value
        self.values = []
        # del value from near cells
        self.del_near_value(all_cells)

class Sudoku:
    def __init__(self, matrix):
        self.cells = []
        for y, row in enumerate(matrix):
            for x, value in enumerate(row):
                cell = Cell(x, y, value)
                self.cells.append(cell)

    def set_value_in_block(self):
        '''in a 3*3 block, if a number only in one cell's values, find and set it
        eg in matrix5:
        in the top center block, 5 only (3,2) cell's values, while this cell's values is [3,5,6]
        so set (3,2) cell's value to 5
        '''

        # 3*3 block
        for x in range(0, 9, 3):
            for y in range(0, 9, 3):
                block = [i for i in self.cells if i.x // 3 == x // 3 and i.y // 3 == y // 3]
                for n in range(1, 10):
                    cells = [i for i in block if n in i.values]
                    if len(cells) == 1:
                        cell = cells[0]
                        cell.values = [n]

    def resolve_with_backtrack(self):
        '''when no cell has only one value, use backtrack to resolve sudoku'''

        shortest = sorted([i for i in self.cells if i.values], key=lambda x: len(x.values))[0]
        current_state = deepcopy(self.cells)

        # try each value of cell
        cell = shortest
        for value in cell.values:
            new_sudoku = Sudoku([])
            new_sudoku.cells = deepcopy(current_state)
            new_cell = [i for i in new_sudoku.cells if i.x == cell.x and i.y == cell.y][0]
            new_cell.values = [value]
            result = new_sudoku.resolve()
            if result:
                print('cell:', (cell.x, cell.y), 'value:', value, cell.values)
                return new_sudoku

    def resolve(self):
        while True:
            # set value for cells which has only one value in a 3*3 block
            self.set_value_in_block()

            count = 0
            # set value for cells which has only one value
            for cell in self.cells:
                if len(cell.values) == 1:
                    cell.set_value(self.cells)
                    count += 1

            # check if all cells have value, success
            if all([cell.value for cell in self.cells]):
                break
            # check if there is a cell which has no value, failed
            if any([not cell.value and not cell.values for cell in self.cells]):
                return []

            # hard level, no cell has only one value
            # use backtrack to resolve
            if count == 0:
                result = self.resolve_with_backtrack()
                self.cells = result.cells

        return [[cell.value for cell in self.cells[i:i+9]] for i in range(0, 81, 9)]

    def show(self):
        print('-' * 23)
        for i, cell in enumerate(self.cells):
            print(cell.value, end=' ')
            if i % 3 == 2:
                print('|', end=' ')
            if i % 9 == 8:
                print()
            if i % 27 == 26:
                print('-' * 23)

def test():
    matrix1 = [
        [0, 6, 1, 0, 0, 4, 7, 0, 0],
        [0, 0, 9, 0, 0, 0, 6, 0, 0],
        [0, 0, 8, 0, 1, 0, 0, 9, 0],
        [0, 0, 7, 0, 2, 0, 3, 8, 0],
        [0, 0, 0, 8, 3, 9, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 3, 7, 0, 0, 0, 6],
        [0, 2, 0, 1, 0, 5, 8, 3, 0],
        [0, 0, 0, 0, 8, 0, 2, 0, 0]
    ]

    matrix2 = [
        [0, 0, 0, 0, 0, 0, 4, 5, 6],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 5, 0, 0, 4, 6, 0, 9, 2],
        [2, 8, 0, 7, 0, 0, 0, 0, 3],
        [6, 0, 0, 0, 1, 0, 5, 0, 0],
        [0, 0, 0, 0, 0, 8, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 3, 0, 0],
        [8, 0, 0, 9, 0, 4, 6, 0, 0],
        [0, 2, 0, 8, 0, 0, 0, 0, 1]
    ]

    matrix3 = [
        [0, 0, 0, 0, 0, 0, 0, 1, 2],
        [0, 0, 0, 0, 3, 5, 0, 0, 0],
        [0, 0, 0, 6, 0, 0, 0, 7, 0],
        [7, 0, 0, 0, 0, 0, 3, 0, 0],
        [0, 0, 0, 4, 0, 0, 8, 0, 0],
        [1, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 1, 2, 0, 0, 0, 0],
        [0, 8, 0, 0, 0, 0, 0, 4, 0],
        [0, 5, 0, 0, 0, 0, 6, 0, 0]
    ]

    matrix4 = [
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 8, 0, 0, 0, 0, 4, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 6, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [2, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 2, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0]
    ]

    matrix5 = [
        [0, 0, 6, 0, 8, 0, 5, 7, 0],
        [0, 0, 0, 4, 0, 0, 3, 0, 0],
        [0, 0, 0, 0, 2, 7, 1, 0, 0],
        [0, 7, 0, 0, 5, 0, 0, 4, 0],
        [0, 4, 9, 0, 0, 8, 6, 0, 0],
        [0, 0, 3, 0, 0, 0, 0, 1, 0],
        [0, 0, 0, 2, 3, 5, 9, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 9, 0, 0, 0, 2, 0]
    ]
    matrix_list = [matrix1, matrix2, matrix3, matrix4, matrix5]
    # matrix_list = [ matrix5]
    for matrix in matrix_list:
        print('matrix:')
        for row in matrix:
            print(row)
        print('result:')
        sudoku = Sudoku(matrix)
        result = sudoku.resolve()
        if result:
            sudoku.show()

if __name__ == '__main__':
    test()

add resolve_with_backtrack to solve matrix5