拼图初始化算法实现
定理:图形A与图形B等价的充要条件图形A的排列的逆序数加上0元素行号和列号的奇偶性等于图形B的排列的逆序数加上0元素行号和列号的奇偶性。为方便表述,把图形排列的逆序数加上0元素行号和列号的奇偶性称为图形的奇偶性。(参考http://www.cppblog.com/lemene/archive/2007/10/04/33405.html)
排列 1 3 2 6 0 5 4 7 8,它的逆序数为8,0元素行号为2,列号为2。逆序数加行号,列号的奇偶性为偶。
排列 1 2 3 4 5 6 7 8 0,它的逆序数为8,0元素行号为3,列号为3。逆序数加行号,列号的奇偶性为偶。两个图形的奇偶性相同,根据定理判断它们等价。
for (int i=0; i<NODE_COUNT; i++) { nodes[i] = i; } shuffle(NODE_COUNT, nodes); if (parityCheck(NODE_COUNT, nodes) != parityCheck(NODE_COUNT, target)) { //若不满足定理,则交换数组最后两个值,使其奇偶性改变。 int i = nodes[NODE_COUNT-2]; nodes[NODE_COUNT-2] = nodes[NODE_COUNT-1]; nodes[NODE_COUNT-1] = i; }