遞回求解網格的演算法

我需要一些幫助來找到可以解決以下問題的演算法。

給定 2d 板和行/列的目標值，行/列的總和應等于這些目標值。可以通過將板值設定為 0 來實作。

就我而言，我有以下板：

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

使用以下行值[24,13,15,8,12]和以下列值[8,11,13,18,22]。

因此，董事會應如下所示：

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

現在，我的代碼如下所示：

# chooses a next cell 
def choose_cell(x,y,visited):
    for i in range(x,board_len):
        for j in range(y, board_len):
            if visited[i][j] == 0 and is_cell_valid(i,j):# if the cell is not visited and is valid => return i,j
                return i,j

    for i in range(0,board_len):
        for j in range(0, board_len):
            if visited[i][j] == 0 and is_cell_valid(i,j):
                return i,j
    return -1,-1

# checks if x,y are not out of board range
def is_cell_valid(x_coord, y_coord):
    if (x_coord < 0 or y_coord < 0) or (x_coord >= board_len or y_coord >= board_len):
        return False
    return True

def solve_board(x, y, visited):
    # if the sum of the row/column equals target row/column value => returns True
    if row_sum() == row_goal and col_sum() == col_goal:
        return True

    if x == -1:# if -1 is returned it means that the algorithm reached the end of a board
        return False

    x,y=choose_cell(x,y, visited)

    # mark the current board element as visited
    visited[x][y] = 1

    # save current board element for future use, put 0 in the board instead
    temp = board[x][y]
    board[x][y] = 0

    # that's where my mind goes blank
    if solve_board(x,y,visited) == False:
        board[x][y] = temp    
    if solve_board(x,y,visited):
        return True
    
    return False

我試圖在這里實作以下內容：

1. 選擇一個單元格。
2. 將值設定為零。
3. 遞回并嘗試解決董事會。
   • 如果棋盤未解決，則回溯并將棋盤元素設定為先前的值。遞回并嘗試解決該值的董事會。
   • 如果棋盤已解決，則回傳 True。

uj5u.com熱心網友回復：

這個約束問題可以通過與數獨或其他二維網格謎題幾乎相同的方式通過回溯來解決。主要的變化是撰寫一組不同的約束條件，用于解決電路板的問題，以及確定何時達到不可滿足的狀態，在那里應該發生回溯。

在您的代碼中，visited[x][y] = 1已設定，但永遠不會撤消。因此，當您回溯時，父狀態已損壞。回溯（以及大多數遞回演算法）的規則是，在彈出呼叫堆疊（即從函式回傳）之前，您必須完全保留將呼叫壓入堆疊時的狀態。如果您跟蹤索引，則不需要訪問串列。

即使使用簡單的回溯機制，對于這種規模的問題，這似乎也運行得非常快（在按行迭代時，如果當前行小于該行的預期值，則退出并回溯；這假設沒有負數）。

def all_sum(board, rows):
    return all(
        target_sum == sum(row)
        for target_sum, row in zip(rows, board)
    )
    
def solved(board, rows, cols):
    return (
        all_sum(board, rows) and
        all_sum(zip(*board[::-1]), cols)
    )

def solve(board, rows, cols, y=0, x=0):
    if y >= len(board):
        return solved(board, rows, cols)
    elif x >= len(board[y]):
        return solve(board, rows, cols, y   1, 0)
    elif sum(board[y]) < rows[y]:
        return False

    square_value = board[y][x]
    board[y][x] = 0

    if solve(board, rows, cols, y, x   1):
        return True

    board[y][x] = square_value
    return solve(board, rows, cols, y, x   1)

if __name__ == "__main__":
    board = [
        [5,9,4,6,1],
        [6,2,3,6,7],
        [3,4,8,4,4],
        [2,2,6,4,6],
        [7,3,1,6,5]
    ]
    rows = [24,13,15,8,12]
    cols = [8,11,13,18,22]
    expected_board = [
        [5,9,4,6,0],
        [0,0,0,6,7],
        [3,0,8,0,4],
        [0,2,0,0,6],
        [0,0,1,6,5]
    ]
    flat_board = [x for row in board for x in row]
    assert all(x >= 0 for x in flat_board   rows   cols)
    solve(board, rows, cols)
    assert board == expected_board

如果您想加快速度或推廣到負值，請在每行（可能還有最后一行的列）的可能結果范圍內添加違規檢查。如果您在此程序中檢查了結果，則可以跳過最后的檢查并節省一些作業。

在迭代時，您發現已達到一行的目標總和，您可以立即轉到下一個。

您也可以將其插入到像PuLP這樣的 LP 求解器中。

標籤：Python 递归 多维数组 网格

上一篇：如何解決遞回呼叫中的堆疊溢位錯誤？

下一篇：將多維陣列決議為完全指定的端點