java吧 关注:1,219,151贴子:12,670,937

【数独】世界最难数独90+毫秒解决。一个不错的算法

只看楼主收藏回复

研究了一整天,12个小时。终于写完了。没有参考任何人的代码。
研究了下数独人工解法,并且自己解了一道5级数独,然后写的代码。
经过测试,90+毫秒内解决世界最难数独,10.7级数独。
9-10级数独,50-70毫秒。
8-9级数独,30-50毫秒。
7-8级数独,20-30毫秒
7级以下数独,统统20毫秒内完杀。
可能你还不太理解我的算法效率。我百度到最好的算法,也要150毫秒才能解决10.7级数独。所以我可以很自豪的给你介绍下我的算法。
如果你对数独感兴趣,可以自行百度数独等级。
7级以上的数独,不是一般人在短时间(半小时内)做出来的。
2楼上源码


1楼2015-04-18 00:22回复
    好牛逼哦


    来自WindowsPhone客户端2楼2015-04-18 00:27
    收起回复
      说好的2楼呢


      来自WindowsPhone客户端3楼2015-04-18 00:27
      回复
        三楼没源码


        IP属地:福建来自Android客户端4楼2015-04-18 00:28
        回复
          绝对厉害呀


          来自Android客户端6楼2015-04-18 00:31
          回复


            IP属地:北京来自手机贴吧7楼2015-04-18 00:33
            回复
              核心思路。
              初始化:
              将数独初始化一个二维数组sudoArr,并且初始化一个节点二维数组nodeArr;
              节点Node最主要目的,是保存在(i,j)节点上的可能取值List<Integer> problist
              然后我们做基础解法(隐式唯一解和显式唯一解)得到一个唯一数组,当然如果数组难度很高,这时候(注意是初始化阶段)的基础解法是徒劳无功的,因为不可能有隐式唯一解。
              深度优先递归:
              1.做基础解。
              2.寻找合适的节点Node,这里仅根据Node的problist的size()判断,可能有点粗糙。
              3.遍历problist,将每个可能值遍历一遍,必定会得到解。
              跳出递归:当一个九宫格(or行列)存在1个节点node,但是这个节点node的problist是空的,那么就代表递归错误,此时开始回溯。
              其实很好理解,深度优先递归,就是人类思维的简单假设法。
              后记:此算法仅仅只能得出一个解,没办法得到一个数独的全部解。
              但是,严格数独的来说,都是唯一解。


              8楼2015-04-18 00:40
              收起回复
                牛逼


                IP属地:福建来自Android客户端9楼2015-04-18 00:57
                回复
                  终于研究出一个比百度上都好的算法了,艹。


                  10楼2015-04-18 00:59
                  收起回复
                    牛逼


                    IP属地:广东11楼2015-04-18 01:30
                    回复


                      IP属地:河南来自WindowsPhone客户端12楼2015-04-18 02:17
                      回复
                        楼主在行业里属于什么水平?想找个标准度量下自己


                        来自WindowsPhone客户端13楼2015-04-18 08:26
                        收起回复

                          不明觉厉


                          来自Android客户端14楼2015-04-18 08:31
                          回复
                            收藏了慢慢研究


                            IP属地:浙江来自Android客户端15楼2015-04-18 09:05
                            回复
                              厉害


                              IP属地:江苏来自WindowsPhone客户端16楼2015-04-18 09:07
                              回复