日历拼图求解-回溯

日历拼图

愚蠢的Lacy得到了老板的恩赏，拿回了一个由香港科技大学出品的日历拼图.

该拼图有10块，任何一个日期（包括月，日，星期）都可以由这10块拼图拼起来。

Lacy拼了一下午也没能解出来。

作为一个程序员，能暴力搜索的问题为什么要费脑子呢（不是）？

求解思路

思路很简单，就是回溯法进行暴力搜索就好啦！

首先定义矩阵pieces，用来保存可供选择的10块拼图。

因为每块拼图有最多8种摆放方式，这八种方式我们可以用旋转和翻转的方式得到，所有的摆放方式存入transformed_pieces。

拼图当前的放置情况我们用map存储，0表示该块不可放置，.表示该块为空，在最终结果中，1-X代表10块拼图放置的方式。

回溯的过程很简单，先找到map中第一个空的块，然后遍历可供选择的拼图，如果能在此处放置，就放置此块拼图，然后递归求解。递归之后我们移除这块拼图，并尝试下一块拼图，直到找到第一个解。

运行示例

以1月15日星期三为例：

锦上添花

花了十几分钟写了个WinForm程序帮助老年人更好的观察结果。

全部代码

详见Github Repo.