八N皇后问题

1 问题的提出

在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法
 

我们的任务就是用MATLAB进行求解

2 数学模型的构建

首先我们分析题目就是
任意两个皇后都不能处于同一行、同一列或同一斜线上

global board sum;
board = zeros(8,8);
sum = 0;
dfs(1);
disp(sum);function dfs(x)global board sum;if x > 8sum = sum + 1;return;endfor i = 1:8if issafe(x,i,board)board(x,i) = 1;dfs(x+1);board(x,i) = 0;endend
endfunction safe = issafe(row, col, board)safe = true;% 检查列for i = 1:row-1if board(i, col) == 1safe = false;return;endend% 检查右上角i = row - 1;j = col + 1;while i >= 1 && j <= 8if board(i, j) == 1safe = false;return;endi = i - 1;j = j + 1;end% 检查左上角i = row - 1;j = col - 1;while i >= 1 && j >= 1if board(i, j) == 1safe = false;return;endi = i - 1;j = j - 1;end
end

我们要学习这里面的思想

3 模块1 dfs搜索函数

function dfs(x)global board sum;if x > 8sum = sum + 1;return;endfor i = 1:8if issafe(x,i,board)board(x,i) = 1;dfs(x+1);board(x,i) = 0;endend
end

我们有8个皇后，那就是for循环循环8行，每次放置一个棋子就进行一次判断，然后判断这个棋子可不可以落在这里如过可以那么久进入到下一行，x进行+1秒如果不可以的话，那么就进入这一行的下一个格子下一个，这就是枚举8行8列
当这个x > 8的话，那么就是放置成功了

4 检查模块

function safe = issafe(row, col, board)safe = true;% 检查列for i = 1:row-1if board(i, col) == 1safe = false;return;endend% 检查右上角i = row - 1;j = col + 1;while i >= 1 && j <= 8if board(i, j) == 1safe = false;return;endi = i - 1;j = j + 1;end% 检查左上角i = row - 1;j = col - 1;while i >= 1 && j >= 1if board(i, j) == 1safe = false;return;endi = i - 1;j = j - 1;end
end

首先我们的行是已经操作完的了，就是在判断行的话是在递归的过程中进行讨论的，然后就是只需要判断这个列是否成立就好了，然后斜边的话，那不就是直接判断左上角和右上角就好了
左上角和右上角的检查

    % 检查右上角i = row - 1;j = col + 1;while i >= 1 && j <= 8if board(i, j) == 1safe = false;return;endi = i - 1;j = j + 1;end

我们知道右上角就是不断的进行加1嘛，这个行的话，列就是不断地进行减1，左上角就是反着地