はじめに
最後に数独を解くためのコードを書きます。バックトラック法を用いています。単純化のため複数解が存在していても一つ見つけたら終了するようになっています。コードは非常に短いですが問題によっては時間がかかる可能性があります。C#のコード
GUIを定義したファイル（settings.cs）に以下の一文を追加しました。solveBtn.Click += Solve_Click;
その後、メインファイル（Form1.cs）に以下の3つを追記しました。
private void Solve_Click(object sender, EventArgs e) { solveBtn.Enabled = false; newBtn.Enabled = false; if (Try()) { for (int i = 0; i < 81; i++) { numberBtn[i].Text = kazu[i].ToString(); } foreach (Button btn in numberBtn) { btn.Enabled = true; } kensyoBtn.Enabled = true; newBtn.Enabled = true; } }
private bool Try() { int blank_position = Array.IndexOf(kazu, 0); if (blank_position == -1) return true; for (int i = 1; i < 10; i++) { if (!(isOK(blank_position, i, kazu))) continue; kazu[blank_position] = i; if(Try()) return true; kazu[blank_position] = 0; } return false; }
private bool isOK(int blk_position, int try_numnber, int[] _kazu) { int row_index = blk_position / 9; int col_index = blk_position % 9; int box_index = (row_index / 3) * 3 + col_index / 3; for (int i = 0; i < 9; i++) { if (_kazu[row_index * 9 + i] == try_numnber) return false; if (_kazu[col_index + i * 9] == try_numnber) return false; if (_kazu[box_start[box_index] + box_offset[i]] == try_numnber) return false; } return true; }
これだけで数独は解けます。
最終的なファイル
書いたファイルは3つです。「Form1.cs」「settings.cs」「inputform.cs」です。
Form1.cs
using System; using System.Drawing; using System.Linq; using System.Windows.Forms; namespace WindowsFormsApp1 { public partial class Form1 : Form { private const int TLPSize = 400; private const int FLPWidth = 150; public static Font buttonFont = new Font("游ゴシック", 12); private readonly int[] box_start = { 0, 3, 6, 27, 30, 33, 54, 57, 60 }; private readonly int[] box_offset = { 0, 1, 2, 9, 10, 11, 18, 19, 20 }; int[] kazu = new int[81]; public Form1() { Load += Form1_load; } private void ClicknumberBtn(object sender, EventArgs e) { if (((Button)sender).Text == "") { InputForm input = new InputForm(); int Form1_x = Left; int Form1_y = Top; int x_min = ((Button)sender).Left; int y_min = ((Button)sender).Top; int width_half = ((Button)sender).Width / 2; input.Left = Form1_x + x_min + width_half; input.Top = Form1_y + y_min + width_half; input.StartPosition = FormStartPosition.Manual; input.ShowDialog(); ((Button)sender).Text = input.result; input.Dispose(); } else { ((Button)sender).Text = ""; } } private void Kensyo_Click(object sender, EventArgs e) { int d; for (int i = 0; i < 81; i++) { int.TryParse(numberBtn[i].Text, out d); kazu[i] = d; } if (Kensyo_do()) { solveBtn.Enabled = true; kensyoBtn.Enabled = false; foreach (Button btn in numberBtn) { btn.Enabled = false; } } else { MessageBox.Show("入力が不適です", "結果" , MessageBoxButtons.OK, MessageBoxIcon.Information); } } private bool Kensyo_do() { int[] box_test = new int[9]; int[] row_test = new int[9]; int[] col_test = new int[9]; for (int i = 0; i < 9; i++) { for (int ii = 0; ii < 9; ii++) { box_test[ii] = kazu[box_start[i] + box_offset[ii]]; row_test[ii] = kazu[i * 9 + ii]; col_test[ii] = kazu[i + ii * 9]; } if (box_test.Where(c => c > 0).Count() != box_test.Where(c => c > 0).Distinct().Count()) { return false; } if (row_test.Where(c => c > 0).Count() != row_test.Where(c => c > 0).Distinct().Count()) { return false; } if (col_test.Where(c => c > 0).Count() != col_test.Where(c => c > 0).Distinct().Count()) { return false; } } return true; } private void New_Click(object sender, EventArgs e) { foreach (Button btn in numberBtn) { btn.Enabled = true; btn.Text = ""; } kensyoBtn.Enabled = true; solveBtn.Enabled = false; } private void Solve_Click(object sender, EventArgs e) { solveBtn.Enabled = false; newBtn.Enabled = false; if (Try()) { for (int i = 0; i < 81; i++) { numberBtn[i].Text = kazu[i].ToString(); } foreach (Button btn in numberBtn) { btn.Enabled = true; } kensyoBtn.Enabled = true; newBtn.Enabled = true; } } private bool Try() { int blank_position = Array.IndexOf(kazu, 0); if (blank_position == -1) return true; for (int i = 1; i < 10; i++) { if (!(isOK(blank_position, i, kazu))) continue; kazu[blank_position] = i; if(Try()) return true; kazu[blank_position] = 0; } return false; } private bool isOK(int blk_position, int try_numnber, int[] _kazu) { int row_index = blk_position / 9; int col_index = blk_position % 9; int box_index = (row_index / 3) * 3 + col_index / 3; for (int i = 0; i < 9; i++) { if (_kazu[row_index * 9 + i] == try_numnber) return false; if (_kazu[col_index + i * 9] == try_numnber) return false; if (_kazu[box_start[box_index] + box_offset[i]] == try_numnber) return false; } return true; } } }
settings.cs
using System; using System.Drawing; using System.Windows.Forms; namespace WindowsFormsApp1 { public partial class Form1 : Form { FlowLayoutPanel flp1 = new FlowLayoutPanel(); TableLayoutPanel tlp1 = new TableLayoutPanel(); Button[] numberBtn = new Button[81]; Button dummyBtn = new Button(); Button newBtn = new Button(); Button kensyoBtn = new Button(); Button solveBtn = new Button(); private void Form1_load(object sender, EventArgs e) { int[] btn_position = { 0, 1, 2, 4, 5, 6, 8, 9, 10 }; Text = "solver"; for (int i = 0; i < 3; i++) { tlp1.RowStyles.Add(new RowStyle(SizeType.Percent, 11f)); tlp1.ColumnStyles.Add(new ColumnStyle(SizeType.Percent, 11f)); } tlp1.RowStyles.Add(new RowStyle(SizeType.Percent, .5f)); tlp1.ColumnStyles.Add(new ColumnStyle(SizeType.Percent, .5f)); for (int i = 0; i < 3; i++) { tlp1.RowStyles.Add(new RowStyle(SizeType.Percent, 11f)); tlp1.ColumnStyles.Add(new ColumnStyle(SizeType.Percent, 11f)); } tlp1.RowStyles.Add(new RowStyle(SizeType.Percent, .5f)); tlp1.ColumnStyles.Add(new ColumnStyle(SizeType.Percent, .5f)); for (int i = 0; i < 3; i++) { tlp1.RowStyles.Add(new RowStyle(SizeType.Percent, 11f)); tlp1.ColumnStyles.Add(new ColumnStyle(SizeType.Percent, 11f)); } tlp1.Size = new Size(TLPSize, TLPSize); for (int i = 0; i < 81; i++) { numberBtn[i] = new Button(); numberBtn[i].Text = ""; numberBtn[i].Dock = DockStyle.Fill; numberBtn[i].Margin = new Padding(0); numberBtn[i].Font = buttonFont; numberBtn[i].Click += ClicknumberBtn; tlp1.Controls.Add(numberBtn[i], btn_position[i % 9], btn_position[i / 9]); } SetClientSizeCore(TLPSize + FLPWidth, TLPSize); Controls.Add(tlp1); flp1.Width = FLPWidth; flp1.Dock = DockStyle.Right; flp1.FlowDirection = FlowDirection.BottomUp; Controls.Add(flp1); dummyBtn.Size = new Size(flp1.Width, 0); newBtn.AutoSize = true; newBtn.Font = buttonFont; newBtn.Text = "新規入力"; newBtn.Width = (int)(flp1.Width * 0.9); newBtn.Anchor = AnchorStyles.None; newBtn.Click += New_Click; kensyoBtn.AutoSize = true; kensyoBtn.Font = buttonFont; kensyoBtn.Text = "検証"; kensyoBtn.Width = newBtn.Width; kensyoBtn.Anchor = AnchorStyles.None; kensyoBtn.Click += Kensyo_Click; solveBtn.AutoSize = true; solveBtn.Font = buttonFont; solveBtn.Text = "実行"; solveBtn.Width = newBtn.Width; solveBtn.Anchor = AnchorStyles.None; solveBtn.Enabled = false; solveBtn.Click += Solve_Click; flp1.Controls.Add(dummyBtn); flp1.Controls.Add(newBtn); flp1.Controls.Add(solveBtn); flp1.Controls.Add(kensyoBtn); } } }
inputform.cs
using System; using System.Drawing; using System.Windows.Forms; namespace WindowsFormsApp1 { public class InputForm : Form { public string result; private const int TLPSize = 180; TableLayoutPanel tlp = new TableLayoutPanel(); Button[] numberBtn = new Button[9]; //コンストラクタ public InputForm() { FormBorderStyle = FormBorderStyle.None; int TLPSize_real = (TLPSize / 3) * 3; SetClientSizeCore(TLPSize_real, TLPSize_real); tlp.Size = new Size(TLPSize_real, TLPSize_real); Controls.Add(tlp); for (int i = 0; i < 3; i++) { tlp.RowStyles.Add(new RowStyle(SizeType.Absolute, (float)(TLPSize / 3))); tlp.ColumnStyles.Add(new ColumnStyle(SizeType.Absolute, (float)(TLPSize / 3))); } for (int i =0; i < 9; i++) { numberBtn[i] = new Button(); numberBtn[i].Font = Form1.buttonFont; numberBtn[i].Text = (i + 1).ToString(); numberBtn[i].Dock = DockStyle.Fill; numberBtn[i].Margin = new Padding(0); numberBtn[i].Click += ClicknumberBtn; tlp.Controls.Add(numberBtn[i], i % 3, i / 3); } } private void ClicknumberBtn(object sender, EventArgs e) { result = ((Button)sender).Text; Close(); } } }
環境
Windows 11 Visual Studio Community 2022
前回までの記事
5年ぶりに数独を解く Part 15年ぶりに数独を解く Part 2
5年ぶりに数独を解く Part 3
