[ 資料結構 小學堂 ] 堆疊 : 堆疊應用 (八皇后問題) - Java 版本

範例代碼 : 

- Stack.java : 定義堆疊的介面

view plaincopy to clipboardprint?

1. package DSwJ.S14;  
2.   
3. public interface Stack{  
4.     public T peek();  
5.     public void push(T item);  
6.     public T pop();  
7.     public int size();  
8.     public boolean isEmpty();  
9. }  

- ALStack.java : 解法所使用的堆疊結構

view plaincopy to clipboardprint?

1. package DSwJ.S14;  
2.   
3. import java.util.ArrayList;  
4.   
5. public class ALStack implements Stack{  
6.     private ArrayList stackList = null;  
7.       
8.     public ALStack() {  
9.         stackList = new ArrayList();  
10.     }  
11.   
12.     public void clear(){stackList.clear();}  
13.     public String display(){  
14.         if(stackList.size()==0) return "[]";  
15.         StringBuffer sb = new StringBuffer("[");  
16.         sb.append(stackList.get(0));  
17.         for(int i=1; i
18.             sb.append(", "+stackList.get(i));  
19.         sb.append("]");  
20.         return sb.toString();  
21.     }  
22.     public void copyTo(ArrayList copy){  
23.         for(int i=0; i
24.     }  
25.     @Override  
26.     public T peek() {  
27.         if(stackList.size()==0) throw new EmptyStackException("Empty Stack");  
28.         return stackList.get(stackList.size()-1);  
29.     }  
30.   
31.     @Override  
32.     public T pop() {  
33.         if(stackList.size()==0) throw new EmptyStackException("Empty Stack");  
34.         return stackList.remove(stackList.size()-1);  
35.     }  
36.   
37.     @Override  
38.     public void push(T item) {  
39.         stackList.add(item);          
40.     }  
41.       
42.     @Override  
43.     public int size() {  
44.         return stackList.size();  
45.     }  
46.       
47.     @Override  
48.     public boolean isEmpty() {  
49.         return stackList.isEmpty();  
50.     }     
51. }  

- Queue8.java : 解題目的主程式

view plaincopy to clipboardprint?

1. package DSwJ.S14.apps;  
2.   
3. import java.util.ArrayList;  
4. import DSwJ.S14.ALStack;  
5.   
6. public class Queue8 {  
7.     private int col=0;  
8.     private int size=8;  
9.     private ALStack posStack = new ALStack();  
10.       
11.     public Queue8(int c){this();col = c;}  
12.     public Queue8(){}  
13.     public Queue8(int s, int c) {size=s; col=c;}  
14.       
15.     /** 
16.      * BD 回到上一個點的下一個不會遭受已存在皇后攻擊的點 
17.      * @return 
18.      */  
19.     protected boolean rollback(){         
20.         int tmp;  
21.         boolean flag = true;  
22.         do{  
23.             if(posStack.size()==0 || (posStack.size()==1 && posStack.peek()==size-1)) return false;  
24.             while((tmp=posStack.pop())==(size-1)){  
25.                 if(posStack.size()==0)return false;  
26.             };  
27.             for(int i=tmp+1; i
28.                 if(!attack(i)){                       
29.                     posStack.push(i);  
30.                     flag = false;  
31.                     break;  
32.                 }  
33.             }             
34.         }while(flag);  
35.         return true;  
36.     }  
37.       
38.     /** 
39.      * BD 檢查是否位置有遭已存在的皇后的攻擊. 如遭攻擊則返回 True.  
40.      * @param p 
41.      * @return 
42.      */  
43.     protected boolean attack(int p) {  
44.         if(posStack.size()==0) return false;  
45.         ArrayList copyList = new ArrayList();  
46.         posStack.copyTo(copyList); // 複製Stack 內容到 ArrayList copyList  
47.         int k;  
48.         for(int i=copyList.size()-1; i>=0; i--) {  
49.             k = copyList.get(i);  
50.             if(k==p||(k+copyList.size()-i)==p||(k-copyList.size()+i)==p) {  
51.                 return true;  
52.             }  
53.         }  
54.         return false;  
55.     }  
56.       
57.     /** 
58.      * BD 開始找尋Solution 
59.      * @return 
60.      */  
61.     protected boolean start() {  
62.         if(posStack.size()==size) { //Next solution  
63.             if(!rollback()){  
64.                 System.out.println("No more solution!");  
65.                 return false;  
66.             }  
67.             if(posStack.size() == size) return true;  
68.             else return start();  
69.         } else { //First solution             
70.             while(posStack.size()
71.                 if(posStack.isEmpty()){  
72.                     posStack.push(col);  
73.                     continue;  
74.                 } else {  
75.                     int i;  
76.                     for(i=0; i
77.                         if(!attack(i)){  
78.                             posStack.push(i);  
79.                             break;  
80.                         }                         
81.                     }  
82.                     if(i==size){  
83.                         if(!rollback()) {                             
84.                             System.out.println("No more solution!");  
85.                             return false;  
86.                         }                         
87.                     }  
88.                 }  
89.             }             
90.         }  
91.         return true;  
92.     }  
93.     protected void printTable(){  
94.         ArrayList copyList = new ArrayList();  
95.         posStack.copyTo(copyList);  
96.         int k;  
97.         for(int i=0; i
98.             k = copyList.get(i);  
99.             for(int j=0; j
100.                 if(j==k) {  
101.                     System.out.print("[Q] ");  
102.                     continue;  
103.                 }   
104.                 System.out.print("[#] ");  
105.             }  
106.             System.out.println("->"+k);  
107.         }  
108.     }  
109.       
110.     /** 
111.      * BD 找出指定數目的解法, 並列印出來. 
112.      * @param num 
113.      */  
114.     public void findSol(int num) {  
115.         for(int i=0; i
116.             if(start()){  
117.                 System.out.printf("====================(Solution %2d)===================\n",i+1);  
118.                 printTable();  
119.             }else {  
120.                 break;  
121.             }  
122.         }  
123.     }  
124.           
125.     public static void main(String args[]) {  
126.         Queue8 queue = new Queue8(0);  
127.         queue.findSol(93); // 找出 93 組解, 但其實總共只有 92組解  
128.     }  
129. }  

執行結果 : 

...(以上省略)...
====================(Solution 91)===================
[#] [#] [#] [#] [#] [#] [#] [Q] ->7
[#] [#] [Q] [#] [#] [#] [#] [#] ->2
[Q] [#] [#] [#] [#] [#] [#] [#] ->0
[#] [#] [#] [#] [#] [Q] [#] [#] ->5
[#] [Q] [#] [#] [#] [#] [#] [#] ->1
[#] [#] [#] [#] [Q] [#] [#] [#] ->4
[#] [#] [#] [#] [#] [#] [Q] [#] ->6
[#] [#] [#] [Q] [#] [#] [#] [#] ->3
====================(Solution 92)===================
[#] [#] [#] [#] [#] [#] [#] [Q] ->7
[#] [#] [#] [Q] [#] [#] [#] [#] ->3
[Q] [#] [#] [#] [#] [#] [#] [#] ->0
[#] [#] [Q] [#] [#] [#] [#] [#] ->2
[#] [#] [#] [#] [#] [Q] [#] [#] ->5
[#] [Q] [#] [#] [#] [#] [#] [#] ->1
[#] [#] [#] [#] [#] [#] [Q] [#] ->6
[#] [#] [#] [#] [Q] [#] [#] [#] ->4
No more solution! <總共只有 92組解>