A sliding puzzle is a grid of 9 squares with 8 tiles. The goal is to...

Transcribed Image Text:

A sliding puzzle is a grid of 9 squares with 8 tiles. The goal is to get the 8 tiles into order (the target configuration). A move slides a tile into an empty square. Below we show first a row move, then a column move. 123 466- 867 Prove that no sequence of moves produces the target configuration. [Hint: The tiles form a sequence going left to right, top to bottom. An inversion is a pair that is out of order. Prove by induction that the number of inversions stays odd. 123 300 A sliding puzzle is a grid of 9 squares with 8 tiles. The goal is to get the 8 tiles into order (the target configuration). A move slides a tile into an empty square. Below we show first a row move, then a column move. 123 466- 867 Prove that no sequence of moves produces the target configuration. [Hint: The tiles form a sequence going left to right, top to bottom. An inversion is a pair that is out of order. Prove by induction that the number of inversions stays odd. 123 300

Answer rating: 100% (QA)

To prove this we can use the following inductive step 1 Base case A puzzle with one t... View the full answer