设为首页 - 加入收藏 焦点技术网
热搜:java
当前位置:首页 >

【开源】完美破解九宫格(数独)游戏

2012-07-05 09:49:00.0 C#.NET 技术 九宫格 破解 数独 算法  
导读:本文sq_zhuyi给大家介绍 【开源】完美破解九宫格(数独)游戏。数独是一种比较费时费脑的游戏,一般难度的数独玩下来也得1个小时左右,本人是伪数独爱好者,碰到难点的数独需要花上若干个小时。。。

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


思路:

1、从第一个空格开始,计算出所有可能填充的数字,拿出第一个进行填充,将剩下的可能数字记录下来;

2、接着计算下一个空格所有可能的数字(在前边填充上的基础上),拿出第一个可能进行填充,将剩下的记录;

3、以此下去;

4、直到出现这样一个空格:所有的数字都没法填充(有冲突),就回到最后一次那个假设点,重新尝试其它的可能数字;

5、以此下去;

6、直到填充完所有空格。


实现代码:

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);        }        ///         /// 获取结果        ///         ///         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(',');        }        ///         /// 打印结果        ///         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 posVals = new List();        //获取当前位置的可能数字        private PosValues GetNumber(int[] pos)        {            List nums = new List();            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 Values;        public bool Ok = true;        public int Value;    }}

调用代码:

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();        }    }}

运行截图:



下载地址:http://download.csdn.net/detail/sq_zhuyi/4411715



(编辑: sq_zhuyi)

网友评论
相关文章