Getting to eighty cubes: combinatorial search heuristics applied to N-Cube Instant Insanity

Includes bibliographical references (pages 42-42)The natural generalization of the Instant Insanity puzzle to n cubes has been shown to be NP-complete. An algorithm to solve the problem therefore requires exponential time unless P=NP. This fact, however, does not mean that the intelligent use of combinatorial search techniques cannot dramatically improve performance over the most basic brute force attack. This paper describes the implementation and performance testing of a number of such techniques. These techniques allow a modest computer (circa 2015) to solve typical instances in time (4/3)^8/10^8} minutes for n < 80