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

標籤

2010年10月17日 星期日

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

範例代碼 : 

- Stack.java : 定義堆疊的介面
  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 : 解法所使用的堆疊結構
  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()==0return "[]";  
  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()==0throw new EmptyStackException("Empty Stack");  
  28.         return stackList.get(stackList.size()-1);  
  29.     }  
  30.   
  31.     @Override  
  32.     public T pop() {  
  33.         if(stackList.size()==0throw 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 : 解題目的主程式
  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()==0return 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組解>


補充說明 : 
[ 資料結構 小學堂 ] 堆疊 : 堆疊應用 (八皇后問題)

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!