Solver and solutions: https://gist.github.com/CyberShadow/39f43cf25dac0534f8a9 The solver uses BFS with delayed duplicate detection for pruning visited states (instead of, say, hash tables). The DDD part can be summed up in two lines of code: prevStates = (prevStates ~ states).sort.uniq.array(); states = nextStates.sort.uniq.setDifference(prevStates).array(); // ... expand states into nextStates ... These were part o…
1. Duplicate detection is done delayed and in bulk, not after expanding each node
2. The linear memory access of the bulk check is more cache friendly than random-like hash table access
Allow me to quote from the first Google result:
Surprisingly, delayed duplicate detection is useful even when all nodes fit in memory, resulting in reduced running time due to improved cache performance. In the standard implementation of breadth-first search in memory, the Open list is stored in a hash table. As each new node is generated, it is looked up in the hash table, which often results in a cache miss, since the hash function is designed to randomly scatter the nodes.
http://www.ijcai.org/Past%20Proceedings/IJCAI-2003/PDF/267.p...