數獨解算器(ASP.NET 2.0)

2019-11-18 16:41:56

字體：大中小

來源：轉載

供稿：網友

數獨游戲在9x9的方格內進行，分為3x3的小方格，被稱為“區”。
數獨游戲首先從已經填入數字的格子開始。
數獨游戲的目的是根據下列規則，用1至9之間的數字填滿空格：
每個數字在每一行、每一列和每一區只能出現一次。
我在 linux 服務器(請參見“在 Linux 下運行 asp.net 2.0”)上用 ASP.NET 2.0 實現了一個數獨解算器。
http://www.sudoku.name 網站上也有一個用戶界面相當不錯的“數獨解算器” ，但是其算法太差了，運算速度比我的算法慢多了。以其網站上的“#5328”謎題(也是我的數獨解算器的例題)為例，它需要大約四個小時才能給出答案，而我的解算器不到一秒鐘就可以給出答案。從它的運算過程來算，估計是逐個空格進行解算。而我的算法是先找出能填入數字個數最少的空格進行解算。算法這個微小的改進，就極大地提高了計算效率。好了，廢話少說，下面就是源程序：

1. sudoku.aspx:
1<%@ Page Language="C#" inherits="Skyiv.Ben.Web.SudokuPage" %>
2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
            " 3<html xmlns=" 4<head runat="server">
5 <title>銀河 - 數獨</title>
6</head>
7<body>
8 <form id="form1" runat="server">
9 <asp:Button Text="返回" OnClick="BtnUriHome_Click" runat="server" />
10 <asp:Button Text="開始" OnClick="BtnSubmit_Click" runat="server" />
11 <hr />
12 <div>
13 <a href="http://www.sudoku.name/index-cn.php" target="_blank">數獨游戲</a>
14 在9x9的方格內進行，分為3x3的小方格，被稱為“區”。<br />
15 數獨游戲首先從已經填入數字的格子開始。<br />
16 數獨游戲的目的是根據下列規則，用1至9之間的數字填滿空格：<br />
17 http://www.49028c.com 每個數字在每一行、每一列和每一區只能出現一次。<br />
18 </div>
19 <div>
20 <asp:TextBox Runat="Server" Id="tbxInput" MaxLength="512" Wrap="False"
21    TextMode="MultiLine" Columns="15" Rows="14" />
22 <asp:TextBox Runat="Server" Id="tbxOutput" ReadOnly="True" Wrap="False"
23    TextMode="MultiLine" Columns="15" Rows="14" />
24 </div>
25 </form>
26</body>
27</html>
28
2. sudoku.aspx.cs:
1using System;
2using System.IO;
3using System.Web.UI;
4using System.Web.UI.WebControls;
5using Skyiv.Ben.Etc;
6
7namespace Skyiv.Ben.Web
8{
9 public class SudokuPage : Page
10 {
11    PRotected TextBox tbxInput;
12    protected TextBox tbxOutput;
13
14    public void Page_Load(object sender, EventArgs e)
15    {
16      if (IsPostBack) return;
17      tbxInput.Text =    "+---+---+---+/n|2..|||/n|8..|1..|.2.|/n"
18        + "|..5|.7.|.3.|/n+---+---+---+/n|.7.|.3.|1..|/n|.9.|.4.|.8.|/n"
19        + "|..4||.7.|/n+---+---+---+/n|.3.|.9.|6..|/n|.8.|..5|..3|/n"
20        + "|||..5|/n+---+---+---+";
21    }
22
23    public void BtnUriHome_Click(object sender, EventArgs e)
24    {
25      Response.Redirect(Pub.UriHome);
26    }
27
28    public void BtnSubmit_Click(object sender, EventArgs e)
29    {
30      try
31      {
32        Sudoku sudoku = new Sudoku(new StringReader(tbxInput.Text));
33        StringWriter writer = new StringWriter();
34        sudoku.Out(writer);
35        tbxOutput.Text = writer.ToString();
36      }
37      catch (Exception ex)
38      {
39        tbxOutput.Text = "Error: " + ex.Message;
40      }
41    }
42 }
43}
44
3. sudoku.cs:
1using System;
2using System.IO;
3using System.Collections.Generic;
4
5namespace Skyiv.Ben.Etc
6{
7 sealed class Sudoku
8 {
9    byte[,] input, output;
10    int steps = 0;
11
12    public Sudoku(TextReader reader)
13    {
14      input = new byte[9, 9];
15      for (int y = 0; y < 9; )
16      {
17        string s = reader.ReadLine();
18        if (s == null) break;
19        s = s.Replace('.', '0');
20        int x = 0;
21        for (int i = 0; i < s.Length; i++)
22          if (Char.IsDigit(s, i) && x < 9) input[x++, y] = (byte)(s[i] - '0');
23        if (x != 0) y++;
24      }
25    }
26
27    public void Out(TextWriter writer)
28    {
29      Compute(input);
30      Out(writer, output);
31    }
32
33    void Out(TextWriter writer, byte[,] output)
34    {
35      for (int y = 0; y <= output.GetLength(1); y++)
36      {
37        if (y % 3 == 0) writer.WriteLine("+---+---+---+");
38        if (y >= output.GetLength(1)) break;
39        for (int x = 0; x <= output.GetLength(0); x++)
40        {
41          if (x % 3 == 0) writer.Write('|');
42          if (x >= output.GetLength(0)) break;
43          writer.Write((output[x, y] == 0) ? '.' : (char)(output[x, y] + '0'));
44        }
45        writer.WriteLine();
46      }
47    }
48
49    bool Compute(byte[,] input)
50    {
51      List<byte[,]> list = StepIt(input);
52      if (list == null) return true;
53      foreach (byte[,] temp in list) if (Compute(temp)) return true;
54      return false;
55    }
56
57    // return null for finish
58    List<byte[,]> StepIt(byte[,] input)
59    {
60      if (steps++ > 100000) throw new Exception("太復雜了");
61      output = input;
62      int theX = -1, theY = -1;
63      byte[] theDigits = null;
64      for (int y = 0; y < input.GetLength(1); y++)
65      {
66        for (int x = 0; x < input.GetLength(0); x++)
67        {
68          if (input[x, y] != 0) continue;
69          byte[] digits = GetDigits(input, x, y);
70          if (digits.Length == 0) return new List<byte[,]>();
71          if (theDigits != null && theDigits.Length <= digits.Length) continue;
72          theX = x;
73          theY = y;
74          theDigits = digits;
75        }
76      }
77      if (theDigits == null) return null;
78      List<byte[,]> result = new List<byte[,]>();
79      foreach (byte digit in theDigits)
80      {
81        byte[,] temp = (byte[,])input.Clone();
82        temp[theX, theY] = digit;
83        result.Add(temp);
84      }
85      return result;
86    }
87
88    byte[] GetDigits(byte[,] input, int x, int y)
89    {
90      bool[] mask = new bool[10];
91      for (int i = 0; i < 9; i++)
92      {
93        mask[input[x, i]] = true;
94        mask[input[i, y]] = true;
95      }
96      for (int i = x / 3 * 3; i < x / 3 * 3 + 3; i++)
97        for (int j = y / 3 * 3; j < y / 3 * 3 + 3; j++)
98          mask[input[i, j]] = true;
99      List<byte> list = new List<byte>();
100      for (int i = 1; i < mask.Length; i++) if (!mask[i]) list.Add((byte)i);
101      return list.ToArray();
102    }
103 }
104}
105
以上代碼都很簡單，也不需要再另外解說了。
http://www.49028c.com/skyivben/archive/2007/01/26/631233.html