用程序来解数独

数独（Sudoku，记忆中这个游戏也叫九宫格，可能是我记错了，应该叫数独比较准确）

数独百度百科：http://baike.baidu.cn/view/961.htm

九宫格百度百科：http://baike.baidu.cn/view/230179.htm#sub5038177

 

前两天看到 @万仓一黍 关于数独解法算法实践的一篇文章（http://www.cnblogs.com/grenet/archive/2013/06/19/3138654.html），突然想起去年的时候，因为微博上一篇关于某个外国学者花费3个月，研究出一道只有一种答案的数独题，然后自己一时热血涌上，花了3个钟写了个程序解了这道题。

原微博地址：http://weibo.com/2305049812/z0k9MciY7?type=repost

我的程序结果：http://weibo.com/1974539725/z0mBU0AtX?type=repost

这道数独题是这样的：

 

接下来说说我当时写程序时的想法是怎样的：

先抛开这道题，数独的规则很简单，就是要每一行、每一列、每一个九宫格中都含有1-9九个数字，且不重复。那就可以根据这一规则来制定解题的流程、逻辑。

用程序来解题的好处就是，我们有“循环”、“递归”这两个概念，而且计算机的计算速度远比人脑要快多了。

 

大概逻辑是：

1、先判断每一格空格可能填写的数字，取数量最少的那一格。

2、循环它可能的数字列，取第一个填入该格，再重复执行该逻辑（递归调用）。

3、若得到的数字列为空，则跳回上一格，取下一个数字填入，继续执行查询；若已跳回第一格，且已取完最后一个数字，则宣布该题无解；若已执行到最后一个，且得到数字列（理论上来将该数字列只有一个item），则宣布得到该题的解。

 

 

这里我使用Winform（C#）来做这个程序。

先设计好界面：

在后台用一个数组变量保存这（9x9）81个格子

private static int _x = 9, _y = 9;private TextBox[,] _tbs = new TextBox[_x, _y];

 

当点击“开始计算”按钮后，后台启动一个线程开始计算。

private bool Find(){    // 循环每一格，找出各自可能情况数    var count = 10;    int[] indexs = null;    IList<int> numbers = null;    for (var i = 0; i < _x; ++i)        for (var j = 0; j < _y; ++j)        {            int val;            if (string.IsNullOrEmpty(_tbs[i, j].Text.Trim()) || !int.TryParse(_tbs[i, j].Text.Trim(), out val))            {                var ns = GetNums(i, j);                if (ns.Count == 0)                    return false;                else if (ns.Count < count)                {                    count = ns.Count;                    indexs = new int[2] { i, j };                    numbers = ns;                }            }        }    // 选择最少可能情况的那一格    if (numbers == null)        return true;    else    {        var tb = _tbs[indexs[0], indexs[1]];        do        {            tb.Text = numbers[0].ToString();            if (Find())                return true;            else                numbers.RemoveAt(0);        }        while (numbers.Count > 0);        tb.Text = "";        return false;    }}// 获取这一格所有可能的情况private IList<int> GetNums(int x, int y){    // 获取该格所在九宫格    var cells = new List<TextBox>();    int xstart = x / 3 * 3,        ystart = y / 3 * 3;    for (int i = xstart, iend = xstart + 3; i < iend; ++i)        for (int j = ystart, yend = ystart + 3; j < yend; ++j)            cells.Add(_tbs[i, j]);    int val;    var nums = new List<int>();    for (var num = 1; num <= 9; ++num)    {        if (nums.Contains(num)) continue;        var isIn = false;        // 横行        for (var index = 0; index < _y; ++index)        {            if (index != y &&                !string.IsNullOrEmpty(_tbs[x, index].Text.Trim()) &&                int.TryParse(_tbs[x, index].Text.Trim(), out val) &&                val == num)            {                isIn = true;                break;            }        }        if (isIn) continue;        // 竖行        for (var index = 0; index < _x; ++index)        {            if (index != x &&                !string.IsNullOrEmpty(_tbs[index, y].Text.Trim()) &&                int.TryParse(_tbs[index, y].Text.Trim(), out val) &&                val == num)            {                isIn = true;                break;            }        }        if (isIn) continue;        // 九宫格        var tb = _tbs[x, y];        foreach (var c in cells)        {            if (c != tb &&                !string.IsNullOrEmpty(c.Text.Trim()) &&                int.TryParse(c.Text.Trim(), out val) &&                val == num)            {                isIn = true;                break;            }        }        if (isIn) continue;        // 可选数值        nums.Add(num);    }    return nums;}

 

两个大的方法已完成，接下来计算花费的时间。以这道题为例，最后得出结果为：

   

 

这个可能不是最优的逻辑算法，之前试过另一种方法，同样可以得出这个结果，但花费了70多秒，这个方法只花费了19秒多。

贴出这篇文章只是为了学习，希望各位前辈多多指教。

 

PS：貌似这道题的答案不止一种，之前做程序的时候至少得到两种答案，不过结果没保存下来。谁知道呢，就让其他人去研究吧 ...