八皇后權重問題

題目如下:
輸入N*N格子，每個格子0~9表示佔此位置可得分數，計算放置N個皇后互不攻擊可得之最大分數。
小弟遞迴有點弱...

瀏覽完整內容，請先 註冊 或 登入會員

ren1244

提供參考：遞迴找出八皇后所有解。
(執行馬上可以跑出答案)

應該可以用這程式改成原題目的要求。

1. #include <stdio.h>
   
2. 
   
3. #define output printf
   
4. 
   
5. void queen(int N,unsigned char M,unsigned char L,unsigned char R,unsigned char* record)
   
6. {
   
7.     //M是前面已佔用位置，L跟R是不能使用位置(斜線位置)，L跟R在每列會分別shift左或右1位元
   
8.     unsigned char mask=M|L|R;
   
9.     int i,j;
   
10.     for(i=0;i<8;++i)
    
11.     {
    
12.         if(!(mask>>i&1))
    
13.         {
    
14.             *record=i;
    
15.             if(N==7)
    
16.             {
    
17.                 for(j=0;j<8;++j)
    
18.                     output("(%d,%d)",*(record-7+j),j);
    
19.                 output("\n");
    
20.             }
    
21.             else
    
22.                 queen(N+1,M|1<<i,(L|1<<i)<<1,(R|1<<i)>>1,record+1);
    
23.         }
    
24.     }
    
25. }
    
26. int main()
    
27. {
    
28.     unsigned char rec[8];
    
29.     queen(0,0,0,0,rec);
    
30.     return 0;
    
31. }

複製代碼

---

2016 6/1：改自上面程式，擴展為N皇后所有解
...

瀏覽完整內容，請先 註冊 或 登入會員

snowflying

就算不用遞迴，若是 N = 8
8! = 40320，窮舉完判斷合不合法，並計算分數，時間也不會太長

gitlab

不就把分數也當作遞迴函數的argument，然後 "擺皇后" 的時候順便加一下?

ren1244 發表於 2016-6-1 12:50 AM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

提供參考：遞迴找出八皇后所有解。
(執行馬上可以跑出答案)

感謝大大
但是您的txt檔中文都變成了亂碼QQ

gitlab 發表於 2016-6-1 02:58 AM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

不就把分數也當作遞迴函數的argument，然後 "擺皇后" 的時候順便加一下?

聽大大這麼一說
好像也是
我再試試看...

瀏覽完整內容，請先 註冊 或 登入會員