Matlab 递归求解八皇后问题

qibbxxt

以前写过一个枚举法求解八皇后问题的程序，今天再写一个递归求解的程序

1. function Queens
   
2. % 8皇后问题的递归法求解
   
3. sol = 1; % 解的个数
   
4. queen = zeros(8); % 8*8的棋盘
   
5. saferows = true(1,8); % 用来表示每一行是否是安全位置
   
6. safeleftdiag = true(1,15); % 用来表示左对角是否安全，在同一个左对角上的元素满足i1+j1 = i2 + j2;
   
7. saferightdiag = true(1,15);% 用来表示左对角是否安全，在同一个右对角上的元素满足i1-j1 = i2 - j2;
   
8. trycol(1); % 检查第一列是否可以放置皇后
   
9. % 该函数用来检查第col列是否可以方位皇后
   
10.     function trycol(col)
    
11.         % 对行循环，一行一行的去放
    
12.         for row = 1 : 8
    
13.             % 检查第row行第col列的位置是否安全
    
14.             if safe(row,col)
    
15.                 % 如果安全，该位置被占据,该行和对角不安全
    
16.                 [saferows(row),safeleftdiag(row + col - 1),saferightdiag(row - col + 8)]=deal(false);
    
17.                 queen(row,col) = 1;
    
18.                 % 如果是第8列，说明解完成，输出
    
19.                 if col == 8
    
20.                     fprintf('第%d个解\n',sol);
    
21.                     disp(queen);
    
22.                     sol = sol + 1;
    
23.                 else % 否则，去试探下一列
    
24.                     trycol(col + 1);
    
25.                 end
    
26.                 % 判断完该行，就去判断下一行，应该清除该行的占据信息和安全信息
    
27.                 [saferows(row),safeleftdiag(row + col - 1),saferightdiag(row - col + 8)]=deal(true);
    
28.                 queen(row,col) = 0;
    
29.             end
    
30.             
    
31.         end
    
32.     end
    
33. % 该函数用来检查第row行第col列的位置是否安全
    
34.     function y = safe(row,col)
    
35.         % 检查该列的行，左对角，右对角是否安全
    
36.         y = saferows(row) & safeleftdiag(row + col - 1) & saferightdiag(row - col + 8);
    
37.     end
    
38. end
    

复制代码