对于作业，我的任务是使用Matlab和递归设计NQueens算法 . 所以我设置它的方式是我有2个辅助函数isValid，它测试有效放置，recursiveQueen，它从0的MxM板放置或删除一个女王，并从每个可能的移动中添加一个或删除1可以使 . 为了节省空间，我从recursiveQueen函数中删除了add函数，但它只是在8个方向上加1或减1 .
我遇到的主要问题是在我的solveNQ函数中，如果找不到前一行的解，则将其转到下一列 . 我已经把我的步骤分解为6件事：
1）在第一行放置一个女王
2）将一个女王放在下一行的下一个有效位置
3）重复步骤2，直到找不到行的有效位置
4）从最后一行删除女王
5）将女王放在行的下一个有效位置
6）重复步骤1-5，直到所有行都包含一个女王（我没有编写此步骤）
function out = NQueens(m) %main function
board = zeros(m,m); %intializes board
out = solveNQ(1,board) %recursive function
end
function out = solveNQ(col,board)
n = length(board);
out = false; %returns false if no solutions found
if col > n
else
for i = col:n
for j = 1:n
if isValid(board,i,j)
board = recursiveQueen(board,i,j,'place') %place queen
out = solveNQ(col+1,board) %recursive call
end
end
board = recursiveQueen(board,i-1,col,'remove') %if no valid placement for row
out = solveNQ(col-1,board) %try again
end
end
end
function out = isValid(board,row,col)
if board(row,col) == 0
out = true;
else
out = false;
end
function board = recursiveQueen(board,row,col,move)
board = goRight(board,row,col,move); %right
board = goLeft(board,row,col,move); %left
board = goDown(board,row,col,move); %down
board = goUp(board,row,col,move); %up
board = goRightUp(board,row,col,move); %diagnol up right
board = goLeftUp(board,row,col,move); %diagnol up left
board = goRightDown(board,row,col,move); %diagnol right down
board = goLeftDown(board,row,col,move); %diagnol left down
if strcmp(move,'place') %places queen
board(row,col) = -1;
elseif strcmp(move,'remove') %removes queen
board(row,col) = 0;
end
end
1 回答
您不需要j =的第二个循环，因为您的col 1将允许您移动到下一列 .
我的概念如下
1）在左上角放置一个女王
2）移动到下一列并将一个皇后放在有效位置
3）重复步骤2，所以现在我们在第3列 . 如果你不能在那里放任何女王，那么删除前一个女王 . 当前代码的主要问题可以通过在if语句中移动queen删除来解决 . 这背后的逻辑是，当不能在该列中放置任何皇后时，for循环将在没有实际执行任何操作的情况下运行（因为isValid为false） . 当for循环（这是for循环INSIDE递归）停止运行时，MATLAB将从先前停止的位置拾取，这是你的clone solveNQ，并跳转到下一行，你应该删除你的后代 .
不要忘记，如果n> col，这意味着你可以将N皇后放在棋盘上，你的输出就是真的 .
我不得不让一个朋友帮我解决这个问题 . 如果我的解释不好，请随时回复 .