IBM Ponder This #303 · July 2023

A game is played on a 2D board:

During every turn of the game, one piece is chosen and can be moved one step right, left, up or down, given enough free space in that direction.

The cost of moving a piece is $5-s$ where $s$ is the size of the piece, so moving a piece composed of four squares costs 1, while moving a piece of one square costs 4.

The goal of the game is to arrange the board according to some goal, with minimum cost.

Note that pieces of the same size and shape are considered identical.

For example, given the following goal for the original board above:

The sequence of steps reaching the goal from the beginning is:

The cost of the first 2 moves is 2, the third one is 3, and the last one is 4, totaling 11.

Given a board, a compact way to describe a solution is to number all the pieces, and then write a string of the form "3U5L" etc. to denote moves (first the number of the shape, and then the direction: U=Up, L=Left, R=Right, D=Down).

For the above board, we can use the following numbering:

So the solution is written as the following:

"1L2R4U7R"

Your goal Starting from this initial board:

Find a solution with a cost of no more than 100 that reaches the following goal:

A bonus "*" will be given for finding a solution with a cost of no more than 150 which, using the same initial board, reaches the following goal:

Solution

Best opened after a real attempt

To be added.