六芒星棋遊戲：先還是後比較有利？

問題敘述：
在一個稱為『六芒星』的星球上，流行著一種『六芒星棋』的遊戲。這種遊戲是由兩個人來比賽，道具是一個棋盤（如圖一）和13 個鐵圈。遊戲的起始狀態是由兩人互相協調或隨機決定，使用m 個（1 ≦ m ≦ 13）鐵圈在棋盤上圈住m個數字。接下來雙方輪流移除棋盤上的鐵圈，每人每次只能移除1個鐵圈或2個相鄰的鐵圈（有直線直接相連的位置視為相鄰），被迫移除最後一個鐵圈的人算輸。

其實如果仔細思考，可以證明不管起始狀態如何，遊戲中先移除鐵圈的人（先手）與其對手（後手）中必定恰有一人，只要他每次都用對自己最有利的方法來移除鐵圈，最後一定百分之百得勝。

以起始狀態如圖二為例，因為所有鐵圈均不相鄰，故一次只能移除一個鐵圈，先手不管移除哪一個圈，後手只要再移除一個圈，就可以逼迫先手移除最後一個圈，因此後手有百分之百得勝的把握，我們說成『圖二的起始狀態是後手有利』。若起始狀態如圖三就不同了，如果先手懂得先移除相鄰的兩個鐵圈（如2^7 與2^10），就可以迫使後手去移除最後一個圈，因此先手就有百分之百得勝的把握，我們說成『圖三的起始狀態是先手有利』。每一種起始狀態，我們用一個整數來表示它，這個整數就是在該起始狀態中所有被鐵圈圈住的數字總和。例如圖二的起始狀態可以用2^3+2^5+2^11=2088 表示，圖三則可用2^7+2^9+2^10=1664 來表示。

請你寫一個程式來判斷在不同的起始狀態下，到底是先手還是後手有利。

　

解法：
使用 Dynamic Programing，大問題由小問題所組成，大的數字由小的數字組成，故判斷 X 為先手或後手可用 X 的上一層來判斷，若 X 拿走一個鐵圈或拿走兩個鐵圈的狀況都是後手有利，則對 X 本身來說即是先手有利；若都是先手有利，對 X 本身來說則會是後手有利；若前一步有先手後手都有利的情況，則在不會選擇故意輸的條件下，必定是選先手有利。

　

Note：

１. 跳脫出圖形的限制，跟圖形沒有關係。

２. 建一 table，存放各種數字組合所對應的有利選擇，從小到大往後填滿。

３. 預設 table[0] 為先手有利。

//----- user definition -----
#define FIRST 1
#define SECOND 0
#define MAX_NUM 8192-1 //2^13-1
#define BOARD_NUM 13
#define NEIGH_NUM 6

//----- global variables -----
/* a table that records the output and initilize first element to 1 */
int table[MAX_NUM]={1};
int component[BOARD_NUM]; /* bit(board) number */

/* neighbors of each node */
int neighbor[BOARD_NUM][NEIGH_NUM+1]={{2,3,-1,-1,-1,-1,-1},
　　　　　　　　　　　　　　　　　　　　　　{2,5,-1,-1,-1,-1,-1},
　　　　　　　　　　　　　　　　　　　　　　{0,1,3,5,6,-1,-1},
　　　　　　　　　　　　　　　　　　　　　　{0,2,4,6,7,-1,-1},
　　　　　　　　　　　　　　　　　　　　　　{3,7,-1,-1,-1,-1,-1},
　　　　　　　　　　　　　　　　　　　　　　{1,2,6,8,9,-1,-1},
　　　　　　　　　　　　　　　　　　　　　　{2,3,5,7,9,10,-1},
　　　　　　　　　　　　　　　　　　　　　　{3,4,6,10,11,-1,-1},
　　　　　　　　　　　　　　　　　　　　　　{5,9,-1,-1,-1,-1,-1},
　　　　　　　　　　　　　　　　　　　　　　{5,6,8,10,12,-1,-1},
　　　　　　　　　　　　　　　　　　　　　　{6,7,9,11,12,-1,-1},
　　　　　　　　　　　　　　　　　　　　　　{7,10,-1,-1,-1,-1,-1},
　　　　　　　　　　　　　　　　　　　　　　{9,10,-1,-1,-1,-1,-1}};

//----- function prototype -----
int find(int,int); /* return which order is better */
void set_compo(int); /* set up the components of the sum */
/* extract one component of sum,
　 if equals 0 then return 1, otherwise return 0 */
int extract(int);

//----- functions -----
/* return which order is better at sum2 */
int find(int sum)
{
　int tmp_sum;

　/* find the output of sum step by step */
　for(tmp_sum=1;tmp_sum<=sum;tmp_sum++)
　{
　　/* set up the components of sum */
　　set_compo(tmp_sum);

　　/* find the output of each tmp_sum */
　　table[tmp_sum]=extract(tmp_sum);
　}
　/* return the result output */
　return table[sum];
}

/* store 2^idx if the index is one of the sum's component, otherwise stores 0 */
void set_compo(int sum)
{
　int i,mask=1;
　for(i=0;i<BOARD_NUM;i++,mask*=2)
　　component[i]=((mask&sum)==mask)?mask:0;
}

/* return FIRST if table[] is 0 */
/* otherwise return SECOND */
int extract(int sum)
{
　int i,j;
　/* scan all the component array */
　for(i=0;i<BOARD_NUM;i++)
　　/* if there is a nonzero in component */
　　if(component[i]!=0)
　　{
　　　/* test by extracting one value */
　　　if(!table[sum-component[i]])　return FIRST;

　　　/* scan this node's neighbor whether they are combined or not */
　　　for(j=0;neighbor[i][j]!=-1;j++)
　　　　/* if it is then test by extracting two values */
　　　　if(component[neighbor[i][j]]!=0)
　　　　　if(!table[sum-component[i]-component[neighbor[i][j]]])
　　　　　　return FIRST;
　　}
　/* if there's no 0s in table[] then SECOND is better */
　return SECOND;
}