建网站需要编程吗,怎么推广游戏叫别人玩,一级域名和二级域名,wordpress ajax登陆一切罪恶的来源是昨晚睡前玩了一把数独#xff0c;找虐的选了个最难的模式#xff0c;做了一个多小时才做完#xff0c;然后就睡不着了..........程序员不能受这委屈#xff0c;今天咋样也得把这玩意儿破解了
破解思路#xff08;暴力破解加深度遍历#xff09;
把数独…一切罪恶的来源是昨晚睡前玩了一把数独找虐的选了个最难的模式做了一个多小时才做完然后就睡不着了..........程序员不能受这委屈今天咋样也得把这玩意儿破解了
破解思路暴力破解加深度遍历
把数独看做是一个二维数组并且这个数组已经填了一部分数字空格填数字0依次遍历这个数组找到第一个空格他所能填的数字为同一行同一列以及所在小九宫格均未出现的数字所能填的数字可能有多个依次进行尝试正确的那个数字肯定能走到最后错误的数字在后面一定会发生矛盾矛盾就是有一个空格1-9都不能填填完一个空格之后就形成了新的数独递归重复这个操作即可
代码实现
package mainimport (fmtos
)
func shuzu_print(shuzu [9][9]int) {fmt.Println(------------------------)for i : 0; i 9; i {fmt.Println(shuzu[i])}
}func main() {shuzu : [9][9]int{ // 初始化数独{2, 0, 0, 0, 4, 0, 0, 1, 0},{6, 1, 7, 0, 0, 3, 0, 0, 5},{0, 5, 0, 0, 0, 0, 0, 0, 3},{0, 0, 9, 0, 3, 6, 5, 7, 8},{0, 6, 5, 0, 8, 0, 0, 4, 2},{0, 0, 8, 4, 1, 5, 0, 6, 9},{0, 0, 0, 3, 0, 0, 0, 9, 0},{0, 9, 2, 0, 7, 0, 8, 3, 0},{8, 3, 0, 9, 2, 0, 0, 5, 7},}shuzu_print(shuzu)// 打印handle(shuzu)}
func handle(shuzu [9][9]int) {for i : 0; i 9; i {for j : 0; j 9; j {if i 8 j 8 { // 已经填完了这个exit 是为了打断所有尝试shuzu_print(shuzu)os.Exit(1)return}if shuzu[i][j] ! 0 {continue}set : make(map[int]struct{}) // map 实现set,存储同行同列所在小九宫格已经存在的数字for k : 0; k 9; k {if shuzu[i][k] ! 0 {set[shuzu[i][k]] struct{}{}}}for k : 0; k 9; k {if shuzu[k][j] ! 0 {set[shuzu[k][j]] struct{}{}}}i_3 : i / 3j_3 : j / 3for ii : i_3 * 3; ii (i_31)*3; ii {for jj : j_3 * 3; jj (j_31)*3; jj {if shuzu[ii][jj] ! 0 {set[shuzu[ii][jj]] struct{}{}}}}if len(set) 9 { // 如果同行同列所在小九宫格1-9均存在了那么发生矛盾此支线走不下去return}for kk : 1; kk 10; kk {if _, ok : set[kk]; !ok {shuzu[i][j] kkhandle(shuzu)// 同行同列所在小九宫格1-9不存在的数字均要进行尝试}}}}} 跑了一下没问题而且是秒出结果但是很悲剧下面这个例子就是我昨晚那个关卡的例子就不行了二十分钟都跑不完,调试了一下0行1列的位置可以填389正解是8但是拿3去尝试的时候一直到第二行填完才出现矛盾并且这个过程大概花了五六秒的时间也太暴力了吧 shuzu : [9][9]int{{1, 0, 4, 0, 0, 0, 0, 0, 0},{0, 0, 0, 0, 0, 5, 0, 0, 0},{0, 6, 0, 0, 8, 0, 0, 7, 3},{0, 0, 0, 8, 0, 1, 9, 0, 0},{6, 5, 0, 0, 0, 0, 0, 0, 0},{0, 0, 0, 3, 0, 0, 0, 0, 8},{0, 2, 0, 0, 3, 0, 0, 0, 7},{0, 0, 0, 0, 0, 7, 1, 3, 0},{4, 7, 0, 0, 0, 0, 8, 9, 0},} 思考和优化
人在做这个的时候会先把容易填的填完不会按照顺序说一定要先填哪一个尝试在这儿进行如下优化
不按顺序填遍历所有需要填的空格当某个空格只有唯一选项时直接填填了就是一个新的数独了如果没有唯一选项的空格时依次挑选唯二唯三唯四选项的空格进行尝试
代码实现
package mainimport (fmttime
)func shuzu_print(shuzu [9][9]int) {fmt.Println(------------------------)for i : 0; i 9; i {fmt.Println(shuzu[i])}
}var num int 0 // 记录一下函数执行的次数func main() {shuzu : [9][9]int{{0, 0, 0, 0, 0, 0, 0, 0, 0},{5, 9, 0, 8, 0, 0, 7, 0, 0},{0, 0, 0, 0, 2, 1, 8, 0, 0},{0, 3, 7, 0, 0, 0, 0, 0, 0},{0, 5, 0, 7, 9, 0, 0, 0, 0},{0, 0, 0, 0, 3, 0, 1, 8, 0},{0, 0, 5, 0, 0, 2, 0, 0, 0},{8, 1, 0, 0, 0, 0, 0, 4, 0},{0, 0, 6, 0, 8, 0, 9, 0, 3},}shuzu_print(shuzu)t1 : time.Now()fmt.Println(t1)result : handle2(shuzu)shuzu_print(result)fmt.Println(time.Now().Sub(t1)) // 记录一下花费的时间}type Left struct { // 定义一个结构体表示i行j列剩余可以填的数字i intj intlen intleft []int
}func check(shuzu [9][9]int) bool {// 检查数组有没有填完for i : 0; i 9; i {for j : 0; j 9; j {if shuzu[i][j] 0 {return false}}}return true}
// 这个里面还用了goto,loop 让函数有个返回
func handle2(shuzu [9][9]int) [9][9]int {num 1left_map : map[int]Left{}if check(shuzu) {println(hhhhhhhhhhhhhhhh)// 填完了真开心hhhhhshuzu_print(shuzu)fmt.Println(num) // 看一下该函数执行了多少次return shuzu}new_shuzu : shuzufor i : 0; i 9; i {for j : 0; j 9; j {if shuzu[i][j] ! 0 {continue}set : make(map[int]struct{}) // 同行同列同小组已经存在的数字for k : 0; k 9; k {if shuzu[i][k] ! 0 {set[shuzu[i][k]] struct{}{}}}for k : 0; k 9; k {if shuzu[k][j] ! 0 {set[shuzu[k][j]] struct{}{}}}i_3 : i / 3j_3 : j / 3for ii : i_3 * 3; ii (i_31)*3; ii {for jj : j_3 * 3; jj (j_31)*3; jj {if shuzu[ii][jj] ! 0 {set[shuzu[ii][jj]] struct{}{}}}}left_len : 9 - len(set)if left_len 0 {goto Loop // 出现矛盾的时候跳出执行}if left_len 1 { // 只剩一个可填直接处理for kk : 1; kk 10; kk {if _, ok : set[kk]; !ok {shuzu[i][j] kknew_shuzu handle2(shuzu)goto Loop// 直接跳出循环了}}} else {_, ok : left_map[left_len]if !ok {left_num : []int{}for kk : 1; kk 10; kk {if _, ok : set[kk]; !ok {left_num append(left_num, kk)}}left_map[left_len] Left{i, j, left_len, left_num} //对于每种剩余可填长度记录一个即可}}}}for k : 2; k 10; k { // 依次找剩余可填长度为2,3,4....,找到一个即可left, ok : left_map[k]if ok {for _, value : range left.left {shuzu[left.i][left.j] valuenew_shuzu handle2(shuzu)if check(new_shuzu) {goto Loop}}break}}
Loop:// fmt.Println(跳出循环)return new_shuzu
}运行结果函数执行3760次10ms运行完成基本满意终于不用我想破脑壳做一个小时了 问题及优化
代码写的很粗糙命名也是随手写的理解哈其实人在做数独的时候不仅可以看到每个空格可填的数字还可以看到可排除了根据所在小九宫格其他的可填和可排除的这样的话可以进一步减少函数执行的次数。这里面9*9 是用数组对于go来说数组作为函数的参数是值传递也就是说9*9 的数组复制了3760次如果用切片的话可以节省这个复制但是用切片的话如果试错了往回走的整个链路都要进行恢复这个想一想应该还是可以优化出来的各位大佬如果还有可以优化的点欢迎赐教
