蓝桥杯-八皇后

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种方法可以解决此问题。

public class 八皇后 {  
  
    public static int sum=0;  
      
      
    public static void main(String[] args) {  
        // TODO Auto-generated method stub  
        String[][] qiPan = new String[8][8];  
        int i, j;  
  
        for (i = 1; i <= 8; i++) {  
            for (j = 1; j <= 8; j++) {  
                if (i % 2 == 1) {  
                    if (j % 2 == 1) {  
                        qiPan[i-1][j-1] = "██";  
                    } else {  
                        qiPan[i-1][j-1] = "  ";  
                    }  
                } else {  
                    if (j % 2 == 0) {  
                          
                        qiPan[i-1][j-1] = "██";  
                    } else {  
                        qiPan[i-1][j-1] = "  ";  
                    }  
                }  
            }  
        }  
        Queen[] queens=new Queen[8];  
        for(i=0;i<8;i++){  
            queens[i]=new Queen();  
        }  
          
        search(queens,0);  
    }  
      
    public static void search(Queen[] queens,int n) {  
        Queen[] queenstemp=new Queen[8];  
        int i;  
          
        for(i=0;i<8;i++){  
            queenstemp[i]=new Queen();  
            queenstemp[i].location=queens[i].location;  
        }  
          
        if(n==8){  
            System.out.println("这是第"+(++sum)+"种摆法");  
            print(queenstemp);  
            System.out.println();  
        }else{  
            for(i=0;i<8;i++){  
                queenstemp[n].location=i;  
                if(isValid(queenstemp, n)){  
                    search(queenstemp, n+1);;  
                }  
            }  
        }  
    }  
      
    public static boolean isValid(Queen[] queens,int n) {  
        int i;  
        for(i=0;i<n;i++){  
            if(queens[i].location==queens[n].location){  
                return false;  
            }  
            if(Math.abs(queens[i].location-queens[n].location)==n-i){  
                return false;  
            }  
        }  
        return true;  
    }  
      
    public static void print(Queen[] queens) {  
          
        String[][] qiPan = new String[8][8];  
        int i, j;  
  
        for (i = 1; i <= 8; i++) {  
            for (j = 1; j <= 8; j++) {  
                if (i % 2 == 1) {  
                    if (j % 2 == 1) {  
                        qiPan[i-1][j-1] = "██";  
                    } else {  
                        qiPan[i-1][j-1] = "  ";  
                    }  
                } else {  
                    if (j % 2 == 0) {  
                          
                        qiPan[i-1][j-1] = "██";  
                    } else {  
                        qiPan[i-1][j-1] = "  ";  
                    }  
                }  
            }  
        }  
          
        for(i=0;i<8;i++){  
            qiPan[i][queens[i].location]="§§";  
        }  
          
        for (i = 1; i <= 8; i++) {  
            System.out.print("|");  
            for (j = 1; j <= 8; j++) {  
                System.out.print(qiPan[i-1][j-1]);  
            }  
            System.out.println("|");  
        }  
    }  
}  
  
class Queen{  
    int location=1;  
} 

输出示例：

输出截图.png