前段时间看到了sudoku的游戏,被这个游戏所吸引,在www.websudoku.com 上玩了好久.随之也对之产生了兴趣,特写了一个sudoku的solver.

  先来介绍一下sudoku,典型的9*9格也称之为9宫格,近年来风靡世界,一个从满智慧的游戏.如下面一个sudoku puzzle

y

^

|

|

|

0 ----------------------------------------------------------------->x

游戏规则:

1:填入1~9的数字(当然这只是9宫格,如果是16*16的,那就是填入1~16的数字)

2:每行不能有重复的数字

3:每列不能有重复的数据

4:每3*3的小方块内不能有重复的数字

这是一个简单的puzzle,预先已填的数字很多,当然玩这个游戏也有技巧,应当先选取已填入数字多的行或列或3*3格开始游戏,当有小格有几个数字都可以填入时,那就要试了.

如上题可以选取x=1 或 x=9 的列开始,解为:

254768931197253684683149752716935428825476193439821567348597216571682349962314875
2 5 4 7 6 8 9 3 1
1 9 7 2 5 3 6 8 4
6 8 3 1 4 9 7 5 2
7 1 6 9 3 5 4 2 8
8 2 5 4 7 6 1 9 3
4 3 9 8 2 1 5 6 7
3 4 8 5 9 7 2 1 6
5 7 1 6 8 2 3 4 9
9 6 2 3 1 4 8 7 5

接下来介绍一下我的java解题方案

1:先loading一个sudoku

2:计算每个空格的优先权,可填入的数字.将sudoku放入stack中

3:从stack中取出一个sudoku,根据优先权和可填入的数字,将一个sudoku分成一个或多个,判断每一个是否已经完成,检查正确性,如还未完成,则检查是否丢弃此sudoku,如果没有完成且还要继续填充,则放入stack

4:接着做3直到完成

基本方案就是这样

网上比较成熟的方案如使用dancing link algorithem,我没有仔细看,大致也就是这样,遍历算法.

csdn上有人用c写的dancing link解决方法,世界上最难的puzzle上,我这个xp2500+的cpu下,需要3.5秒左右

我没有用dancing link算法的java实现来做,所以也就没法对比.

源代码见:

 http://meichua.googlecode.com/files/sudoku.rar