当前位置:首页 > 搜索 > 深度优先搜索 > 正文
SSOJ2230数独游戏填法种数
327+

题目大意:给你一个填了部分数字的数独,请问有多少种方案将他填写完整?

题目描述

“我陪你玩这个数独游戏已经整整三天了,你到底什么时候给我上古神器?”修罗王忍不住问。 “这人生啊,急也好,慢也好,目标总能达到,何不让自己静下心来,慢慢欣赏一下沿途的风景?”上古神器的守护者悠悠道。 修罗王悻悻道:“如果玩这个游戏没有赌注的话,我还真信你的话了,就三天工夫,你都把我的魔法石赢去一大半了。” 已知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组数据按照原顺序就是最快的?)

程序实现

更多
SSOJ2230数独游戏填法种数:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter