SSOJ2230数独游戏填法种数
4640+
作者：crxis 发布：2017-07-30 分类：深度优先搜索
题目大意：给你一个填了部分数字的数独，请问有多少种方案将他填写完整？
题目描述
“我陪你玩这个数独游戏已经整整三天了，你到底什么时候给我上古神器？”修罗王忍不住问。 “这人生啊，急也好，慢也好，目标总能达到，何不让自己静下心来，慢慢欣赏一下沿途的风景？”上古神器的守护者悠悠道。 修罗王悻悻道：“如果玩这个游戏没有赌注的话，我还真信你的话了，就三天工夫，你都把我的魔法石赢去一大半了。” 已知9*9的方阵，有些格子填有1~9的数字，其他格子待填（用0表示）。你的任务是，计算共有多少种填法，使得这个方阵每一行、每一列以及每个小九宫格(共九个这样的格子)都用到1,2,3,4,5,6,7,8,9。
输入
9行，每行9个数，数字之间有一个空格。
输出
输出一个整数，即填法的种数。
样例输入
【输入样例1】
2 3 4 8 6 5 7 9 0
8 6 5 1 7 9 2 0 4
1 7 9 4 3 2 0 5 8
6 1 2 5 8 4 0 7 9
7 4 8 9 2 3 0 6 5
9 5 3 6 1 0 4 8 2
3 9 7 2 0 1 8 4 6
5 8 1 0 4 6 9 2 3
4 2 0 3 9 8 5 1 7
【输入样例2】
0 6 0 1 0 4 0 6 0
0 0 8 3 0 5 6 0 0
2 0 0 0 0 0 0 0 1
8 0 0 4 0 7 0 0 6
0 0 6 0 0 0 3 0 0
7 0 0 9 0 1 0 0 4
5 0 0 0 0 0 0 0 2
0 0 7 2 0 6 9 0 0
0 4 0 5 0 8 0 7 0
样例输出
【输出样例1】
1
【输出样例2】
0
解题思路
一个一个格子填，直到81个格子都填完，填完后累加方案数。搜索前，可以先判断是否可填，即读入数据是边读入边判断是否合法，用x数组记录各行1-9是否用过，y数组记录列，xy数组记录小九宫格，小九宫格从上到下、从左到右依次编号为00，01，02，10，11，12，20，21，22，恰好可以有坐标通过除法取余等直接算出来。
小技巧：从0开始编号，0-80个格子，除以9是行标号，模9是列编号；行编号除以3是九宫格行编号，除以3再模3是九宫格列编号。
补充：此题如果用启发式搜索，感觉会超时，除非你的估价非常准确，且可以预先处理好。（第10组数据按照原顺序就是最快的？）
程序实现
