【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の盤面を入力した結果です。