N皇后问题

- 日理万妓 2022-06-16 12:41 197阅读 0赞

题目:

请设计一种算法，解决著名的n皇后问题。这里的n皇后问题指在一个nxn的棋盘上放置n个棋子，使得每行每列和每条对角线上都只有一个棋子，求其摆放的方法数。给定一个int n，请返回方法数，保证n小于等于15

测试样例：1 返回：1

最初的想法是构造一个二维数组的数据结构,然后穷举所有可能的情况,按照这个思路写了一坨东西,最后实在是不忍直视,于是参照网上的一些思路,自己实现了一下。

首先,并不是采用二维数组这种数据结构,而是采用了一维数组的方式,构造一个position数组,代表棋盘上的一行,比如position\[i\],代表第i行,postion\[i\]列，随后先固定一行,接着对列进行试探,  
伪代码如下:

void queen(int row)
     {
        if (n == row)      //如果已经找到结果，则打印结果
        print_result();
        else {
               for (k=0 to N) { //试探第row行每一个列
              if (can_place(row, k) { 
              place(row, k);   //放置皇后
              queen(row + 1);  //继续探测下一行
               }
            }
          }
     }

下面是具体的实现代码；

public class Queues {
        public int nQueens(int n) {
            // write code here
            if (n<=0){
                return -1;
            }
            int[] position=new int[n];//position[i]表示第i行皇后的列号
            return place(position,0,n);
        }
    
        private int place(int[] position, int i, int n) {
            if (i==n){
                return  1;
            }
            int count=0;
            for(int j=0;j<n;j++){
                if(isvalid(position,i,j)){//如果当前的位置是有效的
                    position[i]=j;
                    count+=place(position,i+1,n);//往下挪一行
                }
            }
            return count;
        }
    
        private boolean isvalid(int[] position, int i, int j) {
            for(int k=0;k<i;k++){//因为是对当前的位置进行判断，所以要对前面的i行数据进行校验
                if ((j==position[k])||(Math.abs(position[k]-j)==Math.abs(i-k))){//如果同在一个列
                    return false;
                }
            }
            return true;
        }
    }