「C#」カテゴリーアーカイブ

【C#】【数独】数独解析プログラム完成

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

前回の修正でほぼほぼ解析ロジックは完成したので、もうちょっと使い勝手が良いように、ファイル入出力とエラー処理に手を加えます。

まずは、いままで出力ファイル名が固定化されていたので、コマンドの第二パラメータに出力ファイルを入力するようにします。

具体的には、ファイル入出力が一つのstaticクラスで行っていたのを分割します。

入力ファイルの読み込みは、最初の1回しか実行しないので、staticクラスで、出力ファイルは何度も使用するので、通常のクラスで定義し直します。

出力クラスのコンストラクタで出力ファイル名を指定します。

    class FileOutput
    {
        private string _filename;
        public FileOutput(string filename)
        {
            _filename = filename;
            if (File.Exists(_filename) == true)
            {
                File.Delete(_filename);
            }
        }

        public void Output(Square[,] sq)
        {
            using (var stream = new StreamWriter(_filename, true))
            {
                for (int row = 0; row < 9; row++)
                {
                    for (int col = 0; col < 9; col++)
                    {
                        stream.Write(sq[row, col].GetValue());
                    }
                    stream.Write("\r\n");
                }
                stream.Write("\r\n");
            }
        }

        public void Output(bool[,] sq)
        {
            using (var stream = new StreamWriter(_filename, true))
            {
                for (int row = 0; row < 9; row++)
                {
                    for (int col = 0; col < 9; col++)
                    {
                        if (sq[row, col] == true)
                        {
                            stream.Write(1);
                        }
                        else
                        {
                            stream.Write(0);
                        }
                    }
                    stream.Write("\r\n");
                }
                stream.Write("\r\n");
            }
        }

        public void Output(int row, int col, int value)
        {
            using (var stream = new StreamWriter(_filename, true))
            {
                stream.Write("[{0},{1}] => {2}\r\n", row, col, value);
            }
        }

        public void Output(string text)
        {
            using (var stream = new StreamWriter(_filename, true))
            {
                stream.Write("{0}\r\n", text);
            }
        }

        public void Output(List<Square> list)
        {
            using (var stream = new StreamWriter(_filename, true))
            {
                stream.Write("候補 ");
                foreach (Square s in list)
                {
                    stream.Write("[{0},{1}]", s.Row, s.Col);
                }
                stream.Write("\r\n");
            }
        }
    }

メイン関数で出力ファイル名を取得します。

第二パラメータが無かった場合は、自動的に入力ファイイル名.outputというファイル名で出力させます。

        static void Main(string[] args)
        {
            // パラメータチェック
            if (args.Length < 1)
            {
                Console.WriteLine("usage : sudoku.exe [input file] [output file]");
                return;
            }

            // ファイルの存在を確認
            string filePath = Environment.CurrentDirectory + "\\" + args[0];
            if (File.Exists(filePath) == false)
            {
                Console.WriteLine("File not found.");
                return;
            }

            // 出力ファイル名
            string outfile = null;
            if (args.Length == 2)
            {
                outfile = Environment.CurrentDirectory + "\\" + args[1];
            }
            else
            {
                outfile = filePath + ".output";
            }

            var sq = FileRead.OpenFile(filePath);
            if(sq == null)
            {
                return;
            }

            Sudoku sudoku = new Sudoku(sq, outfile);
            sudoku.run();
        }

最後に、入力データのエラー処理を改善します。

