数独算法——囧记

自以为的骄傲

我比较喜欢数独,也偶尔会玩一下,突然,有一天就萌生一个想法,写一个数独算法,
于是网上一搜,发现好多算法,有些看着,好像很简陋,有些看着,好吧,看不懂,
不如自己摸索一个。我花了一点时间,开始思考如何解出一个数独。
用程序模拟自己平时解数独的习惯,然后暴力破解,最后,我只能想到这个方法。
于是,我在纸上写下了几个解数独的步骤,总结分为三步,只要完成这三步,相信可以解出大部分不是骨灰级的数独。
————————————分割线———————————-
数独是共有9*9共81格的填数字游戏,行:填入1-9无重复,列:填入1-9无重复,宫(分为九个宫,一宫九格):填入1-9无重复
这是数独的基本规则,
我的解法:我的数独算法博客链接


粉碎的小骄傲

今天,看了两位大神的博客,第一篇数独算法博客比我的妙多了,这是我的看法,首先,这篇博客让我知道了一个知识,
看到的时候,我只能感慨自己的无知

1
List<Integer>[][] dataLeft = new ArrayList[9][9];

就是上面这一句代码,让我突然间醒悟,原来数组还可以这样子用,或者说,之前int[9][9]局限了我的思维,
我一直以为二维数组,只能填入数字,直到这句代码的出现,才知道,原来二维数组还可以这样子用。
作者解数独的思维其实很简单,他创建了一个二维数组(A),每个坐标存储的是一个list
当然这个二维数组对应了另一个二维数组(数独数组:B),作者初始化A数组的时候,
为每个坐标的list添加了数字1-9,即每个数独坐标可填入的所有数字。
然后,作者从第一个坐标位开始判断,如果数独有值,则清除A中该坐标的list,并且清除该坐标行、列、宫所有list的这个值,
1、最后判断A数组中所有list的长度,如果为1,表示找到一个正解,
2、而长度不是1的,则判断行、列、宫内是否只出现了一次,如果是,获得一个正解
3、最后判断单个宫内(可填值list长度不为1的),某个数字如果只在某一行(或者某一列)出现,那么可以排除另外两个宫,
该行(或该列),无法填入该值
A作者数独算法博客链接


另外一位大神则是回溯法解数独,简单点说,就是从第一个需要解值的位置开始,随意填入一个可填入的数字,
然后下一个位置也是如此,一直填下去,如果出现错误,则回溯,如果没有,一直下去,直到解出数独。
当然,核心还是对于行列宫的判断
B作者数独算法博客链接


内心独白

这两个算法都让我深深收到打击,不要说这么悲伤的事实,我还是有很大进步空间的。
然后,
你奇怪我为什么A大神写那么多,B大神写那么少,虽然算法都比我厉害,
但是我个人还是觉得回溯法厉害一点,暴力的美学,深度优先的优雅,你值得拥有。


最后

回溯算法的基本思想是:
从一条路往前走,能进则进,不能进则退回来,换一条路再试,也叫试探法,
我决定深度研究一下这个算法。


寄语

有时候我们执着于自己的骄傲,却不知道,这恰恰局限了未来