Solvability conditions for (n^2-1)-puzzle with fixed cells

Abstract

(n^2-1)-puzzle is a puzzle within square board with n × n unit square cells where n ≥ 3, labelled as cell c ∈ {1, 2, 3, ..., n^2}, in order from left to right, and then from the upper row to the lower row. There are n^2-1 cells contains a unit square tile labelled by number t ∈ {1, 2, 3, ..., n^2-1}, and the other cell contains a single hole. Beginning with an initial configuration of the board, where the first n^2-1 cells contain the tiles with numbers, and the hole is at the bottom-right corner cell, a player has to make moves by switching the hole and a tile next to the hole, so that we can transform the board to the configuration that all tiles are arranged in order from 1 to n^2-1 with the hole in the bottom-right corner cell. The more challenging puzzle is when a board consists of some fixed cells. The tile located at a fixed cell cannot be moved. This research focuses on solvability conditions of an initial configuration of a board with a single fixed cell and a board with two fixed cells. We conclude that for an n × n board with a fixed cell, any even configuration is solvable if and only if the fixed cell is not in {2, n-1, n+1, 2n, n^2-2n+1, n^2-n, n^2-n+2, n^2-1}. As for a board with two fixed cells, we give conditions on the positions of the fixed cells where not all even configuration are solvable. Moreover, some sufficient conditions that make all even configurations solvable are provided.