具体的には、例えば、行と列が10以上あった場合、そして、数字以外の値が入っていた場合、数字が10以上入っていた場合はエラーで終了させます。

    static class FileRead
    {
        /**
         * ファイルからデータを取得する
         */
        public static Square[,] OpenFile(string filePath)
        {
            int[,] matrix = new int[9, 9];

            // ファイルを開く
            bool error = false;
            using (var stream = new StreamReader(filePath))
            {
                int row = 0;
                while (stream.EndOfStream == false)
                {
                    if (row >= 9)
                    {
                        error = true;
                        break;
                    }
                    string lineText = stream.ReadLine();
                    var val = lineText.Split(',');
                    if (val.Length > 9)
                    {
                        error = true;
                        break;
                    }
                    int col = 0;
                    foreach (var v in val)
                    {
                        int i;
                        if (int.TryParse(v, out i))
                        {
                            if(i >= 10)
                            {
                                error = true;
                                break;
                            }
                            matrix[row, col] = i;
                        }
                        else
                        {
                            error = true;
                            break;
                        }
                        col++;
                    }
                    if (error)
                    {
                        break;
                    }
                    row++;
                }
            }
            if (error)
            {
                Console.WriteLine("Illegal format.");
                return null;
            }

            Square[,] ret = new Square[9, 9];
            for (int row = 0; row < 9; row++)
            {
                for (int col = 0; col < 9; col++)
                {
                    Square sq = new Square(matrix[row, col], row, col);
                    ret[row, col] = sq;
                }
            }

            return ret;
        }
    }

そして、最終的にgitHubのようなソースになりました。

https://github.com/takishita2nd/sudoku

【C#】【数独】ログ出力を強化し不具合を探す

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

最新ソースはこちら(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の問題も解けるようになったので、大抵の問題は解けるようになりました。

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

【C#】【数独】仮置きロジック簡略化の修正を元に戻した。

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

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

https://github.com/takishita2nd/sudoku

修正を戻したのは、重大な欠陥に気がついたためです。

仮置きロジックを再起実行させたときに矛盾を検出した場合、正しく処理されない、という動きが発生していました。

やはり、面倒でも、仮置きロジックを再起処理から全てリターンして、値を一つずつ確定していくのが一番良い方法だと思います。

このコードでもう少し問題を解いてみます。

そして、最高難度の問題でも解けるかを確認していきたいと思います。

【C#】【数独】仮置きロジックを簡略化する。

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

最新ソースはこちら(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のソースコードを参照して頂ければ。

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

【C#】【数独】矛盾チェック処理と仮置きロジック再帰処理の実装

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

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

いやーロジック考えるのに時間かかりました。

まず、仮置きロジックを完成させるには、仮置きした結果、矛盾が発生した、ということを検出できる用にしなければならなくて。

これが、以外と難しい。

実際のコードは短くなっても、そこにたどり着くのが難しいのです。

オイラはこのように書きました。

        private bool checkContradict(Square[,] squares)
        {
            for (int row = 0; row < 9; row++)
            {
                for (int col = 0; col < 9; col++)
                {
                    if(squares[row,col].isConfirmed() == false)
                    {
                        Candidate candidate = new Candidate();
                        searchRowLine(_square, row, candidate);
                        searchColLine(_square, col, candidate);
                        search9Area(_square, row, col, candidate);
                        if(candidate.Count() == 9)
                        {
                            return true;
                        }
                    }
                }
            }
            return false;
        }

値は確定していない、しかし、縦、横、9マスを調べた結果、置ける数字が無い場合、という風に考えました。

これを使って仮置きロジックを作成します。

        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;
        }

難しかったのが、仮置きロジックの計算中に再び仮置きロジックが必要になった場合。

そう、このロジックを再帰的に実行する処理が必要なのです。

これを実装するために、これ以外の所もかなりの広範囲で書き換えています。

しかし、これでようやく解を得ることができました。

138964275
624715398
957283614
285637941
796841523
341529786
512476839
479358162
863192457

このロジックでいろいろな問題を解いてみようと思います。

【C#】【数独】仮置き対象を抽出する

かなり時間が空いてしまいましたが。

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

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

https://github.com/takishita2nd/sudoku

さて、実際に仮置きロジックを実装していくのですが、

そのときに必要となる情報が、

仮置きロジックをどこに適用するか

ということです。

今回は、9マスのエリアの中で、一番空きマスの少ない箇所を選択するように実装してみようと思います。

        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;
        }

コードはこんな感じに書いてみました。

9マスエリアに対して、まだ数字が入っていないマスの数を確認します。

数字が入っていないマスのオブジェクトをリストに登録し、それが他の9マスエリアの数より少ないか、を確認します。

