750-8 Queens Chess Problem

<br /> /* <br /> "8 Queens Chess Problem"<br /> Level:6.5<br /> Date:2007/1/28<br /> 技巧: <br /> 先畫出search tree較易分析<br /> 可參考http://programming.im.ncnu.edu.tw/exapmle_for_java/9.htm的search tree.<br /> 這是一種Depth first Search, 但可根據eight queen的規則prune掉一些path.<br /> p.s.只允許output dataset之間有空白行，否則會P.E.到死...>,< */ #include <iostream><br /> using namespace std;<br /> int rowQ[8];<br /> int r,c;<br /> int cnt;<br /> <br /> void addQueen(int row, int col){<br /> //檢查前面column的queen. <br /> for(int i=0;i < col;i++){ //若新增的queen它的row上 or 斜對角線上有其它queen, 則該位置不得addQueen. if(row == rowQ[i] || col-i == abs(row-rowQ[i])){ return; } } rowQ[col]=row; //通過檢驗,在該位置addQueen. if(col < 7){ //若尚未Trace到第七層(即第七個column),則繼續向下trace. for(int i=0;i < 8;i++) addQueen(i,col+1); //測試下一層所有的row是否得以合法addQueen. } else if(rowQ[c-1]==r-1){ //trace完七層,則找到解,但只印出(r,c)有queen的特定解. ++cnt; if(cnt < 10) cout<<" "; cout << cnt << " "; for(int i=0;i < 8;i++) //印出每個column上Queen的row. cout<<" "<< rowQ[i]+1; cout<< endl; } } int main(void){ int num; cin>> num;<br /> int row[num],col[num];<br /> <br /> for(int i=0;i < num;i++){ // cout<< endl; 去掉這行才能AC. cin>>row[i];<br /> cin>>col[i];<br /> }<br /> for(int i=0;i < num;i++){ cout<< "SOLN COLUMN"<< endl; cout<< " # 1 2 3 4 5 6 7 8"<< endl; cout<< endl; r = row[i]; c = col[i]; for(int i=0;i < 8;i++) //trace所有解. addQueen(i,0); cnt=0; if(i != num-1) //加上這行才能AC. cout<< endl; } return 0; }