|
 |
栏目导栏 |
|
| |
|
|
|
|
|
资料搜索 |
|
| |
|
|
|
|
|
热门文章 |
|
| |
|
|
|
|
|
最新文章 |
|
| |
|
|
|
| |
| |
|
|
|
|
数独游戏 在9x9的方格内进行， 分为3x3的小方格，被称为“区”。 PLPLinux联盟
数独游戏首先从已经填入数字的格子开始。 PLPLinux联盟
数独游戏的目的是根据下列规则，用1至9之间的数字填满空格： PLPLinux联盟
每个数字在每一行、每一列和每一区只能出现一次。 PLPLinux联盟
我在 Linux 服务器(请参见“在 Linux 下运行 ASP.NET 2.0”)上用 ASP.NET 2.0 实现了一个数独解算器。 PLPLinux联盟
http://www.sudoku.name 网站上也有一个用户界面相当不错的“数独解算器” ，但是其算法太差了，运算速度比我的算法慢多了。以其网站上的“#5328”谜题(也是我的数独解算器的例题)为例，它需要大约四个小时才能给出答案，而我的解算器不到一秒钟就可以给出答案。从它的运算过程来算，估计是逐个空格进行解算。而我的算法是先找出能填入数字个数最少的空格进行解算。算法这个微小的改进，就极大地提高了计算效率。好了，废话少说，下面就是源程序： PLPLinux联盟
PLPLinux联盟
1. sudoku.aspx: PLPLinux联盟
1<%@ Page Language="C#" inherits="Skyiv.Ben.Web.SudokuPage" %> PLPLinux联盟
2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" PLPLinux联盟
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> PLPLinux联盟
3<html xmlns="http://www.w3.org/1999/xhtml" > PLPLinux联盟
4<head runat="server"> PLPLinux联盟
5 <title>银河 - 数独</title> PLPLinux联盟
6</head> PLPLinux联盟
7<body> PLPLinux联盟
8 <form id="form1" runat="server"> PLPLinux联盟
9 <asp:Button Text="返回" OnClick="BtnUriHome_Click" runat="server" /> PLPLinux联盟
10 <asp:Button Text="开始" OnClick="BtnSubmit_Click" runat="server" /> PLPLinux联盟
11 <hr /> PLPLinux联盟
12 <div> PLPLinux联盟
13 <a href="http://www.sudoku.name/index-cn.php" target="_blank">数独游戏</a> PLPLinux联盟
14 在9x9的方格内进行， 分为3x3的小方格，被称为“区”。<br /> PLPLinux联盟
15 数独游戏首先从已经填入数字的格子开始。<br /> PLPLinux联盟
16 数独游戏的目的是根据下列规则，用1至9之间的数字填满空格：<br /> PLPLinux联盟
17 http://www.knowsky.com 每个数字在每一行、每一列和每一区只能出现一次。<br /> PLPLinux联盟
18 </div> PLPLinux联盟
19 <div> PLPLinux联盟
20 <asp:TextBox Runat="Server" Id="tbxInput" MaxLength="512" Wrap="False" PLPLinux联盟
21 TextMode="MultiLine" Columns="15" Rows="14" /> PLPLinux联盟
22 <asp:TextBox Runat="Server" Id="tbxOutput" ReadOnly="True" Wrap="False" PLPLinux联盟
23 TextMode="MultiLine" Columns="15" Rows="14" /> PLPLinux联盟
24 </div> PLPLinux联盟
25 </form> PLPLinux联盟
26</body> PLPLinux联盟
27</html> PLPLinux联盟
28 PLPLinux联盟
2. sudoku.aspx.cs: PLPLinux联盟
1using System; PLPLinux联盟
2using System.IO; PLPLinux联盟
3using System.Web.UI; PLPLinux联盟
4using System.Web.UI.WebControls; PLPLinux联盟
5using Skyiv.Ben.Etc; PLPLinux联盟
6 PLPLinux联盟
7namespace Skyiv.Ben.Web PLPLinux联盟
8{ PLPLinux联盟
9 public class SudokuPage : Page PLPLinux联盟
10 { PLPLinux联盟
11 protected TextBox tbxInput; PLPLinux联盟
12 protected TextBox tbxOutput; PLPLinux联盟
13 PLPLinux联盟
14 public void Page_Load(object sender, EventArgs e) PLPLinux联盟
15 { PLPLinux联盟
16 if (IsPostBack) return; PLPLinux联盟
17 tbxInput.Text = "+---+---+---+\n|2..|||\n|8..|1..|.2.|\n" PLPLinux联盟
18 + "|..5|.7.|.3.|\n+---+---+---+\n|.7.|.3.|1..|\n|.9.|.4.|.8.|\n" PLPLinux联盟
19 + "|..4||.7.|\n+---+---+---+\n|.3.|.9.|6..|\n|.8.|..5|..3|\n" PLPLinux联盟
20 + "|||..5|\n+---+---+---+"; PLPLinux联盟
21 } PLPLinux联盟
22 PLPLinux联盟
23 public void BtnUriHome_Click(object sender, EventArgs e) PLPLinux联盟
24 { PLPLinux联盟
25 Response.Redirect(Pub.UriHome); PLPLinux联盟
26 } PLPLinux联盟
27 PLPLinux联盟
28 public void BtnSubmit_Click(object sender, EventArgs e) PLPLinux联盟
29 { PLPLinux联盟
30 try PLPLinux联盟
31 { PLPLinux联盟
32 Sudoku sudoku = new Sudoku(new StringReader(tbxInput.Text)); PLPLinux联盟
33 StringWriter writer = new StringWriter(); PLPLinux联盟
34 sudoku.Out(writer); PLPLinux联盟
35 tbxOutput.Text = writer.ToString(); PLPLinux联盟
36 } PLPLinux联盟
37 catch (Exception ex) PLPLinux联盟
38 { PLPLinux联盟
39 tbxOutput.Text = "Error: " + ex.Message; PLPLinux联盟
40 } PLPLinux联盟
41 } PLPLinux联盟
42 } PLPLinux联盟
43} PLPLinux联盟
44 PLPLinux联盟
PLPLinux联盟
. sudoku.cs: PLPLinux联盟
1using System; PLPLinux联盟
2using System.IO; PLPLinux联盟
3using System.Collections.Generic; PLPLinux联盟
4 PLPLinux联盟
5namespace Skyiv.Ben.Etc PLPLinux联盟
6{ PLPLinux联盟
7 sealed class Sudoku PLPLinux联盟
8 { PLPLinux联盟
9 byte[,] input, output; PLPLinux联盟
10 int steps = 0; PLPLinux联盟
11 PLPLinux联盟
12 public Sudoku(TextReader reader) PLPLinux联盟
13 { PLPLinux联盟
14 input = new byte[9, 9]; PLPLinux联盟
15 for (int y = 0; y < 9; ) PLPLinux联盟
16 { PLPLinux联盟
17 string s = reader.ReadLine(); PLPLinux联盟
18 if (s == null) break; PLPLinux联盟
19 s = s.Replace('.', '0'); PLPLinux联盟
20 int x = 0; PLPLinux联盟
21 for (int i = 0; i < s.Length; i++) PLPLinux联盟
22 if (Char.IsDigit(s, i) && x < 9) input[x++, y] = (byte)(s[i] - '0'); PLPLinux联盟
23 if (x != 0) y++; PLPLinux联盟
24 } PLPLinux联盟
25 } PLPLinux联盟
26 PLPLinux联盟
27 public void Out(TextWriter writer) PLPLinux联盟
28 { PLPLinux联盟
29 Compute(input); PLPLinux联盟
30 Out(writer, output); PLPLinux联盟
31 } PLPLinux联盟
32 PLPLinux联盟
33 void Out(TextWriter writer, byte[,] output) PLPLinux联盟
34 { PLPLinux联盟
35 for (int y = 0; y <= output.GetLength(1); y++) PLPLinux联盟
36 { PLPLinux联盟
37 if (y % 3 == 0) writer.WriteLine("+---+---+---+"); PLPLinux联盟
38 if (y >= output.GetLength(1)) break; PLPLinux联盟
39 for (int x = 0; x <= output.GetLength(0); x++) PLPLinux联盟
40 { PLPLinux联盟
41 if (x % 3 == 0) writer.Write('|'); PLPLinux联盟
42 if (x >= output.GetLength(0)) break; PLPLinux联盟
43 writer.Write((output[x, y] == 0) ? '.' : (char)(output[x, y] + '0')); PLPLinux联盟
44 } PLPLinux联盟
45 writer.WriteLine(); PLPLinux联盟
46 } PLPLinux联盟
47 } PLPLinux联盟
48 PLPLinux联盟
49 bool Compute(byte[,] input) PLPLinux联盟
50 { PLPLinux联盟
51 List<byte[,]> list = StepIt(input); PLPLinux联盟
52 if (list == null) return true; PLPLinux联盟
53 foreach (byte[,] temp in list) if (Compute(temp)) return true; PLPLinux联盟
54 return false; PLPLinux联盟
55 } PLPLinux联盟
56 PLPLinux联盟
57 // return null for finish PLPLinux联盟
58 List<byte[,]> StepIt(byte[,] input) PLPLinux联盟
59 { PLPLinux联盟
60 if (steps++ > 100000) throw new Exception("太复杂了"); PLPLinux联盟
61 output = input; PLPLinux联盟
62 int theX = -1, theY = -1; PLPLinux联盟
63 byte[] theDigits = null; PLPLinux联盟
64 for (int y = 0; y < input.GetLength(1); y++) PLPLinux联盟
65 { PLPLinux联盟
66 for (int x = 0; x < input.GetLength(0); x++) PLPLinux联盟
67 { PLPLinux联盟
68 if (input[x, y] != 0) continue; PLPLinux联盟
69 byte[] digits = GetDigits(input, x, y); PLPLinux联盟
70 if (digits.Length == 0) return new List<byte[,]>(); PLPLinux联盟
71 if (theDigits != null && theDigits.Length <= digits.Length) continue; PLPLinux联盟
72 theX = x; PLPLinux联盟
73 theY = y; PLPLinux联盟
74 theDigits = digits; PLPLinux联盟
75 } PLPLinux联盟
76 } PLPLinux联盟
77 if (theDigits == null) return null; PLPLinux联盟
78 List<byte[,]> result = new List<byte[,]>(); PLPLinux联盟
79 foreach (byte digit in theDigits) PLPLinux联盟
80 { PLPLinux联盟
81 byte[,] temp = (byte[,])input.Clone(); PLPLinux联盟
82 temp[theX, theY] = digit; PLPLinux联盟
83 result.Add(temp); PLPLinux联盟
84 } PLPLinux联盟
85 return result; PLPLinux联盟
86 } PLPLinux联盟
87 PLPLinux联盟
88 byte[] GetDigits(byte[,] input, int x, int y) PLPLinux联盟
89 { PLPLinux联盟
90 bool[] mask = new bool[10]; PLPLinux联盟
91 for (int i = 0; i < 9; i++) PLPLinux联盟
92 { PLPLinux联盟
93 mask[input[x, i]] = true; PLPLinux联盟
94 mask[input[i, y]] = true; PLPLinux联盟
95 } PLPLinux联盟
96 for (int i = x / 3 * 3; i < x / 3 * 3 + 3; i++) PLPLinux联盟
97 for (int j = y / 3 * 3; j < y / 3 * 3 + 3; j++) PLPLinux联盟
98 mask[input[i, j]] = true; PLPLinux联盟
99 List<byte> list = new List<byte>(); PLPLinux联盟
100 for (int i = 1; i < mask.Length; i++) if (!mask[i]) list.Add((byte)i); PLPLinux联盟
101 return list.ToArray(); PLPLinux联盟
102 } PLPLinux联盟
103 } PLPLinux联盟
104} PLPLinux联盟
105 PLPLinux联盟
以上代码都很简单，也不需要再另外解说了。 PLPLinux联盟
Linux联盟收集整理 ,转贴请标明原始链接,如有任何疑问欢迎来本站Linux论坛讨论 |
|
|
|
|
|
