Для задания мне было поручено разработать алгоритм NQueens с использованием Matlab и рекурсии. Так что я установил его, у меня есть 2 вспомогательных функции isValid, которые проверяют правильное размещение и recursiveQueen, который помещает или удаляет королеву из платы MxM из 0 и добавляет одну или удаляет 1 из всех возможных действий королевы можно сделать. Для пространства я удалил функции add из функции recursiveQueen, но все, что он делает, это добавить или вычесть 1 в 8 направлениях.Рекурсия алгоритма 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