【解題】井字遊戲 - TTT

台北市95學年度高中資訊學科能力競賽 - 井字遊戲 (TTT)


問題描述

　　井字遊戲是三、四歲小孩就會玩的棋賽。在一個 3 列(row) x 3 行(column)的空格中，參與遊戲的兩人一個只能填入 O，另一個只能填入 X，兩人從頭到尾輪流填入自己的符號，誰先將自己的符號在垂直、水平或斜角方向連成 3 個，誰就勝利。在此假設遊戲一開始都是填入 O 的人先填。

　　請寫一個程式，來判斷給定任一未完成的棋局，其最後結束時(O 贏、X 贏或平手)共有幾種不同的棋盤面，而其中 O 贏的棋盤面、X 贏的棋盤面、和局的棋盤面各有幾種。

　　例如，下圖中，最左邊的棋局，其結束時的棋盤面會有右邊四種可能。第一種 O 贏，第二種平手，第三、四種都是 X 贏，因此輸出(4, 1, 2, 1)。




輸入檔格式(C:\ttt\input.txt)

　　測試檔案中共有一行，以九個連續符號表示未完成的棋局，前三個符號代表該棋局第一列的三個格子的狀態，第四到第六個符號代表該棋局第二列的三個格子的狀態，第七到第九個符號代表該棋局第三列的三個格子的狀態。這些符號除了「O」與「X」外，以「-」來代表尚未被填入的格子。輸入檔中不會有不合理的棋局出現。


輸出檔格式 (C:\ttt\output.txt)

　　依序輸出該棋局最後可能出現的不同棋盤面數、O 贏的棋盤面數，X 贏的棋盤面數，以及平手的棋盤面數，此四個數字以空白隔開。


輸入檔範例1

OX--X-XOO


輸出檔範例1

4 1 2 1


輸入檔範例2

O-OXO-X--


輸出檔範例2

11 9 1 1


輸入檔範例3

O-OXO-X-X


輸出檔範例3

4 2 1 1


解題思考

　　對於這一題，我選擇使用遞迴函式來模擬雙方下棋。

　　首先，我們注意到一個不太明顯的小地方。棋盤的空白處(即未下棋的地方)數量，除了可以來判斷棋盤是否已下滿之外，還可以用它代表現在下棋的人是 O 或是 X。由於是 O 先下，所以剩餘空白處的數量只是奇數就是 O 下，相反的，是偶數則為 X 下。

　　我們根據以上提到的，判斷由誰下棋。並藉由迴圈來模擬下在各種地方的情況。並且，在每下完一步都檢查是否分出勝負。

　　單是這樣還不行，因為即使下的順序不同，最後可能還會出現棋局重複的情形。因此，我們還需要儲存已出現過的棋局。你可以使用一個二維字元陣列。

　　不過，由於我不想耗費一個陣列存一個棋局(就是棋盤的每一格由一個陣列元素儲存)，我將棋局轉換成一個九位數的整數。第一位代表第 1 格，第二位代表第 2 格，以此類推。這樣一個棋局就只需要一個整數變數就能代表了。當然，僅供參考，有人有更好的方法也可以提出。


參考解答(C)

#include <stdio.h>
#include <stdlib.h>

void play(void);
int search(void);

int num = 0, win[2] = {0, 0}, top = 1, st[500];
char t[9];

int main(void)
{
    int i, sum;

    // 宣告檔案串流
    FILE *in, *out = fopen("C:/ttt/output.txt", "w+");
    if (!(in = fopen("C:/ttt/input.txt", "r")))
    {
        printf("找不到 input.txt\n");
        system("pause");
        exit(1);
    }

    printf("讀入資料 . . .\n");
    for (i = 0; i < 9; i++)
    {
        t[i] = fgetc(in);
        printf("%c", t[i]);
        if (t[i] == '-') { num += 1; }
    }

    fclose(in);

    printf("\n---------\n");

    // 呼叫遞迴處理棋局
    play();
    sum = win[0] + win[1] + win[2];

    // 將結果印在輸出檔
    fprintf(out, "%d %d %d %d", sum, win[1], win[0], win[2]);
    fclose(out);

    // 將結果標準輸出
    printf("局數： %d\nO 勝： %d\nX 勝： %d\n和局： %d\n", sum, win[1], win[0], win[2]);
    printf("---------\n輸出資料在 ouput.txt\n");

    system("pause");
}

void play(void)
{
    int i;

    // 判別是否分出勝負
    if ((t[4] != '-') && (((t[0] == t[4]) && (t[4] == t[8]))
        || ((t[6] == t[4]) && (t[4] == t[2]))))
    {
        if (search()) { return; }

        win[(num + 1) % 2] += 1;

        return;
    }

    for (i = 0; i < 3; i++)
    {
        if (((t[i] != '-') && (t[i] == t[i + 3]) && (t[i] == t[i + 6]))
            || ((t[3 * i] != '-') && (t[3 * i] == t[3 * i + 1])
            && (t[3 * i] == t[3 * i + 2])))
        {
            if (search()) { return; }

            win[(num + 1) % 2] += 1;

            return;
        }
}

    // 判別是否和局
    if (num == 0)
    {
        if(search()) { return; }

        win[2] += 1;

        return;
    }

    // 使用窮舉法實現每種可能
    for (i = 0; i < 9; i++)
    {
        if (t[i] == '-')
        {
            t[i] = num % 2 ? 'O' : 'X';
            num--;
            play();
            num++;
            t[i] = '-';
        }
    }
}

int search(void)
{
    int i, temp = 0;

    // 將棋局轉換存入變數
    for (i = 0; i < 9; i++)
    {
        if (t[i] == 'O') { temp = temp * 10 + 1; }
        else if (t[i] == 'X') { temp *= 10; }
        else { temp = temp * 10 + 2; }
    }

    for (i = 0; i < top; i++)
    {
        // 查詢棋局是否重複
        if (temp == st[i]) { return 1; }
    }

    // 將目前棋局記錄下來
    st[top] = temp;
    top++;

    return 0;
}