調査結果は数字が入っていないマスのオブジェクトのリストを返します。

では、このメソッドを使用する処理を作成します。

        private void doKarioki()
        {
            Square[,] copySquare = makeClone(_square);
            List<Square> kariokiList = searchKariokiSquare(copySquare);
            foreach(var s in kariokiList)
            {
                Console.WriteLine("[{0},{1}]", s.Row, s.Col);
            }
        }

仮置き処理を実行するので、処理前にマス配列のクローンを作成します。

そして、先ほどのメソッドを使用して仮置き対象のマスをリストで取得。

そして、それに対してforeachを使って仮置きロジックを適用していきます。

Windows TerminalPS E:\Source\Repos\takishita2nd\sudoku\sudoku\bin\Debug> .\sudoku.exe .\q026.txt
仮置きロジック
[0,6]
[2,6]

こんな感じで、仮置き対象のマスの抽出ができました。

うん、完成が見えてきたぞ。

【C#】【数独】仮置きロジックを適用する条件を考える。

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

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

https://github.com/takishita2nd/sudoku

さて、いよいよ仮置きロジックの実装にとりかかります。

そのためには、仮置きロジックを行う条件を考えましょう。

現在まで実装しているロジックでのみで、ある程度はマスを埋めることができますので、そのロジックでも埋まらなかった場合、と考えるのが妥当でしょう。

その条件とは、周期処理の前と後で、確定しているマスの数が同じならば、と判断するのが一番簡単だと思います。

それでは実装します。

まずは、確定しているマスを数えるメソッドを作成します。

        private int countInputedNumber()
        {
            int ret = 0;
            for(int i = 0; i < 9; i++)
            {
                for(int j = 0; j < 9; j++)
                {
                    if(_square[i, j].isConfirmed())
                    {
                        ret++;
                    }
                }
            }
            return ret;
        }

特に難しいところはありませんね。

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

        private int now_count = 0;
        private int prev_coount = 0;

        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);
                        }
                    }
                }
                searchNumber();

                prev_coount = now_count;
                now_count = countInputedNumber();

                if(prev_coount == now_count)
                {
                    //debug
                    Console.WriteLine("ここで仮置きロジックを適用する {0} {1}", prev_coount, now_count);
                    return;
                }

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

こんな感じでどうでしょうか。

prev_coountが周期前の確定したマス数、now_countが周期後の確定したマス数です。

確定したマス数を数える前に前回のマス数を保存し、それと、現周期でのマス数を比較します。

これが同じならば、仮置きロジックを適用する(debug出力を行っているところ)という動きになります。

次回は、このdebugの箇所を考えていきます。

【C#】【数独】解析ロジック(仮置き矛盾チェック)を考える

前回までの状況はこちら

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

https://github.com/takishita2nd/sudoku

さて、以下のような問題が出題されたとき、解析が止まってしまう現象が発生しました。

例えば、数字の2に注目した場合、

オレンジの2箇所と青の2箇所が数字の2が入る可能性があるのですが、今までのロジックでは値が確定しないため、解析が進まない状態となってしまいます。

この場合、仮置きというやり方をします。

例えば、

オレンジのマスに数字2を置いた場合、今までの解析ロジックから青のマスに2が入りますが、同じライン上に2がすでに存在しますので、この置き方は誤りと言うことになります。

逆に、このように置けば、矛盾が発生しませんので、このマスに入る数字は2で確定する事になります。

これをプログラムでロジック化します。

やり方をまとめます。

解析ループ処理に変化が無かった場合、仮置きロジックを適用します。

解析途中のデータを複製し、空いている箇所に、仮の値を置き、通常の解析ロジックを実施します。

その結果、矛盾が発生していれば、その複製データを破棄します。

矛盾が発生していなければ、その値で確定します。

値が確定すれば、その状態で解析を継続します。

ざっくり言えばこんな感じですね。

次回以降、もう少し細かいところを詰めて、実装していこうと思います。

【C#】【数独】解析ロジック(ラインチェック)を追加する

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

最新ソースはこちら(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;
            }
        }

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

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

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

全部埋まりました。

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