N_QUEEN

发表于   |   分类于   |     |  
  |  

通过递归实现求解N皇后问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import java.util.Scanner;
public class N_Queen {  
   private  int n;  
   private  int[] val;  
   public N_Queen(int n2) {
   		n=n2;
   		val = new int[n2];
}
/** 
    * 确定r行已放置的皇后是否可以 
    * @param r:行号 
    */  
   public boolean isPlace(int r){  
       boolean b = true;  
       for(int i = 0; i < r; i++){  
           if(val[r]==val[i]||Math.abs(val[r]-val[i])==Math.abs(r-i)){  
               b = false;  
               break;  
           }  
       }  
       return b;  
   }  
   /** 
    * 递归法实现N皇后问题,确定每一行皇后放置位置 
    * @param r：行号,从0到n-1 
    */  
   public void traceBackQueen(int r) {  
       if (r == n) {  
           print();  
       }else {  
           for (int i = 0; i < n; i++) {  
               val[r] = i;  
               if (isPlace(r)) {  
                   traceBackQueen(r+1);  
               }  
           }  
       }  
   }  
     
   /** 
    * 打印结果 
    */  
   public void print(){  
       for (int i = 0; i < n; i++) {  
           for (int j = 0; j < n; j++) {  
               if (j == val[i]) {  
                   System.out.print("1"+"  ");  
                   continue;
               }  
               System.out.print("0"+"  ");
           }
           System.out.println();
       }  
       System.out.println();  
   }  
     
   /* 
    * test 
    */  
   public static void main(String[] args){  
   	@SuppressWarnings("resource")
	Scanner input = new Scanner(System.in);
   	System.out.println("请输入皇后的数量:");
   	int n = input.nextInt();
       N_Queen queen = new N_Queen(n);  
      	queen.traceBackQueen(0);  
   }  
   }

运行结果截图：
"yunxingjietu"