Ponder This Challenge - July 2023 - Sliding Pieces Game

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:

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  July 2023 Solution:

  We can use an undirected graph a to decribe the states of the board with edge between two states which differ by one piece move (the graph is undirected since every move is reversible). We add edge weights according to the size of the piece moved, and this transforms the problem into standard shortest-path finding in a graph. Since the the of possible nodes is relatively big, it is best to use a shortest-path finding algorithm which gradually adds new nodes based on their path-length from the source, such as Dijkstra's algorithm (some solvers reported using A* or simple BFS). Some solvers turned to the classic metod instead - solving by hand, which is indeed possible in this problem. One such solution, found by Bertram Felgenhauer, is:

  Main problem:
  8D9D5D6D7L7L4D3D3D2R2R1R1R7U7U5U6U6U3L3L1D1D1R3R3U9U9R5D5D5R6L6D6D
  Bonus problem:
  8D9D7D6R5R1D1D2L3L7L4L4D4D3R3R2R2R1U1U5L6L7L4L3D2R4U4U4L2L3U8U9R9R9R7D7R6D5R1D1D1D4L4D2L3L8U6
  R6R6R5D5R5R
  

  The solver K S was kind enough to create animated GIFs of his solutions:

Solvers

• Lazar Ilic (3/7/2023 4:12 PM IDT)
• *Nathan Salo (3/7/2023 10:24 PM IDT)
• *Martin Thorne (3/7/2023 10:27 PM IDT)
• Guillaume Escamocher (3/7/2023 10:55 PM IDT)
• *Yan-Wu He (4/7/2023 3:04 AM IDT)
• Victor Chang (4/7/2023 6:56 AM IDT)
• *Evan Semet (4/7/2023 8:12 AM IDT)
• *Alper Halbutogullari (4/7/2023 8:33 AM IDT)
• *Sanandan Swaminathan (4/7/2023 10:27 AM IDT)
• *Harald Bögeholz (4/7/2023 10:57 AM IDT)
• Giorgos Kalogeropoulos (4/7/2023 11:17 AM IDT)
• *Phil Proudman (4/7/2023 11:50 AM IDT)
• Fabio Michele Negroni (4/7/2023 1:28 PM IDT)
• *Lyes Belhoul (4/7/2023 5:46 PM IDT)
• *Bertram Felgenhauer (4/7/2023 6:51 PM IDT)
• *Luka Mushkudiani (4/7/2023 10:20 PM IDT)
• *Bert Dobbelaere (5/7/2023 12:40 AM IDT)
• Evan Schor (5/7/2023 9:11 AM IDT)
• *Hok Leung Nip (5/7/2023 5:17 PM IDT)
• *Quentin Higueret (5/7/2023 5:24 PM IDT)
• *Savitha Viswanadh Kandala (5/7/2023 8:28 PM IDT)
• *Kandala Viswakanth (5/7/2023 8:44 PM IDT)
• *Todd Will (5/7/2023 11:15 PM IDT)
• *Daniel Chong Jyh Tar (6/7/2023 5:12 AM IDT)
• *Nathan Hopkins (6/7/2023 5:54 AM IDT)
• *Vladimir Volevich (6/7/2023 7:24 PM IDT)
• *Dominik Reichl (6/7/2023 9:11 PM IDT)
• *Tim Walters (6/7/2023 11:07 PM IDT)
• *Andrew Gauld (7/7/2023 4:23 AM IDT)
• *Nicolas Paris (7/7/2023 5:08 PM IDT)
• *James Heayes (7/7/2023 5:15 PM IDT)
• Reiner Martin (7/7/2023 9:30 PM IDT)
• *Prashant Wankhede (8/7/2023 4:13 AM IDT)
• *Daniel Bitin (9/7/2023 11:46 PM IDT)
• Gary M. Gerken (10/7/2023 5:48 AM IDT)
• Kanit Pongteeraroj (10/7/2023 12:04 PM IDT)
• *Julien Vincent Pradier (10/7/2023 4:09 PM IDT)
• *Armin Krauss (10/7/2023 8:24 PM IDT)
• *Dieter Beckerle (10/7/2023 9:36 PM IDT)
• Hakan Summakoğlu (10/7/2023 11:55 PM IDT)
• *Li Li (11/7/2023 3:02 AM IDT)
• *Stéphane Higueret (11/7/2023 9:45 AM IDT)
• Andras Varga (11/7/2023 11:05 AM IDT)
• *Dan Mayer (11/7/2023 5:52 PM IDT)
• *David F.H. Dunkley (11/7/2023 10:52 PM IDT)
• *Michael J. Swart (12/7/2023 5:08 AM IDT)
• Lazar Ilic (3/7/2023 4:12 PM IDT)
• *Nathan Salo (3/7/2023 10:24 PM IDT)
• *Martin Thorne (3/7/2023 10:27 PM IDT)
• Guillaume Escamocher (3/7/2023 10:55 PM IDT)
• *Yan-Wu He (4/7/2023 3:04 AM IDT)
• Victor Chang (4/7/2023 6:56 AM IDT)
• *Evan Semet (4/7/2023 8:12 AM IDT)
• *Alper Halbutogullari (4/7/2023 8:33 AM IDT)
• *Sanandan Swaminathan (4/7/2023 10:27 AM IDT)
• *Harald Bögeholz (4/7/2023 10:57 AM IDT)
• Giorgos Kalogeropoulos (4/7/2023 11:17 AM IDT)
• *Phil Proudman (4/7/2023 11:50 AM IDT)
• Fabio Michele Negroni (4/7/2023 1:28 PM IDT)
• *Lyes Belhoul (4/7/2023 5:46 PM IDT)
• *Bertram Felgenhauer (4/7/2023 6:51 PM IDT)
• *Luka Mushkudiani (4/7/2023 10:20 PM IDT)
• *Bert Dobbelaere (5/7/2023 12:40 AM IDT)
• Evan Schor (5/7/2023 9:11 AM IDT)
• *Hok Leung Nip (5/7/2023 5:17 PM IDT)
• *Quentin Higueret (5/7/2023 5:24 PM IDT)
• *Savitha Viswanadh Kandala (5/7/2023 8:28 PM IDT)
• *Kandala Viswakanth (5/7/2023 8:44 PM IDT)
• *Todd Will (5/7/2023 11:15 PM IDT)
• *Daniel Chong Jyh Tar (6/7/2023 5:12 AM IDT)
• *Nathan Hopkins (6/7/2023 5:54 AM IDT)
• *Vladimir Volevich (6/7/2023 7:24 PM IDT)
• *Dominik Reichl (6/7/2023 9:11 PM IDT)
• *Tim Walters (6/7/2023 11:07 PM IDT)
• *Andrew Gauld (7/7/2023 4:23 AM IDT)
• *Nicolas Paris (7/7/2023 5:08 PM IDT)
• *James Heayes (7/7/2023 5:15 PM IDT)
• Reiner Martin (7/7/2023 9:30 PM IDT)
• *Prashant Wankhede (8/7/2023 4:13 AM IDT)
• *Daniel Bitin (9/7/2023 11:46 PM IDT)
• Gary M. Gerken (10/7/2023 5:48 AM IDT)
• Kanit Pongteeraroj (10/7/2023 12:04 PM IDT)
• *Julien Vincent Pradier (10/7/2023 4:09 PM IDT)
• *Armin Krauss (10/7/2023 8:24 PM IDT)
• *Dieter Beckerle (10/7/2023 9:36 PM IDT)
• Hakan Summakoğlu (10/7/2023 11:55 PM IDT)
• *Li Li (11/7/2023 3:02 AM IDT)
• *Stéphane Higueret (11/7/2023 9:45 AM IDT)
• Andras Varga (11/7/2023 11:05 AM IDT)
• *Dan Mayer (11/7/2023 5:52 PM IDT)
• *David F.H. Dunkley (11/7/2023 10:52 PM IDT)
• *Michael J. Swart (12/7/2023 5:08 AM IDT)
• *Vaskor Basak (12/7/2023 3:50 PM IDT)
• *Asaf Zimmerman (12/7/2023 5:59 PM IDT)
• *Soonho You (12/7/2023 6:31 PM IDT)
• Ritesh Goenka (14/7/2023 7:39 AM IDT)
• Matt Cristina (14/7/2023 8:02 PM IDT)
• *Guy Daniel Hadas (15/7/2023 11:43 PM IDT)
• *Jim Clare (16/7/2023 2:22 AM IDT)
• *Sri Mallikarjun J (16/7/2023 5:16 PM IDT)
• *Alain Michiels (16/7/2023 8:11 PM IDT)
• *K S (17/7/2023 5:04 AM IDT)
• *Nyles Heise (17/7/2023 8:08 AM IDT)
• Alex Fleischer (17/7/2023 12:15 PM IDT)
• *William Cho (18/7/2023 5:51 AM IDT)
• Hansraj Nahata (19/7/2023 4:19 AM IDT)
• *Karl Mahlburg (19/7/2023 4:40 AM IDT)
• *Paolo Farinelli (19/7/2023 4:24 PM IDT)
• Austin Lee (19/7/2023 5:34 PM IDT)
• Teawoo Kim (19/7/2023 10:24 PM IDT)
• *Diane Pham (20/7/2023 3:40 PM IDT)
• *Digant Patel (21/7/2023 4:33 PM IDT)
• *David Greer (22/7/2023 2:00 PM IDT)
• *Fakih Karademir (22/7/2023 2:03 PM IDT)
• Lorenz Reichel (22/7/2023 6:59 PM IDT)
• Gail Jardine (22/7/2023 9:33 PM IDT)
• *Digant Patel (23/7/2023 10:39 AM IDT)
• *Christian Romon (23/7/2023 11:49 AM IDT)
• *Nikita Sirons (23/7/2023 12:47 PM IDT)
• *Greg Janée (23/7/2023 5:20 PM IDT)
• *Hansraj Nahata (23/7/2023 5:26 PM IDT)
• Aaron Kim (24/7/2023 2:42 AM IDT)
• *Michael Liepelt (24/7/2023 9:44 PM IDT)
• *Chris Shannon (25/7/2023 9:57 AM IDT)
• Kay Lee (26/7/2023 3:29 PM IDT)
• Olivia Jezler & Stefan Wirth (27/7/2023 4:45 AM IDT)
• *Petro Mudrievskyj (27/7/2023 8:31 AM IDT)
• *Daniel Lincke (27/7/2023 1:10 PM IDT)
• Yannick (28/7/2023 12:44 PM IDT)
• *Kang Jin Cho (29/7/2023 2:36 AM IDT)
• Daniel Copeland & Isaac Lawrence & Raphael Deem (29/7/2023
• 10:31 AM IDT)
• *José Eduardo Gaboardi de Carvalho (30/7/2023 11:12 PM
• IDT)
• *Latchezar Christov (31/7/2023 10:10 PM IDT)
• *Marco Bellocchi (1/8/2023 7:13 PM IDT)
• *Radu-Alexandru Todor (2/8/2023 2:21 AM IDT)
• Diogo Cavaco (2/8/2023 11:57 AM IDT)
• *Motty Porat (3/8/2023 12:12 AM IDT)
• Mansi Pai (3/8/2023 6:28 PM IDT)
• Blaine Hill (3/8/2023 10:16 PM IDT)
• Arash Yazdani (4/8/2023 6:58 PM IDT)
• Xiao Liu (5/8/2023 11:50 PM IDT)
• *Govind Jujare (23/8/2023 11:45 PM IDT)