(Java实现) N皇后问题

原文始发于：(Java实现) N皇后问题

n皇后问题是一个以国际象棋为背景的问题：在n×n的国际象棋棋盘上放置n个皇后，使得任何一个皇后都无法直接吃掉其他的皇后，即任意两个皇后都不能处于同一条横行、纵行或斜线上。

蛮力法思想：

---

解决n皇后问题的思想本质上就是蛮力法，生成所有可能的摆放情况，并判断该情况是否满足要求，我们以树结构来表示解决问题的方法。以4*4的棋盘为例，第0层的根节点为空白的棋盘，第1层为只在棋盘的第一行摆放的四种不同情况，第2层是在第1层的基础上，摆放第二行的棋子，最后的叶子结点便是所有可能的完整摆放情况，共256种，但加上中途生成的不完整情况共1+4+16+64+256=340种。

回溯法思想：

---

回溯法其实是以蛮力法为基础，只是不需要生成所有的情况，我们可以发现，在整棵树中，有些棋盘的摆放情况在未达到叶子结点时,便已经不满足n皇后的条件了，那么我们就没有必要再去往下摆放棋子（生成下一层的结点），而是直接回到该结点的父节点，生成新的情况进行判断。通过这种方法可以减少生成完全树中的一些不必要的子树，我们称之为“剪枝”。具体实现中回溯法与蛮力法的主要区别在于判断棋盘的代码所在的位置，蛮力法在摆放完所有皇后后再判断，回溯法在每摆放好一个皇后时就进行判断。

具体实现：

---

根据n皇后问题的规模，创建大小为n的数组代替树结构，使其下标代表行数，内容代表列数，数组中的每个数必定位于不同的行，数组内容不同证明两个元素位于不同的列，两数下标的差的绝对值不等于两数内容的差的绝对值，表示两数不位于同一斜线上。

import java.util.Arrays; import java.util.Scanner;   public class Nhuanghouwenti { 	   private static int queenNum;//皇后的个数   	    private static int[] hash;//下标表示i号皇后（皇后i放在第i行）value表示放的列号   	    private static int count = 0;//合法摆放方式的个数   	   	    public static void placeQueen(int m) {   	        if (m > queenNum) {//如果摆到了n+1行了，说明前n行都是不冲突的，合法的   	            count++;   	            for (int i = 1; i <=queenNum; i++) { 					System.out.print(hash[i]); 				} 	            System.out.println(); //	            System.out.println(Arrays.toString(hash));   	                        //打印合法的摆放结果   //	            for(int i = 1; i <= queenNum; i++){   //	                int column = hash[i];//hash值表示皇后i所在的列号   //	                for(int j = 1; j <= queenNum ;j++){   //	                    if(j!= column){   //	                        System.out.print("* ");   //	                    }else{   //	                        System.out.print("Q ");   //	                    }   //	                }   //	                System.out.println();   //	            }   	            return;   	        }   	        for (int i = 1; i <= queenNum; i++) {   	        //check the column is conflict with former ones or not   	        //if so, check the next column until find a non-conflict column    	                //or until the last column ,return;   	            if (isConfilct(m, i)) {    	                continue;   	            } else {//如果检测到第i列不冲突，是安全的，   	                hash[m] = i;//将皇后m放在第i列   	                placeQueen(m + 1);//再放皇后m+1,   	                //如果皇后m+1放完并返回了   	                //两种可能：   	                //1：冲突，返回了   	                //2.一直将所有的皇后全部放完并安全返回了   	                //将皇后m回溯，探索新的可能或者安全的位置   	                  hash[m] = -1;   	                //其实这里没必要将m重新赋值的，因为检测到下一个   	                //安全位置的时候会把hash[m]覆盖掉的   	                //但是为了更好的体现“回溯”的思想，在这里画蛇添足了   	            }   	        }   	    }   	    /**  	     * 检测冲突  	     * @param index  	     *            表示行号  	     * @param hash 表示第i行放置皇后的列数 	     *            值表示列号  	     * @return  	     */   	    private static boolean isConfilct(int row, int column) {  //一行一个皇后，第n个皇后也代表着第n行 	        if(row == 1){//第1行永远不会冲突   	            return false;   	        }   	        //只需要保证与那些已经就位的皇后不冲突即可   	        for (int i = 1; i < row; i++) {  //当前的行数 	            if (hash[i] == column || ( column - row) == (hash[i] - i) || (row - column)== (i-hash[i])   //以前行数减列数与现在的是否相等 	                || (row + column) == (hash[i] + i)) {   	                return true;   	            }   	        }   	        return false;   	    }   	    public static void main(String[] args) {   	        Scanner sc = new Scanner(System.in);   	        queenNum = sc.nextInt();   	        hash = new int[queenNum + 1];   	        for (int i = 0; i < hash.length; hash[i++] = -1);//初始化棋盘   	        placeQueen(1);   	        System.out.println(count);   	    }    }