问Sudoku算法生成重复值

EN

from math import floor
from typing import List

class Cell:
    x: int
    y: int
    times_visited: int = 0
    value: int
    is_prefilled: bool

    def __init__(self, x: int, y: int, value: int):
        self.x = x
        self.y = y
        self.value = value
        self.is_prefilled = value != None

def gen_possible_for(cell: Cell, sudoku: List[List[Cell]]) -> List[int]:
    # Horizontal
    horizontal = sudoku[cell.y]
    # Vertical
    vertical = [sudoku[y][cell.x] for y in range(9)]
    # 3x3 square
    base_x = floor(cell.x / 3) * 3
    base_y = floor(cell.y / 3) * 3
    square = [
        sudoku[base_y + rel_y][base_x + rel_x]
        for rel_y in range(3)
        for rel_x in range(3)
    ]

    #print("H:",horizontal)
    #print("V:",vertical)
    #print("S:",square)

    all = horizontal + vertical + square
    return [v for v in range(1, 9+1) if v not in all]

def solve_sudoku(sudoku: List[List[int]]):
    # Recursive backtracking algorithm
    
    sudoku_cells = [Cell(x, y, sudoku[y][x]) for x in range(9) for y in range(9)]

    i = 0
    while i < len(sudoku_cells):
        cell = sudoku_cells[i]

        if not cell.is_prefilled:
            possible_values = gen_possible_for(cell, sudoku)

            if not possible_values or cell.times_visited >= len(possible_values):
                if i == 0:
                    # Sudoku is unsolvable
                    return False
                
                print("decr")
                i -= 1
            else:
                cell.value = possible_values[cell.times_visited]
                i += 1
            
            cell.times_visited += 1
        else:
            i += 1
    
    # For some reason, (x + y * 9) causes the grid to rotate 90 degrees counter-clockwise
    return [[sudoku_cells[y + x * 9].value for x in range(9)] for y in range(9)]

# A sudoku from sudoku.com

sudoku = [
    [None, 6,    7,    None, 5,    4,    None, None, None],
    [1,    None, None, None, None, None, 2,    None, None],
    [None, None, None, 6,    1,    None, None, 4,    None],

    [None, None, None, None, None, 5,    None, 6,    None],
    [None, 1,    2,    8,    None, None, 4,    None, None],
    [6,    None, 3,    None, None, None, 8,    7,    None],

    [None, None, None, None, None, 7,    None, 2,    3   ],
    [7,    2,    9,    3,    6,    None, None, 8,    4   ],
    [4,    None, 6,    5,    8,    2,    None, 9,    1   ]
]

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