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

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

https://github.com/takishita2nd/sudoku

前回のソースでは、以下のような問題で解析が途中で失敗していました。

この原因を探るため、ログ出力を強化します。

まず、マスに値を入れるタイミングでログを出します。

次に、仮置きロジックを適用する時と、仮置き前に巻き戻しをする時に、それが分かるようにログを出します。

さらに、仮置きロジックを適用する場所をログに出力するようにします。

ここまでやって、 仮置きロジックを適用する場所を探す処理に不具合がある事が分かりました。

        /**
         * 仮置き対象のマスを抽出する
         *
         * squares マス
         */
        private List<Square> searchKariokiSquare(Square[,] squares)
        {
            List<Square> ret = null;
            for (int row = 0; row < 9; row += 3)
            {
                for (int col = 0; col < 9; col += 3)
                {
                    List<Square> temp = new List<Square>();
                    for (int i = 0; i < 3; i++)
                    {
                        for (int j = 0; j < 3; j++)
                        {
                            if (squares[row + i, col + j].isConfirmed() == false)
                            {
                                temp.Add(_square[row + i, col + j]);
                            }
                        }
                    }
                    if (ret != null) //←★ここ
                    {
                        if (ret.Count > temp.Count && temp.Count != 0)
                        {
                            ret = temp;
                        }
                    }
                    else
                    {
                        ret = temp;
                    }
                }
            }
            return ret;
        }

★の箇所で、ret=nullで、temp.Count = 0の時に、仮置きロジックを適用する箇所がない(ret.Count=0)となり、解析が終了していることが分かりました。

なので、★の箇所を修正します。

                    if (ret != null)
                    {
                        if (ret.Count > temp.Count && temp.Count != 0)
                        {
                            ret = temp;
                        }
                    }
                    else if(temp.Count != 0)
                    {
                        ret = temp;
                    }

解けました。

難易度★5の問題も解けるようになったので、大抵の問題は解けるようになりました。

もう少し動かしてみます。

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

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

https://github.com/takishita2nd/sudoku

前回、仮置きロジックを完成させたのですが、

このコード、結構無駄な処理をやっていることに気がついたんですよ。

        private Square doKarioki(Square[,] squares)
        {
            Square ret = null;
            List<Square> kariokiList = searchKariokiSquare(squares);
            foreach (var s in kariokiList)
            {
                bool roop = true;
                int kariValue = GetUnconfirmedValue(s.GetCandidate());
                if (kariValue == 0)
                {
                    return null;
                }
                Square[,] copySquare = makeClone(squares);
                copySquare[s.Row, s.Col].SetValue(kariValue);
                int now_count = 0;
                int prev_coount = 0;
                while (roop)
                {
                    for (int row = 0; row < 9; row++)
                    {
                        for (int col = 0; col < 9; col++)
                        {
                            if (copySquare[row, col].isConfirmed() == false)
                            {
                                Candidate candidate = new Candidate();
                                searchRowLine(copySquare, row, candidate);
                                searchColLine(copySquare, col, candidate);
                                search9Area(copySquare, row, col, candidate);
                                copySquare[row, col].checkCandidate(candidate);
                            }
                        }
                    }
                    searchNumber(copySquare);

                    if (checkContradict(copySquare))
                    {
                        break;
                    }

                    prev_coount = now_count;
                    now_count = countInputedNumber(copySquare);

                    if (prev_coount == now_count)
                    {
                        Console.WriteLine("仮置きロジック");
                        Square s2 = doKarioki(copySquare);
                        if (s2 == null)
                        {
                            Console.WriteLine("失敗しました");
                            return null;
                        }
                        else
                        {
                            copySquare[s2.Row, s2.Col].SetValue(s2.GetValue());
                        }
                    }

                    if (checkEnd(copySquare) == true)
                    {
　　　　　　　　　　　　　★
                        roop = false;
                        s.SetValue(kariValue);
                        Console.WriteLine("[{0},{1}] = {2}", s.Row, s.Col, s.GetValue());
                        ret = s;
                    }
                    FileAccess.Output(copySquare);
                }
                if(ret != null)
                {
                    break;
                }
            }
            return ret;
        }

今までは★に入ったタイミングで仮置きした値が確定して、という処理を行っていたんですが、

実はここに入った時点で解析結果が判明しているんですよね。

なので、この時点で解析結果を出力して終了、という処理にすれば、大幅に処理が短くなるはずです。

詳細はgitHubのソースコードを参照して頂ければ。

ついでに関数ヘッダにコメント入れました。