課題として、Matlab と再帰を使用して NQueens アルゴリズムを考案する任務がありました。したがって、私が設定した方法は、有効な配置をテストする2つのヘルパー関数isValidと、0のMxMボードからクイーンを配置または削除し、クイーンの可能なすべての動きから1を追加または削除するrecursiveQueenを持っていることです作れます。スペースの都合上、recursiveQueen 関数から加算関数を削除しましたが、8 方向で 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