Блог

У меня возникли проблемы с адаптацией решателя судоку отсюдаhttps://techwithtim.net/tutorials/python-programming/sudoku-solver-backtracking / для включения диагонального ограничения

Это исходный код:

 board = [
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0]
]

def solve(bo):
    find = find_empty(bo)
    if not find:
        return True
    else:
        row, col = find

    for i in range(1,10):
        if valid(bo, i, (row, col)):
            bo[row][col] = i

            if solve(bo):
                return True

            bo[row][col] = 0

    return False


def valid(bo, num, pos):
    
    # Check row
    for i in range(len(bo[0])):
        if bo[pos[0]][i] == num and pos[1] != i:
            return False

    # Check column
    for i in range(len(bo)):
        if bo[i][pos[1]] == num and pos[0] != i:
            return False

    # Check box
    box_x = pos[1] // 3
    box_y = pos[0] // 3

    for i in range(box_y*3, box_y*3   3):
        for j in range(box_x * 3, box_x*3   3):
            if bo[i][j] == num and (i,j) != pos:
                return False
                
    return True


def print_board(bo):
    for i in range(len(bo)):
        if i % 3 == 0 and i != 0:
            print("- - - - - - - - - - - - - ")

        for j in range(len(bo[0])):
            if j % 3 == 0 and j != 0:
                print(" | ", end="")

            if j == 8:
                print(bo[i][j])
            else:
                print(str(bo[i][j])   " ", end="")


def find_empty(bo):
    for i in range(len(bo)):
        for j in range(len(bo[0])):
            if bo[i][j] == 0:
                return (i, j)  # row, col

    return None

print_board(board)
solve(board)
print("______________________")
print_board(board)
  

Теперь это пустая доска, на ней, очевидно, есть почти бесконечное количество допустимых решений, и код просто вернет первое найденное, но он также быстро найдет уникальное решение, когда вы введете несколько реальных чисел.

В качестве проблемы с кодированием я решил посмотреть, могу ли я добавить диагональное ограничение: т. е. ни одно число не повторяется в bo [i] [i] от i = 0 до i = 8 включительно (т. е. диапазон (0,9) или range (9) — смотрите, я знаю некоторый код!)

Итак, это казалось довольно простым — мне просто нужно добавить дополнительный цикл в действительную функцию — насколько это может быть сложно?

Я пытался:

 for i in range(9):
        if bo[i][i] == num and (i,i) != pos:
            return False
  

и множество подобных его вариаций — и поэтому такая удача. Я не могу заставить это работать. Для этого варианта кажется, что он выполняется вечно, но если вы введете, скажем

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

Которое должно легко возвращать допустимое диагональное решение судоку — оно просто возвращает ту же введенную доску, что и «решение», т. Е. с 72 пустыми ячейками!

Очевидно, мне не хватает чего-то очень простого, но я схожу с ума, выясняя, что это такое.

Я новичок в python, и это мой первый пост здесь — поэтому приношу извинения, если мой этикет на форуме неправильный. Я ценю все отзывы!

Спасибо!

редактировать: ОК. У меня есть решение, которое почти работает, но я хотел бы знать, почему есть одно исключение, и я все еще хотел бы знать, почему мой оригинал этого не сделал. Вот что я сделал

Первый:

 def main_diagonal(bo):
    main_diagonal = []
    for i in range(0,9):
        main_diagonal  = str(bo[i][i])
    for i in range(0,9):
        main_diagonal[i] = int(main_diagonal[i])
    return main_diagonal
  

Затем в пределах допустимой функции добавьте:

 for i in range(1,10):
        if main_diagonal(bo).count(i) > 1:
            return False
  

Теперь это очень хорошо помогает остановить повторение чисел по диагоналям, однако есть исключение! 81-я ячейка, то есть bo[8][8], которая появляется на главной диагонали, может содержать повторяющееся число. Может быть, это связано с тем, что исходный алгоритм предполагает (правильно), что если первые 80 ячеек допустимы, то и 81-я тоже, тогда как здесь это не так? Как мне устранить эту ошибку?

Этот способ подсчета, если количество появлений определенного числа больше 1, для меня гораздо более интуитивно понятен, чем исходный код, но мне все еще нужно узнать, почему моя первая попытка не сработала, чтобы не попасть в подобную ситуацию в дальнейшем.