前回までの状況はこちら

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

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

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

実行結果はこちら。

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

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

【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回繰り返す、と言うことにしています。

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

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

実行結果はこちら

1回ループする毎に、途中結果も全てファイルに吐き出すようにしています。

見事に全部埋まりました。

これを、ナンプレアプリに入力してみましょう。

目論見通りに動いてくれましたね。

多分、簡単な数独問題ならこれで解けるはず。

前回の状況はこちら。

【C#】【数独】ファイルからデータを取り込む

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

https://github.com/takishita2nd/sudoku

前回はファイルからデータを取り出して、int型の二次元配列に取り込む、ということをしましたが、このままでは数独の解析は難しいでしょう。

なので、マス目一つ一つをオブジェクトとして、様々なデータを持つようにしたいと思います。

とりあえず、今考えているのは、

• 確定した値
• 確定したかどうか
• 候補となる数字
• etc…

とりあえず、これを実装してみたいと思います。

    class Square
    {
        class Candidate
        {
            public bool value1;
            public bool value2;
            public bool value3;
            public bool value4;
            public bool value5;
            public bool value6;
            public bool value7;
            public bool value8;
            public bool value9;

            public Candidate()
            {
                this.value1 = false;
                this.value2 = false;
                this.value3 = false;
                this.value4 = false;
                this.value5 = false;
                this.value6 = false;
                this.value7 = false;
                this.value8 = false;
                this.value9 = false;
            }
        }

        // 確定した数字
        private int _value;
        // 確定したかどうか
        private bool _confirmed;
        // 候補の数字
        private Candidate _candidate;

        public Square()
        {
            this._value = 0;
            this._confirmed = false;
            this._candidate = new Candidate();
        }

        public Square(int val)
        {
            this._value = val;
            if(val == 0)
            {
                this._confirmed = false;
            }
            else
            {
                this._confirmed = true;
            }
            this._candidate = new Candidate();
        }

        public int GetValue()
        {
            return this._value;
        }

        public void SetValue(int val)
        {
            this._value = val;
            this._confirmed = true;
        }

        public bool isConfirmed()
        {
            return this._confirmed;
        }
    }

まずは、こんな感じでマス目のクラスSquareを定義しました。

これで完全とは思っていません。

今後も必要に応じて追加していきます。

これに、ファイルから取得したデータを設定します。

    static class FileAccess
    {
        /**
         * ファイルからデータを取得する
         */
        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)
                {
                    string lineText = stream.ReadLine();
                    var val = lineText.Split(',');
                    int col = 0;
                    foreach (var v in val)
                    {
                        int i;
                        if (int.TryParse(v, out i))
                        {
                            matrix[row, col] = i;
                        }
                        else
                        {
                            error = true;
                        }
                        col++;
                    }
                    row++;
                    if (row > 9)
                    {
                        error = true;
                    }
                }
            }
            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]);
                    ret[row, col] = sq;
                }
            }

            return ret;
        }

        // debug
        public static void Output(Square[,] sq)
        {
            using (var stream = new StreamWriter(System.Environment.CurrentDirectory + "\\output"))
            {
                for (int row = 0; row < 9; row++)
                {
                    for (int col = 0; col < 9; col++)
                    {
                        stream.Write(sq[row, col].GetValue());
                    }
                    stream.Write("\r\n");
                }
            }
        }
    }

前回のファイルリード、ライト処理をクラス化しました。やっていることに大きな変更はありません。

これで、Main関数もスッキリするはずです。

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

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

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

            // debug
            FileAccess.Output(sq);
        }
    }

前回と同じ結果を取得することができました。

取り込みが美味く機能していることが言えます。

とりあえず、今日はここまで。

実際にロジックを考えてみます。

なんか、とあるプログラミングスクールの入学試験でこういう問題は出題されたらしい。

合格できると、スクールの費用が全額無料ということなのですが、やはり、その門のハードルは高いようです。

で、オイラも腕試しで数独（ナンバープレイス）を解くプログラミングをやってみようと思いました。

まずは、問題を読み取るところから。（そこからかよ！）

とにかく、今回はUIは気にしないで、

こんな感じのファイルを取り込んで、デバッグ機能としてそのまま出力するところまでやります。

コードはこんな感じになりました。

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace sudoku
{
    class Program
    {
        static void Main(string[] args)
        {
            int[,] matrix = new int[9, 9];

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

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

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

            // debug
            using (var stream = new StreamWriter(System.Environment.CurrentDirectory + "\\output"))
            {
                for(int row = 0; row < 9; row++)
                {
                    for(int col = 0; col < 9; col++)
                    {
                        stream.Write(matrix[row, col]);
                    }
                    stream.Write("\r\n");
                }
            }
        }
    }
}

実行結果

引数でファイル名を取得する

Main()の引数args[]の中にコマンドパラメータが入っています。

今回使用する引数は、ファイル名１個だけですので、args.lengthが1以外の場合は、usageを表示して終了します。

ファイルの存在を確認する

今回はカレントフォルダに存在するファイルを対象にすることにします。

おそらく相対パスなら大丈夫かもしれませんが、絶対パスならエラーになるでしょう。

対策は後で考えます。力を入れるべきところはここじゃないので。

Environment.CurrentDirectoryにカレントフォルダが入っているので、これにファイル名をくっつけて、完全なファイルパスを作成します。

そして、File.Exists()でファイルの存在を確認します。存在しなければfalseが返るので、エラーメッセージを表示して終了します。

ファイルのデータを取り込む

テキストのデータ読み取りならStreamReaderを使うのが簡単でしょう。

StreamReaderでファイルを開いて、ファイルストリームを取得します。

usingを使うと、usingの中でExceptionが発生しても、適切なtry/catch処理をやってくれます。

まぁ、エラーが起こってもプログラムがファイルを掴んだままにならない、ということです。

usingの中でwhileループをおこない、ReadLine()でファイルから1行ずつ取り出します。

取り出した1行データをsplit()を使って、”,”(カンマ)で分割します。結果はstring[]になります。

これをさらにtryParse()でint型に変換します。

これで読み込んだ文字列が数字に変換されて取り込むことができます。

これを全てのデータに対して行います。

念のためフォーマットエラーも確認します。

まぁ、クラス構成はもうちょっと考えるとして、とりあえずはこんな感じで。