読者です 読者をやめる 読者になる 読者になる

数独を解く(別解:バックトラック法)

c#

Form1.cs

using System;
using System.Linq;
using System.Windows.Forms;

namespace 数独バックトラック法
{
    public partial class Form1 : Form
    {
        Button[] IDbutton = new Button[81];
        Button kensyo = new Button();
        Button zikko = new Button();
        Button newGame = new Button();

        int[] kazu = new int[81];
        readonly int[] next_position = { 0, 1, 2, 9, 10, 11, 18, 19, 20 };
        readonly int[] start_position = { 0, 3, 6, 27, 30, 33, 54, 57, 60 };

        public Form1()
        {
            InitializeComponent();
        }

        private void kensyo_Click(object sender, EventArgs e)
        {
            //数字の拾い出し
            int d;
            for (int i = 0; i < 81; i++)
            {
                int.TryParse(IDbutton[i].Text, out d);
                kazu[i] = d;
            }
            //検証を実行
            if (kensyo_do())
            {
                zikko.Enabled = true;
                kensyo.Enabled = false;
                foreach (Button a in IDbutton)
                {
                    a.Enabled = false;
                }
            }
            else
            {
                MessageBox.Show("入力が不適です", Application.ProductName
                    , MessageBoxButtons.OK, MessageBoxIcon.Information);
            }
        }
        private bool kensyo_do()
        {
            int[] box_kensyo = new int[9];
            int[] tate_kensyo = new int[9];
            int[] yoko_kensyo = new int[9];

            for (int i = 0; i < 9; i++)
            {
                for (int ii = 0; ii < 9; ii++)
                {
                    //3×3の検証
                    box_kensyo[ii] = kazu[start_position[i] + next_position[ii]];
                    //横の検証
                    yoko_kensyo[ii] = kazu[i * 9 + ii];
                    //縦の検証
                    tate_kensyo[ii] = kazu[i + ii * 9];
                }
                if (box_kensyo.Where(c => c > 0).Count() != box_kensyo.Where(c => c > 0).Distinct().Count()) return false;
                if (yoko_kensyo.Where(c => c > 0).Count() != yoko_kensyo.Where(c => c > 0).Distinct().Count()) return false;
                if (tate_kensyo.Where(c => c > 0).Count() != tate_kensyo.Where(c => c > 0).Distinct().Count()) return false;
            }
            return true;
        }
        private void newGame_Click(object sender, EventArgs e)
        {
            foreach (Button a in IDbutton)
            {
                a.Text = "";
                a.Enabled = true;
            }
            kensyo.Enabled = true;
            zikko.Enabled = false;
        }
        private void IDbutton_Click(object sender, EventArgs e)
        {
            if (((Button)sender).Text == "")
            {
                input inputform = new input();
                inputform.ShowDialog();
                ((Button)sender).Text = inputform.num;
                inputform.Dispose();
            }
            else
            {
                ((Button)sender).Text = "";
            }
        }
        private void zikko_Click(object sender, EventArgs e)
        {
            Try(kazu);
        }
        private void Try(int[] x)
        {
            //0(空欄)を探す→存在しない場合には-1を返す
            int blank = Array.IndexOf(kazu, 0);
            if (blank != -1)
            {
                for (int i = 1; i < 10; i++)
                {
                    if (isOK(blank,i,kazu))
                    {
                        kazu[blank] = i;
                        Try(kazu);
                        kazu[blank] = 0;
                    }
                }
            }
            else
            {
                for (int i = 0; i < 81; i++)
                {
                    IDbutton[i].Text = kazu[i].ToString();
                }
            }
        }
        private bool isOK(int x, int y, int[] z)
        {
            int yoko; int tate; int box;
            yoko = x / 9;
            tate = x % 9;
            box = (yoko / 3) * 3 + tate / 3;
            for (int i = 0; i < 9; i++)
            {
                if (z[yoko * 9 + i] == y) return false;
                if (z[tate + i * 9] == y) return false;
                if (z[start_position[box] + next_position[i]] == y) return false;
            }
            return true;
        }
    }
}

GUI.cs

using System;
using System.Drawing;
using System.Windows.Forms;

