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

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

https://github.com/takishita2nd/sudoku

さて、前回のアルゴリズムで、いくつか問題を解いてみたのですが、

こんな問題の時、解析が完了しませんでした。

この状態のまます、解析が進まなかったんですね。

この状態、手で解いた場合、

この2箇所に「3」が入ります。

この時の解析ロジックを組み込まなければなりません。

では、どうやって解析すればいいのか。

この場合、3という数字に注目すると、

この部分、および、すでに確定されているマスに「3」が入ることができません。

赤いところの9マスは一箇所しか空いていないため、そこの空いているマスには「3」が入ることが確定されます。

これをプログラミングで行います。

考え方は、9×9の二次元配列を用意し、各数字について、入れることができないマスを埋めていき、9エリアに一箇所だけ空きがあれば、その値が確定する、とします。

        private void searchNumber()
        {
            for(int number = 1; number <= 9; number++)
            {
                bool[,] tempTable = new bool[9, 9];
                // 初期化
                for (int i = 0; i < 9; i++)
                {
                    for (int j = 0; j < 9; j++)
                    {
                        tempTable[i, j] = false;
                    }
                }

                // 数字が入らないところをtrueにする
                for (int i = 0; i < 9; i++)
                {
                    for(int j = 0; j < 9; j++)
                    {
                        if(tempTable[i,j] == false)
                        {
                            tempTable[i, j] = _square[i, j].isConfirmed();
                            if(_square[i,j].GetValue() == number)
                            {
                                for(int row = 0; row < 9; row++)
                                {
                                    tempTable[row, j] = true;
                                }
                                for(int col = 0; col < 9; col++)
                                {
                                    tempTable[i, col] = true;
                                }

                                int rowStart;
                                int colStart;
                                getRowCol9Area(i, j, out rowStart, out colStart);
                                for (int r = rowStart; r < rowStart + 3; r++)
                                {
                                    for (int c = colStart; c < colStart + 3; c++)
                                    {
                                        tempTable[r, c] = true;
                                    }
                                }
                            }
                        }
                    }
                }

                // debug
                FileAccess.Output(tempTable);

                // 結果を確認する
                for(int i = 0; i < 9; i++)
                {
                    for(int j = 0; j < 9; j++)
                    {
                        if(tempTable[i,j] == false)
                        {
                            int rowStart;
                            int colStart;
                            getRowCol9Area(i, j, out rowStart, out colStart);

                            int count = 0;
                            for (int r = rowStart; r < rowStart + 3; r++)
                            {
                                for (int c = colStart; c < colStart + 3; c++)
                                {
                                    if(tempTable[r,c] == false)
                                    {
                                        count++;
                                    }
                                }
                            }
                            if(count == 1)
                            {
                                _square[i, j].SetValue(number);
                            }
                        }
                    }
                }
            }
        }

        private void getRowCol9Area(int row, int col, out int rowStart, out 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;
            }
        }

一応、色塗りした処理結果もデバッグ用に出力させました。

３の時の色塗り結果を見てみると、９マスで一か所だけ空きがあることが分かります。

目論見通り、３が確定されました。

全部埋まりました。

ロジックがうまく働いたようです。

前回までの状況はこちら

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

https://github.com/takishita2nd/sudoku

さて、最後に解析終了処理を実装していきます。

解析終了条件は、9×9＝81マス全ての数字が確定した場合、になります。

逆に言えば、81マスの中で、一つでも確定していないマスがあれば、終了しない、と言うことになります。

と言うわけで、コードはこうなりました。

        private bool checkEnd()
        {
            for (int i = 0; i < 9; i++)
            {
                for(int j = 0; j < 9; j++)
                {
                    if(_square[i, j].isConfirmed() == false)
                    {
                        return false;
                    }
                }
            }
            return true;
        }

解析終了ならばtrueを、そうでないならばfalseを返します。

これを周回処理に組み込みます。

        public void run()
        {
            bool roop = true;
            while (roop)
            {
                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);
                        }
                    }
                }

                roop = !checkEnd();
                FileAccess.Output(_square);
            }
        }

ループ条件と判定結果が反転しているので、!演算子で反転させています。

実行結果はこちら。

ちゃんと全部埋まった時点で終了しました。