hhbhhy 发表于 2016-3-15 22:32

自己编的8皇后问题求解

八皇后问题描述:在国际象棋盘中,8*8格,放置8个皇后,使得每行,每列,每对角斜线上都只有一个皇后。问一共有多少种可能的排布方法。

程序如下,高手指点!


%N个皇后排座问题
N=8;
%方案个数
M=0;

%以一为不可使用位置。
for i1=1:N
       %初始化
       huanghou=zeros(N,N);
       %设定第一位皇后位置
       huanghou(i1,1)=1;
       %列可以不管,设置本行后面元素全为1,
       huanghou(i1,:)=1;
       %对角排除不可放的位置
       %斜向上
       if i1>1
         for g1=1:i1-1;
               huanghou(i1-g1,1+g1)=1;
         end
       end
       %斜向下
       for g1=1:N-i1
         huanghou(i1+g1,1+g1)=1;
       end

       %第二步,与第一步类似。
       for i2=1:N
          %承接第一步的结果
          huanghou2=huanghou;
          %如果本列相加为维数N,说明没有位置可放皇后,则这种方案放弃,直接返回第一步。
          if sum(huanghou2(:,2))==N
            break;
          end
          %如果(i2,2)位置上为1,不可放皇后,则跳到下一个i2进行尝试。
          if huanghou2(i2,2)==1
            continue;
          end
          %找到第二个皇后的位置。下面与第一步相同,不再解释。
          huanghou2(i2,2)=2;
          huanghou2(i2,3:N)=1;
         if i2>1
               for g1=1:min(N-2,i2-1);
                  huanghou2(i2-g1,2+g1)=1;
               end
         end
          for g1=1:min(N-i2,N-2)
         huanghou2(i2+g1,2+g1)=1;
          end

         

         %第三步         
         for i3=1:N
          huanghou3=huanghou2;
          if sum(huanghou3(:,3))==N
            break;
          end
          if huanghou3(i3,3)==1
            continue;
          end
          huanghou3(i3,3)=3;
          huanghou3(i3,4:N)=1;
         if i3>1
               for g1=1:min(N-3,i3-1);
                  huanghou3(i3-g1,3+g1)=1;
               end
         end
          for g1=1:min(N-i3,N-3)
         huanghou3(i3+g1,3+g1)=1;
          end

         %第四步         
         for i4=1:N
          huanghou4=huanghou3;
          if sum(huanghou4(:,4))==N
            break;
          end
          if huanghou4(i4,4)==1
            continue;
          end
          huanghou4(i4,4)=4;
          huanghou4(i4,5:N)=1;
         if i4>1
               for g1=1:min(N-4,i4-1);
                  huanghou4(i4-g1,4+g1)=1;
               end
         end
          for g1=1:min(N-i4,N-4)
         huanghou4(i4+g1,4+g1)=1;
          end

         %第五步         
         for i5=1:N
          huanghou5=huanghou4;
          if sum(huanghou5(:,5))==N
            break;
          end
          if huanghou5(i5,5)==1
            continue;
          end
          huanghou5(i5,5)=5;
          huanghou5(i5,6:N)=1;
         if i5>1
               for g1=1:min(N-5,i5-1);
                  huanghou5(i5-g1,5+g1)=1;
               end
         end
          for g1=1:min(N-i5,N-5)
         huanghou5(i5+g1,5+g1)=1;
          end


         %第六步         
         for i6=1:N
          huanghou6=huanghou5;
          if sum(huanghou6(:,6))==N
            break;
          end
          if huanghou6(i6,6)==1
            continue;
          end
          huanghou6(i6,6)=6;
          huanghou6(i6,7:N)=1;
         if i6>1
               for g1=1:min(N-6,i6-1);
                  huanghou6(i6-g1,6+g1)=1;
               end
         end
          for g1=1:min(N-i6,N-6)
         huanghou6(i6+g1,6+g1)=1;
          end

         %第七步         
         for i7=1:N
          huanghou7=huanghou6;
          if sum(huanghou7(:,7))==N
            break;
          end
          if huanghou7(i7,7)==1
            continue;
          end
          huanghou7(i7,7)=7;
          huanghou7(i7,8:N)=1;
         if i7>1
               for g1=1:min(N-7,i7-1);
                  huanghou7(i7-g1,7+g1)=1;
               end
         end
          for g1=1:min(N-i7,N-7)
         huanghou7(i7+g1,7+g1)=1;
          end
         

         %最后一步         
         for i8=1:N
          huanghou8=huanghou7;
          if sum(huanghou8(:,8))==N
            break;
          end
          if huanghou8(i8,8)==1
            continue;
          end
          %找到最后一个皇后的位置
          huanghou8(i8,8)=8;
          M=M+1;
          %输出:
          disp(['第' num2str(M) '个方案'])
          huanghou8





%最后一步结束
end


%第七步结束
end


%第六步结束
end



%第五步结束
end

%第四步结束

end



%第三步结束
end

         
         
         
%第二步结束      
         
end





   


%第一步结束
end


页: [1]
查看完整版本: 自己编的8皇后问题求解