Ruo Ando, Yoshiyasu Takefuji
CoRR abs/2012.08231 2020年12月15日
A sliding puzzle is a combination puzzle where a player slide pieces along
certain routes on a board to reach a certain end-configuration. In this paper,
we propose a novel measurement of complexity of massive sliding puzzles with
paramodulation which is an inference method of automated reasoning. It turned
out that by counting the number of clauses yielded with paramodulation, we can
evaluate the difficulty of each puzzle. In experiment, we have generated 100 *
8 puzzles which passed the solvability checking by countering inversions. By
doing this, we can distinguish the complexity of 8 puzzles with the number of
generated with paramodulation. For example, board [2,3,6,1,7,8,5,4, hole] is
the easiest with score 3008 and board [6,5,8,7,4,3,2,1, hole] is the most
difficult with score 48653. Besides, we have succeeded to obverse several
layers of complexity (the number of clauses generated) in 100 puzzles. We can
conclude that proposal method can provide a new perspective of paramodulation
complexity concerning sliding block puzzles.