递归求解网格的算法

Question

我需要一些帮助来找到解决以下问题的算法。

给定 rows/columns 的 2d 板和目标值，rows/columns 的总和应等于这些目标值。可以通过将板值设置为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

我尝试在此处实现以下内容：

Select一个单元格。
将值设置为零。
递归尝试解决棋盘问题。
- 如果没有解出棋盘，则回溯，将棋盘元素设置为之前的值。递归地尝试解决该值的问题。
- 如果棋盘已解决，return正确。

Answer 1

此 constraint problem can be solved with backtracking pretty much the same way as Sudoku 或其他二维网格拼图。主要的变化是编写一组不同的约束，用于确定何时解决电路板以及确定何时达到应发生回溯的不可满足状态。

在您的代码中，visited[x][y] = 1 已设置，但从未撤消。因此，当您回溯时，父状态已损坏。回溯（和大多数递归算法）的规则是，在弹出调用堆栈（即从函数中 return ）之前，您必须完全保持将调用压入堆栈时的状态。如果您跟踪索引，则不需要访问列表。

对于这种规模的问题，这似乎运行相当快，即使使用简单的回溯机制也是如此（在逐行迭代时，如果当前行小于该行的预期值，则退出并回溯; 这假设没有负数）。

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

如果您想加快速度或将其归纳为负值，请在每行（可能还有最后一行的列）的可能结果边界上添加违规检查。如果您一直检查结果，则可以跳过最后的检查并节省一些工作。

在迭代的过程中，你发现你已经达到了一行的目标总和，你可以立即进入下一个。

您也可以将其插入 LP 求解器，例如 PuLP。

递归求解网格的算法

Algorithm for recursively solving the grid

python

grid

recursion

multidimensional-array