简单点

最近又开始对数独感兴趣了，大学时期解数独的算法已经印象模糊，平常工作用go多，于是乎，用go写个解数独的程序被提上了日程。

在写代码的过程中，我一直在思考，如果我是一个正常玩家，应该怎样去解数独，我想我应该是观察棋盘上的空位，看看有哪些位置是立即可以确定填某个数字，或者只有2-3种填法，通过记录填过的数字，可以很快的找出答案。

循着这个思路，我写了第一版代码，大致思路就是遍历整个棋盘，找出所有位置可填写的数字，用1除以可填数字的数量作为置信度，选取置信度最高的一个格子填写对应的数字，然后继续计算置信度，递归寻解。

乍看之下这个思路似乎没什么毛病，但实际一运行，不是陷入死循环，就是遍历了上千万次都找不出解，问题到底出在了哪里呢？

我开始到网络上寻找思路，看到了这样一句话：

剪枝的判断条件很多时候都是有代价的，随着剪枝条件复杂性的增加，带来的开销也会增加，甚至可能出现剪枝了还不如不剪的情况发生。

突然就明白了，我的思路中有两个问题：

  1. 我用人的思维让机器去解数独，其实忽略了机器也不具备人的某些思考能力，我用了看似高明的剪枝，但这个剪枝却需要扫描整个棋盘，至少是O(n^3)的复杂度。
  2. 这种解题逻辑看似简单其实背后的结构非常复杂，或许这种思路能够正确解出，但可能因为一些小bug导致陷入了死循环。

想了想，不如尝试下暴力求值。说干就干，新的解题思路也很简单，既然是让机器解题，就应该用机器的思维，从棋盘左上角依次到右下角暴力遍历即可，当然剪枝是少不了的，但剪枝的策略尤为重要，还是用空间换时间的策略，缓存每行、每列、每个大格是否能填某个数字，在遍历求解过程中快速判断，当这行、这列、这个大格都可以填某个数字时，果断填上，进入下一层循环。代码如下：

package main

import (
	"fmt"
	"strings"
)

func main() {
	for i, input := range []string{
		"000007020 712030690 080600050 200000100 050000060 008000009 040002080 063080274 020900000",
		"607500020 020009305 000630000 400000010 076000450 080000002 000098000 804100090 060005701",
		"802096000 005018030 106700024 078902105 000105603 001000098 984031700 250049080 600000000",
		"503000070 010309800 000040000 001000009 000006000 090208300 007402080 020060000 000010400",
	} {
		fmt.Printf("=== case %d ===\n", i+1)
		data, ok := solve(input)
		if !ok {
			panic("impossible")
		}
		for i := 0; i < 9; i++ {
			for j := 0; j < 9; j++ {
				fmt.Print(data[i][j])
			}
			fmt.Println()
		}
		fmt.Println()
	}
}

func solve(input string) ([9][9]int, bool) {
	lines := strings.Split(input, " ")
	var data [9][9]int
	var xUsed [9][10]bool
	var yUsed [9][10]bool
	var zUsed [9][10]bool
	for i, line := range lines {
		for j, char := range line {
			data[i][j] = int(char - '0')
			if data[i][j] != 0 {
				xUsed[i][data[i][j]] = true
				yUsed[j][data[i][j]] = true
				zUsed[getZ(i, j)][data[i][j]] = true
			}
		}
	}
	return data, loop(&xUsed, &yUsed, &zUsed, &data, 0, 0)
}

func loop(xUsed, yUsed, zUsed *[9][10]bool, data *[9][9]int, i, j int) bool {
	loopNext := func() bool {
		if i == 8 && j == 8 {
			return true
		}
		if j < 8 {
			return loop(xUsed, yUsed, zUsed, data, i, j+1)
		} else {
			return loop(xUsed, yUsed, zUsed, data, i+1, 0)
		}
	}

	if data[i][j] > 0 {
		return loopNext()
	}

	k := getZ(i, j)
	for value := 1; value <= 9; value++ {
		if xUsed[i][value] || yUsed[j][value] || zUsed[k][value] {
			continue
		}
		data[i][j] = value
		xUsed[i][value] = true
		yUsed[j][value] = true
		zUsed[k][value] = true
		if ok := loopNext(); ok {
			return ok
		}
		data[i][j] = 0
		xUsed[i][value] = false
		yUsed[j][value] = false
		zUsed[k][value] = false
	}

	return false
}

func getZ(i, j int) int {
	return (i/3)*3 + j/3
}

不到100行的代码，几乎瞬间解出，为了避免偶然，我从网络上找了2个最高难度的数独加入测试case中，也是秒出，我又看了眼第一版的代码，太辣眼，不敢放出来了。

有时候，简单点，反而能将复杂的问题简单化，想得太多，就容易陷入死循环。生活中亦然，简单的生活方式能得到莫大的放松，顾虑太多，将会寸步难行。

 • 
简单点