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

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

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

実行結果はこちら

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

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

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

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

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

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

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

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

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

まずは、問題を読み取るところから。(そこからかよ!)

とにかく、今回は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[]の中にコマンドパラメータが入っています。

今回使用する引数は、ファイル名1個だけですので、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型に変換します。

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

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

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

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

【プログラミング】勇者と魔王の戦い

Tech commitの課題で、面白そうなテーマだったので、挑戦してみました。

https://github.com/takishita2nd/battle_rpg

  • 勇者と魔王が交互に攻撃する
  • 一定確率で攻撃を回避する
  • 一定確率でクリティカルヒット(ダメージ1.5倍)になる
  • どっちが勝利したかを表示する
using System;

namespace battle_rpg
{
    public static class Common
    {
        public static bool roleJudge(int rate)
        {
            bool judge = false;
            Random r = new Random();
            int value = r.Next(0, 100);
            if(value < rate) {
                judge = true;
            }
            return judge;
        }
    }
}

これは乱数を使って、命中やクリティカル判定などの確率判定を行うメソッドです。

引数に確率(%)を受け取り、乱数を0〜100の範囲で発生させて、その値が確率以下ならばtrueを返します。

using System;

namespace battle_rpg
{
    public class Charactor
    {
        private const String Statusformat = "{0}:HP{1} 攻撃力{2}";
        private const String AttackFormat = "{0}の攻撃!{1}に{2}のダメージ";
        private const String CriticalAttackFormat = "{0}の攻撃!クリティカルヒット!{1}に{2}のダメージ";
        private const String EvasionFormat = "{0}の攻撃!{1}は攻撃をかわした";
        public string Name {get;}
        public int Hp {get; set;}
        public int Attack {get;}
        public int evasionRate { get;}
        public int criticalRate { get;}

        public Charactor(string _name, int _hp, int _attack)
        {
            this.Name = _name;
            this.Hp = _hp;
            this.Attack = _attack;
            this.evasionRate = 5;
            this.criticalRate = 5;
        }

        /**
         * ターゲットを攻撃
         * <param>  _target 攻撃対象
         * <return> 与えたダメージ
         */
        public String doAttack(Charactor _target)
        {
            String message = String.Empty;
            if(isHit(_target)) {
                int damage = this.Attack;
                if(isCritical()) {
                    damage = (int)(damage * 1.5);
                    message = String.Format(CriticalAttackFormat, this.Name, _target.Name, damage);
                } else {
                    message = String.Format(AttackFormat, this.Name, _target.Name, damage);
                }
                _target.Hp -= damage;
            } else {
                message = String.Format(EvasionFormat, this.Name, _target.Name);
            }

            return message;
        }

        /**
         * 命中判定
         * <param>  _target 攻撃対象
         * <return> true:命中
         */
        private bool isHit(Charactor _target)
        {
            bool hit = true;
            if(Common.roleJudge(_target.evasionRate)) {
                hit = false;
            }
            return hit;
        }

        /**
         * クリティカル判定
         * <return> true:クリティカル
         */
        private bool isCritical()
        {
            bool critical = false;
            if(Common.roleJudge(this.criticalRate)) {
                critical = true;
            }
            return critical;
        }

        /**
         * 死亡判定
         * <return> true:死亡
         */
        public bool isDie()
        {
            bool die = false;
            if(this.Hp <= 0) {
                die = true;
            }
            return die;
        }

        public String showStatus()
        {
            return String.Format(Statusformat, this.Name, this.Hp, this.Attack);
        }
    }
}

勇者や魔王を扱うクラスです。

このクラスの中でHPや攻撃力などを保持します。

メインはdoAttack()メソッド。この中で命中判定やクリティカル判定をおこない、攻撃対象(引数)のHPを減らしていきます。

using System;

namespace battle_rpg
{
    public class Battle
    {
        private Charactor yusha;
        private Charactor maou;
        private const String DieFormat = "{0}は倒れた。";
        public Battle()
        {
            yusha = new Charactor("勇者", 300, 15);
            maou = new Charactor("魔王", 400, 9);
        }

        public void execute()
        {
            bool nowBattle = true;
            while(nowBattle) {
                // HP表示
                Console.WriteLine(yusha.showStatus());
                Console.WriteLine(maou.showStatus());
                Console.WriteLine();

                // 勇者の攻撃
                Console.WriteLine(yusha.doAttack(maou));

                // 魔王死亡判定
                if(maou.isDie()) {
                    Console.WriteLine();
                    Console.WriteLine(DieFormat, maou.Name);
                    nowBattle = false;
                    Console.WriteLine("世界に平和が訪れた。");
                }

                if(nowBattle == false) {
                    return;
                }

                // 魔王の攻撃
                Console.WriteLine(maou.doAttack(yusha));

                // 勇者死亡判定
                if(yusha.isDie()) {
                    Console.WriteLine();
                    Console.WriteLine(DieFormat, yusha.Name);
                    nowBattle = false;
                    Console.WriteLine("世界は征服された。");
                }
                Console.WriteLine();
            }
        }
    } 
}

実際にバトルを行うクラスです。

コンストラクタで勇者と魔王のステータスを設定、execute()でどちらかが負けるまでループを行います。

using System;

namespace battle_rpg
{
    class Program
    {
        static void Main(string[] args)
        {
            Battle battle = new Battle();
            battle.execute();
        }
    }
}

メイン関数。Battleクラスをインスタンス化してexecute()を実行しているだけです。

とりあえず、こんな感じで要求されている処理はできました。

カスタマイズすれば色々と拡張できそうですね。