Как исправить мой решатель судоку на основе возврата

Question

Я пытался создать алгоритм решения судоку, используя python и основанный на возврате, но он всегда ничего не возвращал, говоря, что судоку неверно.

Вот мой код:

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

e = [0, 0]

def checkEmpty():
    for i in range(0, 9):
        for j in range(0, 9):
            if board[i][j] == 0:
                e[0] = i
                e[1] = j
                return True
    return False

def vLine(i, test):
    for j in range(9):
        if board[i][j] == test:
            return True
    return False

def vColumn(j, test):
    for i in range(9):
        if board[i][j] == test:
            return True
    return False

def vBlock(i, j, test):
    for I in range(3):
        for J in range(3):
            if(board[i+I][j + J] == test):
                return True
    return False

def validMove(i, j, test):
    if vColumn(j, test) == False and vBlock(i, j, test) == False and vLine(i, test) == False:
        return True
    else:
        return False

def solve():
    e = [0, 0]
    if checkEmpty() == False:
        return True
    i = e[0]
    j = e[1]
    for k in range(1, 10):
        if validMove(i, j, k) == True:
            board[i][j] = k
            if solve() == True:
                return True
            board[i][j] = 0
    return False

if solve():
    print("solved!")
else:
    print("No solution exists")

Проблема в том, что код внутри этой функции if validMove(i, j, k) == True:, кажется, никогда не выполняется. Однако я не смог найти ни одной ошибки в этой функции.

Кроме того, я на самом деле не знаю, должен ли я сделать отступ, отступ или оставить эту строку board[i][j] = 0 здесь.

Answer 1

Ваш блок проверки неверен - если вы введете 2,2,9, он не будет проверять правильный блок, но что-то сместится.

def vBlock(i, j, test):
    for I in range(3):
        for J in range(3):
            if(board[i+I][j + J] == test):   # checks 2-5. 2-5 row&col
                return True
    return False

Измените его на

def vBlock(i, j, test):
    for I in range(3):
        for J in range(3):
            if(board[i//3+I][j//3 + J] == test): # this way it cecks the blocks correctly 
                # if you input 2,2,9 it checks 2//3+range == 0+0-3 
                return True
    return False

Это не изменит общую ошибку, но компенсирует хотя бы одну ошибку.

---

Вы вернетесь в solve(), даже не изменив e -список строки / столбца, проверенных в данный момент - ваш solve() работает с локальной переменной e - ваш checkEmpty() изменяет global e, изменения никогда не отражаются внутри solve().

Fix:

def checkEmpty():
    global e        # explicitly use the global e
    for i in range(0, 9):
        for j in range(0, 9):
            if board[i][j] == 0:
                e[0] = i
                e[1] = j
                return True
    return False

def solve():
    global e        # explicitly use the global e
    if checkEmpty() == False:
        return True
    i = e[0]
    j = e[1]
    print(e)
    for k in range(1, 10): 
        if validMove(i, j, k) == True:
            board[i][j] = k
            if solve() == True:
                return True
            board[i][j] = 0

    return False

---

Даже если вы исправите эти 2 ошибки:

Вы должны быть в состоянии отбросить более ранние находки, т.е. в начале одно пространство может быть заполнено 9,1,3,4 - сначала вы проверяете 1 - бинго - вставьте его, но позже столкнетесь с проблемами из-за места в этом блоке, которое могло удерживать только 1. Теперь 1 отдан, и у вас нет решения.

Вы должны сначала вычислить «все возможные» числа для всех ваших 0, затем заполнить их с единственной возможностью, удалив это число из соответствующих списков строк / столбцов / блоков 0 и продолжить, пока все заполнены.

Итог: решение проблемы с использованием первого доступного варианта может привести к тому, что вы получите локальное минимальное значение, которое решает 10 из 12 оставшихся нулей, и тогда вы застряли.