【C#】【数独】数独解析ロジックを実装する。

前回までの状況はこちら。

【C#】【数独】マス目のデータをどう持つか、を考える。

最新ソースはこちら(gitHub)

https://github.com/takishita2nd/sudoku

多分、今回が一番のキモ。

実際に数独を解析するロジックを作成していきます。

そもそも、数独のルールは、

オレンジのところに入る数字は、黄色の縦、横、9マスの部分に同じ数字が存在してはならない、ということです。

ということは、黄色の部分を検索して、そのなかに含まれない数字が、このマスに入る数字の候補となります。

そのとき、もし、候補が一つしか存在しない場合は、その値がそのマスに入る数字で確定します。

この調査を、確定していないマス全てに対して、全てのマスが確定するまで実施します。

では、まずは候補を調査した結果を格納するクラスの定義。

    class Candidate
    {
        public bool[] value;

        public Candidate()
        {
            this.value = new bool[9] { false, false, false, false, false, false, false, false, false };
        }

        public int Count()
        {
            int ret = 0;
            foreach(var val in this.value)
            {
                if(val == true)
                {
                    ret++;
                }
            }

            return ret;
        }
    }

boolean値の配列9個を持ち、コンストラクタでfalseに初期化します。

メソッドとしては、この中でいくつヒットしたか、配列のtrueの数を数えて結果を返すメソッドを持ちます。

これを使用して、実際に調査を行う処理はこちら。

    class Sudoku
    {
        private Square[,] _square;

        /**
         * コンストラクタ
         */
        public Sudoku(Square[,] square)
        {
            _square = square;
        }

        /**
         * 実行
         */
        public void run()
        {
            int roop = 0;
            while (true)
            {
                for(int row = 0; row < 9; row++)
                {
                    for(int col = 0; col < 9; col++)
                    {
                        if(_square[row,col].isConfirmed() == false)
                        {
                            Candidate candidate = new Candidate();
                            searchRowLine(row, candidate);
                            searchColLine(col, candidate);
                            search9Area(row, col, candidate);
                            _square[row, col].checkCandidate(candidate);
                        }
                    }
                }

                //debug
                roop++;
                FileAccess.Output(_square);
                if(roop == 10)
                {
                    break;
                }
            }
        }

        private void searchRowLine(int row, Candidate candidate)
        {
            for(int i = 0; i < 9; i++)
            {
                int val = _square[row, i].GetValue();
                if(val != 0)
                {
                    candidate.value[val - 1] = true;
                }
            }
        }

        private void searchColLine(int col, Candidate candidate)
        {
            for (int i = 0; i < 9; i++)
            {
                int val = _square[i, col].GetValue();
                if (val != 0)
                {
                    candidate.value[val - 1] = true;
                }
            }
        }

        private void search9Area(int row, int col, Candidate candidate)
        {
            int rowStart;
            int colStart;
            if (row >= 0 && row <= 2)
            {
                rowStart = 0;
            }
            else if(row >= 3 && row <= 5)
            {
                rowStart = 3;
            }
            else
            {
                rowStart = 6;
            }

            if (col >= 0 && col <= 2)
            {
                colStart = 0;
            }
            else if (col >= 3 && col <= 5)
            {
                colStart = 3;
            }
            else
            {
                colStart = 6;
            }

            for(int r = rowStart; r < rowStart+3; r++)
            {
                for (int c = colStart; c < colStart + 3; c++)
                {
                    int val = _square[r, c].GetValue();
                    if (val != 0)
                    {
                        candidate.value[val - 1] = true;
                    }
                }
            }
        }
    }

searchRowLine()では、横のラインを、

searchColLine()ででゃ、縦のラインを、

search9Area()では9マスの範囲を検索します。

ヒットした数字に対して、candidateの持つ配列にtrueを設定します。

なお、－1しているのは、数独に設定する数字が1～9なのに対し、プログラム上の配列の範囲は0～8なので、その補正です。

そして、調査結果を反映する処理はこちら。

    class Square
    {
：
中略
：
        public void checkCandidate(Candidate candidate)
        {
            if(candidate.Count() == 8)
            {
                for(int i = 0; i < 9; i++)
                {
                    if(candidate.value[i] == false)
                    {
                        SetValue(i + 1);
                    }
                }
            }
        }
    }

調査結果、見つかった数字の数が8個だった場合、見つかっていない数字を探し、その値でマスの値を確定します。

これをrun()メソッドで、確定していない全マスに対して行います。

本来は、全てのマスが埋まったことを確認して終了しなければならないのですが、そこはまだ作っていないので、とりあえず、10回繰り返す、と言うことにしています。

では、実際に動かしてみます。

インプットデータはこちら。