プログラミングとかブログ

Unity/C#/SRPGStudio/RPGツクールMVの情報とかその他気になったことを調べて書きます。

【C#】数独を解くメソッド

シンプルな数独の解法を解説してみた(C言語) - Newt Net(ひよっこプログラマー日記)にあるやつをC#で書きました。

コード

/// 総当たり回答
public void BruteForce(int[] board, int pos, int[][] retBoard)
{
    int emptyPos = 0;
    //現在位置から最も近い空白マスの位置を取得
    emptyPos =
        board.Select((p, i) => new { Content = p, Index = i })
        .Where(p => p.Content == 0 && p.Index >= pos)
        .Select(p => p.Index)
        .FirstOrDefault();
    //1マス目以外で空白マス位置が0になるようなら
    //Firstが見つからずDefaultが返ってきたということなので全部埋めたことになる
    //そのときは終了
    if (pos > 0 && emptyPos == default(int))
    {
        int xynum = 0;
        for (int k = 0; k < Utility.ROW; k++)
            for (int j = 0; j < Utility.COL; j++)
                retBoard[k][j] = board[xynum++];
        return;
    }
    //1から9のなかで現在のマスに入れられる数字があったなら埋めて次のマスへ
    for (int n = 1; n <= 9; n++)
    {
        if (CanInput(board, emptyPos, n))
        {
            board[emptyPos] = n;
            BruteForce(board, emptyPos + 1, retBoard);
            //ここにきた時点で入れた数字が間違っていたことになるので
            //それをなかったことにする
            board[emptyPos] = 0;//バックトラック
        }
    }
}


/// 同行同列同ブロックで入力数字がダブっておらず入れられるか
bool CanInput(int[] board, int pos, int inputNum)
{
    int N = 9, B = 3;
    int row = pos / N;
    int col = pos % N;
    //行と列に入力数字が出ているか
    for (int i = 0; i < N; ++i)
    {
        if (board[row * N + i] == inputNum) return false;
        if (board[col + i * N] == inputNum) return false;
    }
    //ブロックの左上の位置を取得
    int topLeft = N * (row / B) * B + (col / B) * B;
    //ブロック内に入力数字が出ているか
    for (int i = 0; i < B; ++i)
        for (int j = 0; j < B; ++j)
            if (board[topLeft + i * N + j] == inputNum)
                return false;

    return true;
}

結果

000000300090200070602080400000107080009000500070406000008070609020009030003000000の盤面を入力した結果です。
f:id:shirakamisauto:20160626150723p:plain
f:id:shirakamisauto:20160626150726p:plain

解説

冒頭のサイトと基本的に変わりません。
入力データは1次元配列です。
以下相違点。
・適当にリファクタリング
・空白マスの検索をLINQでやってます。Selectのオーバーロードでインデックス取得してます。
・2次元配列を渡すと回答盤面をコピーします。