I need some help to find an algorithm that will solve the following problem.

Given the 2d board and target values for rows/columns, the sum of rows/columns should be equal to these target values. It can be achieved by setting a board value to 0.

In my case I have the following board:

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]
]

With the following values for rows [24,13,15,8,12], and the following values for columns [8,11,13,18,22].

As a result, the board should look like this:

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]
]

For now, my code looks like this:

# 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

I tried to implement the following here:

1. Select a cell.
2. Set the value to zero.
3. Go recursively and try to solve the board.
   • If the board is not solved, then backtrack and set the board element to the previous value. Go recursively and try to solve the board for that value.
   • If the board is solved, return True.

CodePudding user response：

This constraint problem can be solved with backtracking pretty much the same way as Sudoku or other 2-d grid puzzles. The main change is coding up a different set of constraints for when the board is solved as well as determining when an unsatisfiable state is reached where backtracking should occur.

In your code, visited[x][y] = 1 is set, but never undone. So when you backtrack, parent states are corrupted. The rule with backtracking (and most recursive algorithms) is that before you pop the call stack (i.e. return from a function), you have to leave your state exactly as it was when you pushed the call onto the stack. If you keep track of the indices, there's no need for the visited list.

This seems to run pretty fast for this size of problem even with a naive backtracking mechanism (while iterating rowwise, if the current row is ever less than the expected value of the row, bail out and backtrack; this assumes no negative numbers).

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

If you want to speed it up or generalize to negative values, add checks for violations on the bound of possible results per row (and possibly columns for the last row). If you've checked results along the way, you can skip checking that at the end and save some work too.

While iterating, you find you've met the target sum for a row, you can immediately move on to the next one.

You could also plug this into a LP solver like PuLP.