This is the forty second part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Today we solve another puzzle: Fifteen puzzle. Let’s begin.

Game

Fifteen puzzle
Image from Wikipedia.

In order to solve the game using single tile moves, we need 80 of them. We will use exactly the same approach as when solving Rubik’s cub.e

Code

We start with defining initial position. Next, for every move we define variable representing the move: we can slide pieces right, down, left, or up. As commented, we don’t need dummy move because we can always make move down or right when we have empty piece in bottom-right corner and this will not change anything.

Next, we calculate indexes, extract source and destination, exchange them conditionally, and that’s all.

Summary

Presented approach is universal — we can easily adapt it to solve different riddles. Even when we don’t know the “God’s number”, we can approximate it or event make it so high to be sure that it will be enough.