开发学院 WEB开发 ASP.NET 数独解算器(ASP.NET 2.0) 阅读

数独解算器(ASP.NET 2.0)

　2007-01-27 17:47:06　来源：WEB开发网　　　

核心提示：数独游戏在9x9的方格内进行，分为3x3的小方格，数独解算器(ASP.NET 2.0)，被称为“区”，数独游戏首先从已经填入数字的格子开始，用1至9之间的数字填满空格：<br />17 http://www.cncms.com 每个数字在每一行、每一列和每一区只能出现一次，<br />18

数独游戏在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"
　　　　　 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
3<html xmlns="http://www.w3.org/1999/xhtml" >
4<head runat="server">
5 <title>银河 - 数独</title>
6</head>
7<body>
8 <form id="form1" runat="server">
9 <asp:Button Text="返回" runat="server" />
10 <asp:Button Text="开始" 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.cncms.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.cnblogs.com/skyivben/archive/2007/01/26/631233.html