-1
$\begingroup$

This quiz is about the 8-puzzle. It is a board with 9 spaces. There are 8 tiles with the numbers 1 through 8. One space is empty (.). You slide the tiles around the board, but only numbers next to the empty space can be slid into the empty space.

The starting configuration is

$$ % Preview . \:\: 8 \:\: 7 \\ % . 8 7 6 \:\: 5 \:\: 4 \\ % 6 5 4 3 \:\: 2 \:\: 1 % 3 2 1 $$

The end configuration is

$$ % Preview . \:\: 1 \:\: 2 \\ % . 1 2 3 \:\: 4 \:\: 5 \\ % 3 4 5 6 \:\: 7 \:\: 8 % 6 7 8 $$

The goal is to get the board from the start configuration to the end configuration in 12 steps. Sliding two tiles at the same time counts as two steps.

$\endgroup$
  • 3
    $\begingroup$ What do you mean by a "step"? Surely to get each of the 1, 2, 7, 8 tiles to its new position will take three steps, using up the twelve already without even fixing the 3, 4, 5, 6 tiles. $\endgroup$ – Rand al'Thor Dec 4 '19 at 22:20
  • 1
    $\begingroup$ i meant a 'move' $\endgroup$ – Richard Dec 4 '19 at 22:22
  • 1
    $\begingroup$ it would count as 2 steps $\endgroup$ – Richard Dec 4 '19 at 22:54
  • 2
    $\begingroup$ As Randal'Thor mentioned, it's not possible if you count a step as moving a single tile. I verified this with a brute-force algorithm on this site: tristanpenman.com/demos/n-puzzle $\endgroup$ – Skylar Dec 4 '19 at 23:14
  • 6
    $\begingroup$ Step 1: Open the frame. Step 2: Dump out all the tiles.... $\endgroup$ – aschepler Dec 5 '19 at 1:35
6
$\begingroup$

It is not possible to do this in 12 steps. In fact, a simple argument shows that at least 20 steps are necessary:

    Tiles 1 and 8 need to be swapped. They are however a distance of 3 moves apart, so each tile needs to be moved at least 3 times. Similarly, tiles 2 and 7 also each need 3 moves to reach their goal locations. So these 4 tiles together need at least 12 moves to be solved.

    Tiles 3 and 6 need to be swapped and are each 1 move away from their goal location, but since they cannot pass through each other, one of the tiles needs to temporarily move to a different row, so together these 2 tiles need at least 4 moves. Similarly tiles 4 and 5 also need 4 moves.

I have run this position through a solver, and it actually turns out that the fewest number of moves to solve it is 30. Even if shifting two tiles at the same time is considered a single move, it needs 21 moves.

 . 1 2   3 1 2   3 1 2   3 1 .   3 . 1 
 3 4 5   . 4 5   4 5 .   4 5 2   4 5 2 
 6 7 8   6 7 8   6 7 8   6 7 8   6 7 8 
 
 3 5 1   3 5 1   . 5 1   5 . 1   5 7 1 
 4 7 2   4 7 2   3 7 2   3 7 2   3 6 2 
 6 . 8   . 6 8   4 6 8   4 6 8   4 . 8 
 
 5 7 1   5 7 .   5 . 7   5 6 7   5 6 7 
 3 6 2   3 6 1   3 6 1   3 8 1   3 8 1 
 4 8 .   4 8 2   4 8 2   4 . 2   . 4 2 
 
 . 6 7   6 . 7   6 8 7   6 8 7   6 8 7 
 5 8 1   5 8 1   5 4 1   5 4 1   5 4 . 
 3 4 2   3 4 2   3 . 2   3 2 .   3 2 1 
 
 6 8 7   . 8 7 
 . 5 4   6 5 4 
 3 2 1   3 2 1 
 

$\endgroup$
  • $\begingroup$ It is well known that these two positions need the largest number of moves - assuming the 0 is in the same corner before and after. $\endgroup$ – WhatsUp Dec 5 '19 at 1:09
  • $\begingroup$ @WhatsUp Not true. There are two positions that are at distance 31 from the starting position. See for example here, but turn them upside-down for this question's upside-down starting position. $\endgroup$ – Jaap Scherphuis Dec 5 '19 at 6:18
  • $\begingroup$ I did say assuming the 0 is in the same corner before and after... $\endgroup$ – WhatsUp Dec 5 '19 at 10:53
  • $\begingroup$ @WhatsUp Sorry, you're right. The only ones at 31 don't have the blank in the same place as the start. $\endgroup$ – Jaap Scherphuis Dec 5 '19 at 10:56
  • $\begingroup$ Several decades ago we played this game in our primary school, at the age of ~7. Our math teacher told us the fact that, if one only exchanges the positions of two numbers and keeps the remaining, then it's unsolvable. This might be easy with a bit of group theory, but it was amazing how he managed to explain it to children of age 7! $\endgroup$ – WhatsUp Dec 5 '19 at 11:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.