数独游戏制作过程记录
我打算自己做一个数独游戏,主要分为两步:
- 生成一个数独
- 验证玩家填入的数字是否正确
生成一个数独可以有很省事的办法,就是直接从数独库中随机选一个(甚至可以直接把空白都给你挖好)。也可以用暴力方法(回溯法),一行一行去填,进行不下去就回溯到上一步。
生成数独最高效的算法是:舞蹈链,实际上舞蹈链是一种数据结构,是为了X 算法而产生的,而 X 算法是用来解决一类问题:精确覆盖问题
插个题外话,我朋友说,东野圭吾的小说《嫌疑犯 X 的献身》,的凶手就在研究这个问题,有兴趣可以顺带看看,这小说挺有名的。
精确覆盖问题是一个 NP 完全问题,NP 问题的概念我差不多忘光了,得重新看看