对于一项任务,我负责使用Matlab和递归来设计NQueens算法。所以我设置它的方式是我有2个辅助函数isValid,它测试有效的位置,以及递归Queue,它从0的MxM板放置或移除一个皇后,并添加一个或从每一个可能的移动中删除1可以使。为了空间的缘故,我从recursiveQueen函数中删除了add函数,但它所做的只是在8个方向上加1或减1。Matlab NQueens算法递归
我遇到的主要问题是在我的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