Блог

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

Моя структура платы следующая: у меня есть список списка размером 6 на 6, каждый элемент подсписка представляет собой другой список со всеми возможностями от 1 до 6. Когда у меня есть список длиной 1, это означает, что элемент внутри является единственной возможностью, и поэтому он становится int . Пример строки на доске размером 3 * 3: row = [[1,2] , [1,2] , 3] (конечно, в этом примере на доске будет еще 2 строки)

Вот что у меня есть до сих пор, я не понимаю, почему это не работает.

 def search(searchBoard, clues):
    print_board(searchBoard)
    if not full(searchBoard):
        return searchBoard
    row, col = full(searchBoard)
    for i in searchBoard[row][col]:
        next_board = copy.deepcopy(searchBoard)
        next_board[row][col] = i
        if valid(next_board, clues , i , (row,col)):
            search(recElim(next_board , 6), clues)
    return False

def valid(board, clues, num, pos):
    row = [num if i == pos[1] else board[pos[0]][i] for i in range(6)]
    col = [num if i == pos[0] else board[i][pos[1]] for i in range(6)]

    if row.count(num) > 1:
        return False
    if col.count(num) > 1:
        return False

    clue = clues[pos[1]]
    if clue != 0 and clue not in make_permutations(col):
        return False

    clue = clues[pos[0]   6]
    if clue != 0 and clue not in make_permutations(row[::-1]):
        return False

    clue = clues[::-1][pos[1]   6]
    if clue != 0 and clue not in make_permutations(col[::-1]):
        return False

    clue = clues[::-1][pos[0]]
    if clue != 0 and clue not in make_permutations(row):
        return False

    return True
 

Поиск: Поиск — моя основная функция обратного отслеживания.

Допустимо: допустимо проверяет, является ли новая строка с вставленным целым числом допустимой или нет.

Полный: полный проверяет, есть ли еще элементы для размещения на доске или нет, если нет, он возвращает None, в противном случае он возвращает кортеж (i , j) (координаты ячейки для заполнения)

Исправление: эта функция имеет 2 роли:

 1: Removes values from the list of possibilities if those values are already inserted in the row
2: If in a list of possibilities, there is one element that none of the other sublists have, then it inserts that element
 

make_permutations : Наконец, эта функция возвращает все возможные подсказки, которые действительны в зависимости от строки

Во время отладки моя функция, похоже, выполняет все перестановки (даже находит правильный ответ), но просто продолжает, пока не выполнит все из них. Затем он возвращает плату без изменений. Я бы хотел, чтобы он находил и возвращал правильный ответ без вычисления всех других перестановок