namespace 数独バックトラック法
{
    public partial class Form1 : Form
    {
        private void Form1_Load(object sender, EventArgs e)
        {
            this.SuspendLayout();
            //Form1の設定
            this.Height = 382; this.Width = 530;
            this.MinimizeBox = false; this.MaximizeBox = false;
            this.Text = "数独ソルバー(バックトラック法)";
            this.FormBorderStyle = FormBorderStyle.FixedSingle;
            //
            //IDbuttonの設定
            int[] gyo = { 10, 45, 80, 120, 155, 190, 230, 265, 300 };

            for (int i = 0; i < 81; i++)
            {
                IDbutton[i] = new Button();
                IDbutton[i].Text = "";
                IDbutton[i].Size = new Size(35, 35);
                IDbutton[i].Font = new Font("Arial", 14);
                IDbutton[i].Location = new Point(gyo[i % 9], gyo[i / 9]);
                IDbutton[i].Click += IDbutton_Click;
            }
            this.Controls.AddRange(IDbutton);
            //
            //新規、検証、実行ボタンの設定
            newGame.Text = "新規入力"; kensyo.Text = "検証"; zikko.Text = "実行";
            newGame.Size = new Size(150, 40);
            kensyo.Size = new Size(150, 40);
            zikko.Size = new Size(150, 40);
            newGame.Location = new Point(350, 190);
            kensyo.Location = new Point(350, 240);
            zikko.Location = new Point(350, 290);
            zikko.Enabled = false;
            newGame.Click += newGame_Click;
            kensyo.Click += kensyo_Click;
            zikko.Click += zikko_Click;
            this.Controls.AddRange(new Control[] { newGame, kensyo, zikko });
            //
            this.ResumeLayout();
        }
    }
}

input.cs

using System;
using System.Drawing;
using System.Windows.Forms;

namespace 数独バックトラック法
{
    public partial class input : Form
    {
        Button[] button = new Button[9];
        public string num;

        public input()
        {
            InitializeComponent();
            this.StartPosition = FormStartPosition.CenterParent;
        }

        private void input_Load(object sender, EventArgs e)
        {
            this.SuspendLayout();
            this.FormBorderStyle = FormBorderStyle.None;
            this.Height = 250; this.Width = 250;

            int[] position = { 10, 90, 170 };
            for (int i = 0; i < 9; i++)
            {
                button[i] = new Button();
                button[i].Size = new Size(70, 70);
                button[i].Text = (i + 1).ToString();
                button[i].Font = new Font("Arial", 20);
                button[i].Location = new Point(position[i % 3], position[i / 3]);
                button[i].Click += button_Click;
            }
            this.Controls.AddRange(button);
            this.ResumeLayout();
        }
        private void button_Click(object sender, EventArgs e)
        {
            num = ((Button)sender).Text;
            this.Close();
        }
    }
}

数独を解く(6日目)

c#

