雲林SONG: 高中生程式解題系統：a016: 數獨(SUDOKU)

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

註：此題高中生程式解題系統目前不公開。筆者在高中生程式解題系統有公開時，解掉此題。http://zerojudge.tw/ShowProblem?problemid=a016

內容：
底下文字出自Wikipeida：

數獨（日語：数独／すうどく^Sūdoku */?）是一種數學邏輯遊戲，遊戲由9×9個格子組成，玩家需要根據格子提供的數字推理出其他格子的數字。遊戲設計者會提供最少17個數字使得解答謎題只有一個答案。這種遊戲只需要邏輯思維能力，與數字運算無關。雖然玩法簡單，但提供的數字卻千變萬化，所以不少教育者認為數獨是鍛鍊腦筋的好方法。

現在用程式來判斷一個九宮格數字是不是一個數獨的正解。

輸入說明：

輸入的每一組測試資料均為 9 × 9 的矩陣，且全部為 1~9 的數字，每兩組九宮格之間以一空行作為分隔

輸出說明：

yes or no

範例輸入 ：

若題目沒有特別說明，則應該以多測資的方式讀取，若不知如何讀取請參考 a001 的範例程式。

1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 1
3 4 5 6 7 8 9 1 2
4 5 6 7 8 9 1 2 3
5 6 7 8 9 1 2 3 4
6 7 8 9 1 2 3 4 5
7 8 9 1 2 3 4 5 6
8 9 1 2 3 4 5 6 7
9 1 2 3 4 5 6 7 8

1 9 3 2 6 5 4 7 8
7 8 2 3 1 4 9 5 6
4 5 6 9 7 8 1 3 2
2 3 4 8 5 1 6 9 7
9 6 5 4 3 7 2 8 1
8 7 1 6 9 2 3 4 5
3 1 9 5 8 6 7 2 4
5 2 7 1 4 3 8 6 9
6 4 8 7 2 9 5 1 3

範例輸出 ：

no
yes

提示：

背景知識：陣列

出處：

Jiangsir

程式解法是照著規則所寫的，底下文字出自Wikipeida：

由9個3×3個的九宮格組成。
每一列的數字均須包含 1～9，不能缺少，也不能重複。
每一行的數字均須包含 1～9，不能缺少，也不能重複。
每一宮(粗黑線圍起來的區域，通常是 3*3 的九宮格)的數字均須包含 1～9，不能缺少，也不能重複。

用一維陣列short sudoku[MATRIX_SIZE];來存3x3的九宮格，而陣列short matrix[SIZE];用來存每一個九宮格的數字。底下程式碼：

short index[] = {
    1, 2, 3,
    10, 11, 12,
    19, 20, 21
};

是用來記錄每個九宮格在sudoku[MATRIX_SIZE]的索引位置。

程式碼：

#include <iostream>
#include <cmath>

using namespace std;

const short SIZE = 9;

void prtMsg(bool b)
{
    cout << (b?"yes":"no") << endl;
}

bool check(short value[SIZE])
{
    bool num[SIZE + 1];

    for(int i = 0; i < SIZE + 1; i++)
        num[i] = false;

    for(int i = 0; i < SIZE; i++)
    {
        //cout << "value[" << i << "] = " << value[i] << " ";

        if( num[value[i]] == false )
        {
            num[value[i]] = true;
        }
        else
        {
            return false;
        }
    }

    return true;
}

int main()
{
    const short MATRIX_SIZE = SIZE*SIZE;
    short sudoku[MATRIX_SIZE];
    short matrix[SIZE];

    short index[] = {
        1, 2, 3,
        10, 11, 12,
        19, 20, 21
    };

    while( cin >> sudoku[0] )
    {
        for( int i = 1; i < MATRIX_SIZE; i++ )
            cin >> sudoku[i];

        bool isSudoku = true;

        for(int k = 0; k < SIZE; k++)
        {
            short subScript = 27 * (k/3) + 3 * (k%3);

            for( int j = 0; j < SIZE; j++ )
            {
                short temp = subScript + index[j];
                matrix[j] = sudoku[temp-1];
            }

            isSudoku = check(matrix);
            if(!isSudoku)
                break;
        }


        prtMsg(isSudoku);
    }

    return 0;
}

高中生程式解題系統：a016: 數獨(SUDOKU)

沒有留言: