保持有关访问状态的信息的想法

Question

我现在制作了15个拼图解算器(用c ++编写),但不仅仅是15个拼图,我的程序还必须解决3x4拼图,8x8拼图等... - > X x Y拼图.我必须以某种方式保存有关访问状态的信息,我的第一个想法是制作树,例如:
拼图:

州1
1 2
3 0

州2
1 3
0 2

我留在树上:

root-> 1-> 2-> 3-> 0
            \ _
                \ - > 3-> 0-> 2

对于所有谜题,这也适用于拼图5x3,6x6等

这个想法有效,但是它浪费了大量内存,而且要添加节点,需要一些时间:/所以效率非常低.

下一个想法是在stl的std :: map <>中保持访问状态,但我不知道如何制作好的哈希函数 - 从拼图状态制作快捷方式(beacouse我不必存储拼图状态,我只需要信息已被访问.你有任何想法,关于std :: map的关键,或其他想法保持信息已被状态访问？

Answer 1

我将单个状态表示为 BigInteger 数字（此处提供了 C++ 实现，或者如果您想实现自己的状态，这里也有一个线程）。

假设您有一个尺寸为 (X,Y) 的拼图，您可以使用 base = X*Y 创建一个数字，并且该数字的数字将代表扁平化为一维的拼图块。

例如：

State 1
1 2
3 0

这将被扁平化为

1 2 3 0

然后转换成以 4 为基数的数字，例如：

state = (1 * (4^3)) + (2 * (4^2)) + (3 * 4) + 0;

这将唯一地标识任何谜题的任何给定状态。