# Sliding jigsaw configurations

• Jul 26th 2011, 04:26 AM
godelproof
Sliding jigsaw configurations
Consider an $N\times N$ sliding jigsaw (SJ) with an empty block and ${N}^{2}-1$ numbered blocks from $1$ to ${N}^{2}-1$ (see the attachment for a configuration of a $4 \times 4$ SJ, where blocks $8,5,2$ or $9$ can move to the empty block, leaving their blocks empty, which any of their adjacent neighbors can in turn move to, ect.)

Definition 1: A configuration is standard, if the empty block is at the northwest corner of the board.

Definition 2: A configuration is ordered, if every block is greater than the block to its left (the first block of a row is greater than the last block of the previous row), ignoring the empty block.

Question 1: Starting from a standard configuration of an $N\times N$ SJ, how many different standard configurations can we reach?

Question 2: Starting from an arbitary configuration, can we reach an ordered SJ?
• Jul 26th 2011, 12:39 PM
Opalg
Re: Sliding jigsaw configurations
There is a very clear analysis of the 4x4 case here, with enough information to give you some good hints on tackling the NxN case.
• Jul 26th 2011, 08:28 PM
godelproof
Re: Sliding jigsaw configurations
Q1: $({N}^{2}-1)!/2$