[目前，我正在研究一个我认为非常有趣的问题。问题如下：
Given a chess board with N rows and N columns,
what is the maximum number of knights you could place on the board
so that no knight can be attacked by another knight?
[过去，我已经使用回溯解决了soduku问题，我认为我也可以将回溯应用于此类问题。我当前的思考过程是：
1. Check if the current space that I am looking at is free from attack
2. If the space is free from attack, place a knight and calculate the maximum number of knights
3. Backtrack, remove the knight, and calculate the maximum number of knights
4. If the total number after placing the knight is >= the total number after removing the knight, place the knight again
5. Go to the next space
我已经写了一些代码，但是，我不确定我是否正确实现了该代码，或者我的逻辑是否正确
GRID_DIMENSION = 3
def is_safe(board, position):
x,y = position
if((x-2) >= 0 and (y-1) >= 0 and board[x-2][y-1] == 1):
return False
if((x-2) >= 0 and (y+1) < GRID_DIMENSION and board[x-2][y+1] == 1):
return False
if((x+2) < GRID_DIMENSION and (y-1) >= 0 and board[x+2][y-1] == 1):
return False
if((x+2) < GRID_DIMENSION and (y+1) < GRID_DIMENSION and board[x+2][y+1] == 1):
return False
if((x-1) >= 0 and (y-2) >= 0 and board[x-1][y-2] == 1):
return False
if((x-1) >= 0 and (y+2) < GRID_DIMENSION and board[x-1][y+2] == 1):
return False
if((x+1) < GRID_DIMENSION and (y-2) >= 0 and board[x+1][y-2] == 1):
return False
if((x+1) < GRID_DIMENSION and (y+2) < GRID_DIMENSION and board[x+1][y+2] == 1):
return False
return True
def count_knights(board):
total = 0
for i in range(GRID_DIMENSION):
for j in range(GRID_DIMENSION):
if board[i][j] == 1:
total = total + 1
return total
def calc_knights_backtracking(board, i, j):
if i < 0 or i >= GRID_DIMENSION:
return
if j < 0 or j >= GRID_DIMENSION:
return
# check if the spot is safe from attacks
if(is_safe(board, (i,j))):
# place a knight and continue to end of board
board[i][j] = 1
if j+1 < GRID_DIMENSION:
calc_knights_backtracking(board, i, j+1)
else:
calc_knights_backtracking(board, i+1, j)
# get the total number of knights
totalPlaced = count_knights(board)
# remove the knight from (i,j) and go through rest of board
board[i][j] = 0
if j+1 < GRID_DIMENSION:
calc_knights_backtracking(board, i, j+1)
else:
calc_knights_backtracking(board, i+1, j)
# get the total number of knights
totalUnplaced = count_knights(board)
# compare the two
if totalPlaced >= totalUnplaced:
board[i][j] = 1
else:
if j+1 < GRID_DIMENSION:
calc_knights_backtracking(board, i, j+1)
else:
calc_knights_backtracking(board, i+1, j)
board = [[0 for i in range(GRID_DIMENSION)] for j in range(GRID_DIMENSION)]
calc_knights_backtracking(board, 0, 0)
此代码示例未向我返回具有最大骑士数的正确板配置。我在做什么错？
我也在学习回溯，所以我尝试做这个问题。我认为您的流程很好。但这与N-Queens略有不同。对于N皇后，我们只能逐行检查，因为连续只有一个皇后。但是对于Knight，我们可以在同一行中放置多个骑士。因此，我们必须检查网格中的每个条目。这是我的代码：
import itertools
def solveNKnights(n):
board = [['.']*n for _ in range(n)]
# all positions of the board
pos = [p for p in itertools.product(range(n), repeat=2)]
# index 0 is the number of knights, index 1 is the board
res = [0, None]
backtrack(board, pos, res)
return res
def isValid(board, p):
# all attack positions
arr = [(-2, -1), (-1, -2), (1, -2), (2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1)]
for tup in arr:
newi = p[0]+tup[0]
newj = p[1]+tup[1]
if 0 <= newi < len(board) and 0 <= newj < len(board[0]):
if board[newi][newj] == 'K': return False
return True
def backtrack(board, pos, res):
if len(pos) == 0:
# count K in the current board
ks = sum(i.count('K') for i in board)
res[0] = max(res[0], ks)
# save the board if it has the maximum K so far
if res[0] == ks:
res[1] = [x[:] for x in board]
return
for i in range(len(pos)):
if not isValid(board, pos[i]):
continue
board[pos[i][0]][pos[i][1]] = 'K'
backtrack(board, pos[i+1:], res)
board[pos[i][0]][pos[i][1]] = '.'
res = solveNKnights(3)
print(res[0])
print(res[1])