破解九宫格数独游戏

数独是一种比较费时费脑的游戏，一般难度的数独玩下来也得1个小时左右，本人是伪数独爱好者，碰到难点的数独需要花上若干个小时，于是偷懒写了一套破解程序，特拿出来分享，希望有人喜欢。

思路： 从第一个空格开始，计算出所有可能填充的数字，拿出第一个进行填充，将剩下的可能数字记录下来； 接着计算下一个空格所有可能的数字（在前边填充上的基础上），拿出第一个可能进行填充，将剩下的记录； 以此下去； 直到出现这样一个空格：所有的数字都没法填充（有冲突），就回到最后一次那个假设点，重新尝试其它的可能数字； 以此下去； 直到填充完所有空格。 实现代码

// C#
using System;
using System.Collections.Generic;
using System.Text;
/* =====================================
 * Author: 朱乙
 * Blog: http://blog.csdn.net/sq_zhuyi
 * Email: sqzhuyi@gmail.com
======================================== */
namespace SudokuResponder
{
    public class SudokuService
    {
        Number[][][][] pArr = null;//存储数独数字

        public SudokuService(string numStr)
        {
            string s = numStr.Replace(",", "");
            if (s.Length != 81)
            {
                throw new Exception("初始数独错误，必须是81个数字");
            }
            int[] numArr = new int[81];
            for (int i = 0; i < s.Length; i++)
            {
                numArr[i] = Convert.ToInt32(s[i].ToString());
            }
            pArr = GetArray(numArr);
        }
        public SudokuService(int[] numArr)
        {
            if (numArr.Length != 81)
            {
                throw new Exception("初始数独错误，必须是81个数字");
            }
            pArr = GetArray(numArr);
        }
        /// <summary>
        /// 获取结果
        /// </summary>
        /// <returns></returns>
        public string GetResult()
        {
            FillArray();

            StringBuilder sb = new StringBuilder();
            for (int m = 0; m < 3; m++)
            {
                for (int i = 0; i < 3; i++)
                {
                    for (int n = 0; n < 3; n++)
                    {
                        for (int j = 0; j < 3; j++)
                        {
                            sb.Append(pArr[m][n][i][j].Value);
                        }
                    }
                    sb.Append(",");
                }
            }
            return sb.ToString().TrimEnd(',');
        }
        /// <summary>
        /// 打印结果
        /// </summary>
        public void PrintResult()
        {
            for (int m = 0; m < 3; m++)
            {
                if (m == 0) Console.WriteLine("".PadLeft(25, '-'));
                for (int i = 0; i < 3; i++)
                {
                    for (int n = 0; n < 3; n++)
                    {
                        if (n == 0) Console.Write("| ");
                        for (int j = 0; j < 3; j++)
                        {
                            var pv = pArr[m][n][i][j];
                            if (pv.Default) Console.ForegroundColor = ConsoleColor.Red;
                            Console.Write("{0} ", pv.Value);
                            Console.ForegroundColor = ConsoleColor.White;
                        }
                        Console.Write("| ");
                    }
                    Console.WriteLine();
                }
                Console.WriteLine("".PadLeft(25, '-'));
            }
        }

