Problem 291 The House Of Santa Claus，聖誕老公公的房子

這個是小時候的遊戲，但我可沒玩過。題目要的答案是能筆不離紙的畫出下列圖形：
最後的輸出是將所有從點1出發的答案都列印出來。
我對這題的解法使用了回溯的方法，也就是和解八個皇后的方法一樣，請參考Problem 167 The Sultan's Successors，權位的繼承者。
畫圖的路徑一共有八條，所以會有九個點來敘述答案，不是範例中的八個數字，應該是九個。因此我使用

int path[PATHSIZE];

而PATHSIZE是9。在C語言主程式中呼叫

    path[0] = 0;
    Santa(0);

Santa是用來遞迴呼叫的C語言函數，完成細節如后。

void Santa(int i)
{
    int j;
    if (promising(i))
    {
        if (i==PATHSIZE-1)
        {
            for (j=0;j<PATHSIZE;j++)
                printf("%d", path[j]+1);
            printf("\n");
        }
        else
        {
            for (j=0;j<SIZE;j++)
            {
                path[i+1] = j;
                Santa(i+1);
            }
        }
    }
}

這個promising(i)決定要不要走下個點，有兩個基本考量
1. 不要走回自己，例如點3連到點3。
2. 不要走重複過的路，例如有了34，則34和43就不應該再出現在答案路徑中。
這個部份是訓練C語言程式設計邏輯的好機會，可以自己練習一下。
答案有44個，前五個是
123153452
123154352
123451352
123453152
123513452

p291題目連結
回ACM題庫目錄
回首頁