八皇后——穷举法

《八皇后——穷举法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、利用穷举解法来解决八皇后问题。    由于棋盘的对称性，第一行只考虑前四列的情况，然后逐行查找可行点，计算出结果后，总的解法数即是计算结果的两倍，而后四列的情况也即是前四列结果关于垂直线的对称。源程序如下：1.public class EightQueens {2.    int answer=0;       //结果数3.    int chess[][]=new int[8][8];//棋盘4.    EightQueens() {5.        int i=0,j=0,k=0;6.        //取半个棋盘计算结

2、果，最后结果*27.        for(k=0;k<4;k++) {8.            //棋盘初始化为09.            for(i=0;i<8;i++) {10.                for(j=0;j<8;j++)11.                    chess[i][j]=0;12.            }13.            //第一行14.            chess[0][k]=1;15.            row(1);16.        }17.  

3、      System.out.println("八皇后问题共有"+answer+"种解法");18.    }19.    public void row(int I) {20.        int i=0,j=0;21.        for(j=0;j<8;j++) {22.            //重新初始化行23.            for(i=I;i<8;i++) {24.                if(sum(i)>0) {25.                    for(int k=0;k<8

4、;k++) {26.                        chess[i][k]=0;27.                    }28.                }29.            }1.            if(sum1(j)==0&&sum2(I,j)==0) {2.                chess[I][j]=1;3.                if(I==7) {4.                    answer+=2;5.                    /

5、/输出结果，棋盘以数组形式表示6.                    /*for(int a=0;a<8;a++) {7.                        for(int b=0;b<8;b++) {8.                            System.out.println("解法"+answer+":");9.                            System.out.print(chess[a][b]+" ");10.                        }

6、11.                        System.out.println();12.                    }13.                    System.out.println();14.                  */15.                 /*for(int a=0;a<8;a++) {16.                    for(int b=0;b<8;b++) {17.                        System.out.p

7、rintln("解法"+(answer+1)+":");18.                        System.out.print(chess[a][7-b]+" ");19.                    }20.                    System.out.println();21.                }22.                System.out.println();23.                */24.                }25.    

8、            else row(I+1);26.            }27.        }28.    }29.    //计算行值30.    public int sum(int i) {31.        int j=0,s=0;32.