        private Number[][][][] GetArray(int[] defVal)
        {
            Number[][][][] pArr = new Number[3][][][];
            for (int m = 0; m < 3; m++)
            {
                pArr[m] = new Number[3][][];
                for (int n = 0; n < 3; n++)
                {
                    pArr[m][n] = new Number[3][];
                    for (int i = 0; i < 3; i++)
                    {
                        pArr[m][n][i] = new Number[3];
                        for (int j = 0; j < 3; j++)
                        {
                            pArr[m][n][i][j] = new Number() { Value = 0, Default = false };
                        }
                    }
                }
            }

            int c = 0;
            for (int m = 0; m < 3; m++)
            {
                for (int i = 0; i < 3; i++)
                {
                    for (int n = 0; n < 3; n++)
                    {
                        for (int j = 0; j < 3; j++)
                        {
                            int val = defVal[c++];
                            pArr[m][n][i][j].Value = val;
                            if (val > 0)
                                pArr[m][n][i][j].Default = true;
                        }
                    }
                }
            }

            return pArr;
        }
        private void FillArray()
        {
            for (int m = 0; m < 3; m++)
            {
                for (int n = 0; n < 3; n++)
                {
                    for (int i = 0; i < 3; i++)
                    {
                        for (int j = 0; j < 3; j++)
                        {
                            if (pArr[m][n][i][j].Default == false)
                            {//空白格
                                var pv = GetNumber(new int[4] { m, n, i, j });

                                if (!pv.Ok)
                                {
                                    m = pv.Position[0];
                                    n = pv.Position[1];
                                    i = pv.Position[2];
                                    j = pv.Position[3];
                                    ClearAfter(pv.Position);

                                }
                                pArr[m][n][i][j].Value = pv.Value;
                            }
                        }
                    }//end small
                }
            }//end big
        }
        //清空该位置后边的空格
        private void ClearAfter(int[] pos)
        {
            int min = pos[0] * 1000 + pos[1] * 100 + pos[2] * 10 + pos[3];
            for (int m = 0; m < 3; m++)
            {
                for (int n = 0; n < 3; n++)
                {
                    for (int i = 0; i < 3; i++)
                    {
                        for (int j = 0; j < 3; j++)
                        {
                            if (m * 1000 + n * 100 + i * 10 + j > min)
                            {
                                if (pArr[m][n][i][j].Default == false)
                                {
                                    pArr[m][n][i][j].Value = 0;
                                }
                            }
                        }
                    }
                }
            }
        }
        
        //记录每个位置的可能数字
        private List<PosValues> posVals = new List<PosValues>();

        //获取当前位置的可能数字
        private PosValues GetNumber(int[] pos)
        {
            List<int> nums = new List<int>();
            for (int n = 1; n <= 9; n++)
            {
                nums.Add(n);
            }
            //3宫格内
            for (int i = 0; i < 3; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    int a = pArr[pos[0]][pos[1]][i][j].Value;
                    if (a > 0 && nums.Contains(a))
                    {
                        nums.Remove(a);
                    }
                }
            }
            //横向
            for (int n = 0; n < 3; n++)
            {
                for (int j = 0; j < 3; j++)
                {
                    int a = pArr[pos[0]][n][pos[2]][j].Value;
                    if (a > 0 && nums.Contains(a))
                    {
                        nums.Remove(a);
                    }
                }
            }
            //纵向
            for (int m = 0; m < 3; m++)
            {
                for (int i = 0; i < 3; i++)
                {
                    int a = pArr[m][pos[1]][i][pos[3]].Value;
                    if (a > 0 && nums.Contains(a))
                    {
                        nums.Remove(a);
                    }
                }
            }

            if (nums.Count == 0)
            {
                if (posVals.Count == 0)
                {
                    return new PosValues()
                    {
                        Value = 0
                    };
                }
                var pv = posVals[posVals.Count - 1];

                pv.Ok = false;
                pv.Value = pv.Values[0];
                pv.Values.Remove(pv.Value);
                if (pv.Values.Count == 0)
                {
                    posVals.Remove(pv);
                }
                return pv;
            }
            else
            {
                var pv = new PosValues();
                pv.Position = pos;
                pv.Value = nums[0];
                nums.Remove(pv.Value);
                pv.Values = nums;
                if (nums.Count > 0)
                {
                    posVals.Add(pv);
                }
                return pv;
            }
        }
    }
    public struct Number
    {
        public int Value;
        public bool Default;
    }
    public class PosValues
    {
        public int[] Position;

        public List<int> Values;

        public bool Ok = true;

        public int Value;
    }
}

调用代码

// C#
using System;
using System.Collections.Generic;

namespace SudokuResponder
{
    class Program
    {
        static void Main(string[] args)
        {
            string s = "000000007,008000400,003801600,804306201,000000000,105407908,007603800,006000100,400000005";

            SudokuService service = new SudokuService(s);
            DateTime start = DateTime.Now;
            string result = service.GetResult();
            TimeSpan span = DateTime.Now - start;
            service.PrintResult();

            Console.WriteLine("计算结束，用时 {0} 毫秒", span.Milliseconds);
            Console.WriteLine("press enter to exit");
            Console.ReadLine();
        }
    }
}

运行截图 破解九宫格运行结果

作者：朱会震