数独解算器(ASP.NET 2.0)

王朝asp·作者佚名  2008-05-31
窄屏简体版  字體: |||超大  

数独游戏 在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="返回" 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.knowsky.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

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航