実行ボタンのClickイベントハンドラを記述する。

        private void zikko_Click(object sender, EventArgs e)
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            ////////////////////////////////////////////////////////////////////////////////////////////////////////////
            string[] _kugiri = { "\r\n" };
            string[] all_data = Properties.Resources.resource.Split(_kugiri, StringSplitOptions.RemoveEmptyEntries);
            string[] num_data = Enumerable.Repeat("999999999", 9).ToArray();
            int[] data_num = new int[9];
            ////////////////////////////////////////////////////////////////////////////////////////////////////////////
            for (int i = 0; i < 9; i++)
            {
                for (int u = 0; u < 81; u++)
                {
                    if (kazu[start_position[u / 9] + next_position[u % 9]] == i + 1)
                    {
                        num_data[i] = num_data[i].Remove(u / 9, 1);
                        num_data[i] = num_data[i].Insert(u / 9, (u % 9).ToString());
                    }
                }
            }
            for (int i = 0; i < 9; i++)
            {
                List<string> possible_array = new List<string>();
                foreach (string aa in all_data)
                {
                    bool hantei = true;
                    for (int char_no = 0; char_no < 9; char_no++)
                    {
                        if (num_data[i][char_no] == '9')
                        {
                            if (kazu[start_position[char_no] + next_position[(int)(aa[char_no] - '0')]] != 0)
                            {
                                hantei = false;
                                break;
                            }
                        }
                        else
                        {
                            if (num_data[i][char_no] != aa[char_no])
                            {
                                hantei = false;
                                break;
                            }
                        }
                    }
                    if (hantei)
                    {
                        possible_array.Add(aa);
                    }
                }
                data_num[i] = possible_array.Count();
                each_data[i] = possible_array.ToArray();
            }
            for (int i = 0; i < 9; i++) sort_index[i] = i;
            Array.Sort(data_num, sort_index);
            for (each_data_para[0] = 0; each_data_para[0] < data_num[0]; each_data_para[0]++)
            {
                for (each_data_para[1] = 0; each_data_para[1] < data_num[1]; each_data_para[1]++)
                {
                    if (!hantei(1)) continue;
                    for (each_data_para[2] = 0; each_data_para[2] < data_num[2]; each_data_para[2]++)
                    {
                        if (!hantei(2)) continue;
                        for (each_data_para[3] = 0; each_data_para[3] < data_num[3]; each_data_para[3]++)
                        {
                            if (!hantei(3)) continue;
                            for (each_data_para[4] = 0; each_data_para[4] < data_num[4]; each_data_para[4]++)
                            {
                                if (!hantei(4)) continue;
                                for (each_data_para[5] = 0; each_data_para[5] < data_num[5]; each_data_para[5]++)
                                {
                                    if (!hantei(5)) continue;
                                    for (each_data_para[6] = 0; each_data_para[6] < data_num[6]; each_data_para[6]++)
                                    {
                                        if (!hantei(6)) continue;
                                        for (each_data_para[7] = 0; each_data_para[7] < data_num[7]; each_data_para[7]++)
                                        {
                                            if (!hantei(7)) continue;
                                            for (each_data_para[8] = 0; each_data_para[8] < data_num[8]; each_data_para[8]++)
                                            {
                                                if (hantei(8))
                                                {
                                                    goto finish;
                                                }
                                                    
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        finish:
            for (int i = 0; i < 9; i++)
            {
                for (int n = 0; n < 9; n++)
                {
                    IDbutton[start_position[n] + next_position[(int)(each_data[sort_index[i]][each_data_para[i]][n] - '0')]].Text = (sort_index[i] + 1).ToString();
                }
            }
            sw.Stop(); 
            MessageBox.Show(sw.Elapsed.ToString());
            foreach (Button a in IDbutton)
            {
                a.Enabled = true;
            }
            kensyo.Enabled = true;
            zikko.Enabled = false;
        }
        private bool hantei(int para)
        {
            for (int i = 0; i < para; i++)
            {
                for (int ii = 0; ii < 9; ii++)
                {
                    if (each_data[sort_index[i]][each_data_para[i]][ii] == each_data[sort_index[para]][each_data_para[para]][ii]) return false;
                }
            }
            return true;
        }

数独を解く(5日目)

c#

新規ボタンのClickイベントハンドラを記述する。

        private void newGame_Click(object sender, EventArgs e)
        {
            foreach (Button a in IDbutton)
            {
                a.Text = "";
                a.Enabled = true;
            }
            kensyo.Enabled = true;
            zikko.Enabled = false;
        }

数独を解く(4日目)

c#

検証ボタンのClickイベントハンドラを記述。

        private void kensyo_Click(object sender, EventArgs e)
        {
            //数字の拾い出し
            int d;
            for (int i = 0; i < 81; i++)
            {
                int.TryParse(IDbutton[i].Text, out d);
                kazu[i] = d;
            }
            //検証を実行
            if (kensyo_do())
            {
                zikko.Enabled = true;
                kensyo.Enabled = false;
                foreach (Button a in IDbutton)
                {
                    a.Enabled = false;
                }
            }
            else
            {
                MessageBox.Show("入力が不適です",Application.ProductName
                    , MessageBoxButtons.OK, MessageBoxIcon.Information);
            }
        }
        private bool kensyo_do()
        {
            int[] box_kensyo = new int[9];
            int[] tate_kensyo = new int[9];
            int[] yoko_kensyo = new int[9];
            
            for (int i = 0; i < 9; i++)
            {
                for (int ii = 0; ii < 9; ii++)
                {
                    //3×3の検証
                    box_kensyo[ii] = kazu[start_position[i] + next_position[ii]];
                    //横の検証
                    yoko_kensyo[ii] = kazu[i * 9 + ii];
                    //縦の検証
                    tate_kensyo[ii] = kazu[i + ii * 9];
                }
                if (box_kensyo.Where(c => c > 0).Count() != box_kensyo.Where(c => c > 0).Distinct().Count()) return false;
                if (yoko_kensyo.Where(c => c > 0).Count() != yoko_kensyo.Where(c => c > 0).Distinct().Count()) return false;
                if (tate_kensyo.Where(c => c > 0).Count() != tate_kensyo.Where(c => c > 0).Distinct().Count()) return false;
            }
            return true;
        }

数独を解く(3日目)

c#

以下のプログラムをコンソールアプリケーションとして実行する。
「resource.txt」というファイルが作られる。
出来たファイルをおおもとのプログラムにリソースとして取り込む。

using System.Collections.Generic;

namespace 下準備
{
    class Program
    {
        static void Main(string[] args)
        {
            List<int> gyo = new List<int>();
            List<string> result = new List<string>();


            for (int m0 = 0; m0 < 9; m0++)
            {
                for (int m1 = 0; m1 < 9; m1++)
                {
                    for (int m2 = 0; m2 < 9; m2++)
                    {
                        if (hantei(m0, m1, m2))
                        {
                            gyo.Add(m0 * 100 + m1 * 10 + m2);
                        }
                    }
                }
            }
            int count = gyo.Count;
            for (int m0 = 0; m0 < count; m0++)
            {
                for (int m1 = 0; m1 < count; m1++)
                {
                    for (int m2 = 0; m2 < count; m2++)
                    {
                        if (hantei2(gyo[m0], gyo[m1], gyo[m2]))
                        {
                            result.Add((gyo[m0] * 1000000 + gyo[m1] * 1000 + gyo[m2]).ToString("000000000"));
                        }
                    }
                }
            }
            System.IO.File.WriteAllLines(@"resource.txt", result);
        }

        private static bool hantei(int a, int b, int c)
        {
            if (a / 3 != b / 3 && a / 3 != c / 3 && b / 3 != c / 3)
            {
                return true;
            }
            else
            {
                return false;
            }
        }

        private static bool hantei2(int a, int b, int c)
        {
            if (
                (a / 100) % 3 != (b / 100) % 3 &&
                (a / 100) % 3 != (c / 100) % 3 &&
                (b / 100) % 3 != (c / 100) % 3
                )
            {
                if (
                    ((a % 100) / 10) % 3 != ((b % 100 / 10) % 3) &&
                    ((a % 100) / 10) % 3 != ((c % 100 / 10) % 3) &&
                    ((b % 100) / 10) % 3 != ((c % 100 / 10) % 3)
                    )
                {
                    if (
                        (a % 10) % 3 != (b % 10) % 3 &&
                        (a % 10) % 3 != (c % 10) % 3 &&
                        (b % 10) % 3 != (c % 10) % 3
                        )
                    {
                        return true;
                    }
                    else return false;
                }
                else
                {
                    return false;
                }
            }
            else
            {
                return false;
            }
        }
    }
}

数独を解く(2日目)

c#

ユーザーフォームを追加する
(input.cs)
Loadのイベントハンドラを作成する必要あり。

using System;
using System.Drawing;
using System.Windows.Forms;

namespace 数独をとく
{
    public partial class input : Form
    {
        Button[] button = new Button[9];
        public string num;

        public input()
        {
            InitializeComponent();
            this.StartPosition = FormStartPosition.CenterParent;
        }

        private void input_Load(object sender, EventArgs e)
        {
            this.SuspendLayout();
            this.FormBorderStyle = FormBorderStyle.None;
            this.Height = 250; this.Width = 250;

            int[] position = { 10, 90, 170 };
            for (int i = 0; i < 9; i++)
            {
                button[i] = new Button();
                button[i].Size = new Size(70, 70);
                button[i].Text = (i + 1).ToString();
                button[i].Font = new Font("Arial", 20);
                button[i].Location = new Point(position[i % 3], position[i / 3]);
                button[i].Click += button_Click;
            }
            this.Controls.AddRange(button);
            this.ResumeLayout();
        }
        private void button_Click(object sender, EventArgs e)
        {
            num = ((Button)sender).Text;
            this.Close();
        }
    }
}

その後メインフォームのIDbuttonのClickイベントハンドラを記述。

        private void IDbutton_Click(object sender, EventArgs e)
        {
            if (((Button)sender).Text == "")
            {
                input inputform = new input();
                inputform.ShowDialog();
                ((Button)sender).Text = inputform.num;
                inputform.Dispose();
            }
            else
            {
                ((Button)sender).Text = "";
            }
        }

数独を解く(1日目)

c#

まずはGUIまわりから(GUI.cs)
メインフォーム(Form1)のLoadのイベントハンドラーを作成する必要あり。

using System;
using System.Drawing;
using System.Windows.Forms;

namespace 数独ソルバー
{
    public partial class Form1 : Form
    {
        private void Form1_Load(object sender, EventArgs e)
        {
            this.SuspendLayout();
            //Form1の設定
            this.Height = 382; this.Width = 530;
            this.MinimizeBox = false; this.MaximizeBox = false;
            this.Text = "数独ソルバー";
            this.FormBorderStyle = FormBorderStyle.FixedSingle;
            //
            //IDbuttonの設定
            int[] gyo = { 10, 45, 80, 120, 155, 190, 230, 265, 300 };

            for (int i = 0; i < 81; i++)
            {
                IDbutton[i] = new Button();
                IDbutton[i].Text = "";
                IDbutton[i].Size = new Size(35, 35);
                IDbutton[i].Font = new Font("Arial", 14);
                IDbutton[i].Location = new Point(gyo[i % 9], gyo[i / 9]);
                IDbutton[i].Click += IDbutton_Click;
            }
            this.Controls.AddRange(IDbutton);
            //
            //新規、検証、実行ボタンの設定
            newGame.Text = "新規入力"; kensyo.Text = "検証"; zikko.Text = "実行";
            newGame.Size = new Size(150, 40);
            kensyo.Size = new Size(150, 40); 
            zikko.Size = new Size(150, 40);
            newGame.Location = new Point(350, 190);
            kensyo.Location = new Point(350, 240); 
            zikko.Location = new Point(350, 290);
            zikko.Enabled = false;
            newGame.Click+=newGame_Click;
            kensyo.Click += kensyo_Click;
            zikko.Click += zikko_Click;
            this.Controls.AddRange(new Control[] { newGame, kensyo, zikko });
            //
            this.ResumeLayout();
        }
    }
}

メインプログラム(Form1.cs)

using System;
using System.Windows.Forms;
using System.Linq;
using System.Collections.Generic;
using System.Diagnostics;

namespace 数独をとく
{
    public partial class Form1 : Form
    {
        Button[] IDbutton = new Button[81];
        Button kensyo = new Button();
        Button zikko = new Button();
        Button newGame = new Button();

        int[] kazu = new int[81];
        readonly int[] next_position = { 0, 1, 2, 9, 10, 11, 18, 19, 20 };
        readonly int[] start_position = { 0, 3, 6, 27, 30, 33, 54, 57, 60 };

        string[][] each_data = new string[9][];
        int[] each_data_para = new int[9];
        int[] sort_index = new int[9];

        public Form1()
        {
            InitializeComponent();
        }

        private void kensyo_Click(object sender, EventArgs e)
        {
            //後で記述
        }
       
        private bool kensyo_do()
        {
            //後で記述
        }

        private void zikko_Click(object sender, EventArgs e)
        {
            //後で記述
        }

        private bool hantei(int para)
        {
            //後で記述
        }
        
        private void newGame_Click(object sender, EventArgs e)
        {
            //後で記述
        }
        
        private void IDbutton_Click(object sender, EventArgs e)
        {
            //後で記述
        }
    }
}