自从出国来读书就更加无聊了，所以开始刷题了。十分感谢这些题，让我从完全不知道DFS，到逐渐理解DFS的内涵，再到这题的优化。
题目
- 题目关于一个大的正方形。
- 大的正方形由n*n个小的正方形组成。
- 每个正方向被分成了4块三角形，三角形上有各自的数字。
- 问能否通过排列这n*n个小正方形，使得所有三角形上的数字和其正对着的三角形相同。
输入
第1行，每行的小正方形数。
接下来的n行中，4个数分别是正方形内部“上，右，下，左”的三角形的值，
0 <= n <= 5, n 为0时表示输入结束了。
2
5 9 1 4
4 4 5 6
6 8 5 4
0 4 4 3
2
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4
0
输出
Game 1: Possible
Game 2: Impossible
对于每个游戏先输出 “Game”，再输出空格，再输出第几个游戏，再输出”:”,再输出空格，再对应输出”Possible”或者”Impossible”。
每个游戏之间需要有一个空行。
分析与第一次尝试
首先题目中没有说到正方形可以旋转，这降低了很多难度。
- 将图中的正方形逻辑是分成每个正方形自身，以及N个槽位。
- 对于每一个小正方形构成的大正方形虽然是一个二维的结构，但是因为二维数组去实现iterate和backtrack一方面容易越界，一方面在代码里需要多一层循环会大大降低可读性，而且难以去构思如何实现。所以把n*n(后文称N)个小正方形存到一位数组里，再用
%操作去处理会方便很多。 （使用一位数组存储小正方形（实际上是二维数组，因为每个小正方形还有4个三角形值需要存储）） - 要探寻可能性，所以要得到所有的小正方形的排布情况（即N个数的全排列），会得到
N!个排列。（找到全排列） - 每个排列中的数 - 1为小正方形的编号，再对每个排列按照排列顺序将对应小正方放入第 1-N个槽中。（通过每个排列建立小正方形和位置的映射）
- 对每个排列的情况进行检验，检验每个正方形的上下左右的三角形是否和对应的三角形等值，如果出现全等，之后的便不再检验（可以通过Exception实现，也可以通过检测一些简单的
boolean flag来判断）。
虽然我轻松地用DFS把全排列的方法给写了出来，但是结果却很现实，要么是时间超要么是内存超（绝大多数时候是时间超）。而且，我还并不知道是超了，以至于我根本就不知道该如何改进。
优化
除了改用原生数组实现容器操作，很快我就发现了一些可以优化的空间。
-
不需要比较上下左右，对于已经给出的特定排列左下开始，每个小正方形只需要比较上和右。
-
不需要把所有的排列都存起来，在已经全排列模块已经找到一个新的排列的情况下，可以直接检测。这样有两个好处：
-
减少了排列的存储空间
-
如果成功，可以直接进行下一个游戏的检测，省去了继续计算全排列的时间。
-
-
在录入具体三角形的迭代中，可以计算不正方形见一共存在的等值的三角形的对字数，当这个数小于
2*n对时，则一定不能完成游戏。 （在第一版优化中实现了该功能，因为“不同正方形”间的等值三角形比较难实现，代码又重构了，于是在后续的优化中就没有针对这个比较specific的情况写处理）
然而还是超，超得莫名其妙，而且什么信息也不给。我并不知道我是超了一点，还是超了几个量级，于是我开始苦恼了。
继续优化
我开始在网络上寻找一些点拨，随便浏览一两篇文章。看到压缩与分类，我像是突然间醒悟过来一样，其实这并不是“全排列”，而且绝大多数时候总是用全排列去处理问题是一种图方便的方式。因为，分类是在排列问题中总是可以做的一个步骤。
如果有小正方形一样怎么办？
当存在数目不等的一样的小正方形的时候，这个问题就从1-N的排列变成了a个1，b个2，.., x个N的排列，如果把他当作全排列去对待，那必然会在结果在出现的冗余的操作。
重构
把原本的正方形容器拆分成小正方形类型容器和小正方形类型数量容器。全排列模块也相应的通过前面两个参数来控制迭代，从原本的 (1-N) -> (2-N)-> ... -> N的单个参数控制的DFS变成先同类型不同数量DFS再不同类型DFS的二维迭代方式。
然而，时间还是超了。
永无止境的优化
为什么还是超了？
因为嵌套的循环太多! 这是这直接原因，真正影响效率的从来都不是什么细枝末节的检查检查2个方向还是检查4个方向，整个程序最深的循环嵌套，才是需要被优化的地方。
要么改变基础算法把嵌套层次减少，要么让不合规的操作尽快地continue或者break。
然后再反思一下之前的程序设计：
-
循环最多的代码块很显然在排列的迭代
-
如果觉得通过降低基础的搜索算法来减少复杂度是困难的，那就应该尽快地continue或者break。（本质就是，检验操作应该在越浅层越好）
-
之前的检验操作都是在一次排列完成后再操作的，我们能把他尽可能的提到浅层吗？
不需要，因为可以一边搜索排列的结果，一边计算当下排列的元素的合法性。只需要，把原先的比较
右，上改成比较左，下就行了，每次比较的都是已经深搜出来的元素。这样，在发现部分排列不合适的时候，就可以直接进入下一次排列的搜索。
于是，就Accepted啦！:D