Ponder This Challenge - November 2023 - The 15 Puzzle and magic squares

The 15 Puzzle is composed of a 4x4 grid of squares containing the numbers from 0 to 15. In each turn, the number 0 is swapped with one of its neighbours. It is also customary to treat the 0 square simply as an empty space, as is done in physical versions of the game.

The usual goal of the puzzle is to start from a random board and arrive at a sorted board. It is a well-known fact that it is not possible to reach every possible combination of numbers in position from every other position. For example, from fully sorted board, it is not possible to reach an almost sorted board where 14 and 15 are swapped. However, every board can be arranged to arrive at one of those two boards. As a result, we consider both boards to be sorted for this challenge:

The sequence of steps performed on the board can be described by a list of the non-0 numbers being swapped with 0 at every stage.

For example, if we start from

and apply the sequence of steps

we arrive at the sorted board

A magic square is an n x n grid of numbers where the sums of each row, column and diagonal are equal. In the case of the 4 x 4 grid with the numbers from 0 to 15, this means a sum of 30.

Your goal: Starting from one of the two sorted boards, arrive at a board that is a magic square in 150 steps or less. Give your solution as a sequence of steps as above; also provide the initial and final states for reference.

A Bonus "*" will be given for solving the main problem in 50 steps or less.

Solution

• Click here to view the solution

  November 2023 Solution:

  Solution

  The optimal number of steps possible is 35. One way to obtain this minimum is the sequence

  [12, 11, 10, 9, 5, 6, 2, 3, 4, 8, 7, 10, 15, 12, 11, 7, 8, 4, 10, 15, 9, 5, 13, 14, 5, 2, 3, 10,  
  
   15, 3, 6, 13, 2, 9, 12]
  

  Leading from

  1 2 3 4
  5 6 7 8
  9 10 11 12
  13 14 15 0
  

  to

  1 10 15 4
  13 6 3 8
  2 9 12 7
  14 5 0 11
  

  A common method for solving this problem is using the A* algorithm. A more exhustive approach finds all possible 4x4 magic sqaures (7040 in total) and searching for a path from the initial boards to one of them. Vladimir Volevich suggested optimizing this method by utilizing "meet in the middle" tactic, expanding simultaneously the sets of positions reachable from the initial states and positions reachable from the magic squares and searching for a common element. This ensures none of the sets grow too much out of control, making the search feasible.

Solvers

• Lazar Ilic (29/10/2023 12:17 PM IDT)
• *Bertram Felgenhauer (29/10/2023 1:41 PM IDT)
• *Paul Lupascu (29/10/2023 4:57 PM IDT)
• *Bert Dobbelaere (29/10/2023 5:00 PM IDT)
• *Alper Halbutogullari (29/10/2023 5:40 PM IDT)
• *Gary M. Gerken (29/10/2023 7:43 PM IDT)
• *Giorgos Kalogeropoulos (29/10/2023 11:10 PM IDT)
• *Michael Liepelt (30/10/2023 12:04 AM IDT)
• *Jeff Harris (30/10/2023 1:15 AM IDT)
• *Martin Thorne (30/10/2023 7:33 AM IDT)
• *Evert van Dijken (30/10/2023 1:01 PM IDT)
• *Stéphane Higueret (30/10/2023 1:39 PM IDT)
• *Quentin Higueret (30/10/2023 3:02 PM IDT)
• *John Kelly (30/10/2023 3:09 PM IDT)
• *Soham Sud (30/10/2023 3:31 PM IDT)
• *Florian Sikora (30/10/2023 4:40 PM IDT)
• Yan-Wu He (30/10/2023 7:14 PM IDT)
• *Paul Revenant (30/10/2023 10:21 PM IDT)
• John Tromp (30/10/2023 10:48 PM IDT)
• *Blaine Hill (30/10/2023 11:07 PM IDT)
• *Evan Semet (31/10/2023 7:00 AM IDT)
• Sanandan Swaminathan (31/10/2023 9:21 AM IDT)
• *Dan Dima (31/10/2023 11:36 AM IDT)
• Yi Jiang (31/10/2023 12:56 PM IDT)
• *Guglielmo Sanchini (31/10/2023 2:54 PM IDT)
• *Hugo Pfoertner (31/10/2023 4:29 PM IDT)
• *Lyes Belhoul (31/10/2023 10:40 PM IDT)
• *Franciraldo Cavalcante (1/11/2023 2:51 AM IDT)
• Reda Kebbaj (1/11/2023 6:57 AM IDT)
• Dieter Beckerle (1/11/2023 7:52 AM IDT)
• *Sanandan Swaminathan (1/11/2023 12:01 PM IDT)
• Lorenz Reichel (1/11/2023 2:56 PM IDT)
• *Dieter Beckerle (1/11/2023 3:02 PM IDT)
• *Yan-Wu He (1/11/2023 9:37 PM IDT)
• Frank Schoeps (2/11/2023 2:25 AM IDT)
• *Kevin Bauer (2/11/2023 2:33 AM IDT)
• Soonho You (2/11/2023 8:51 AM IDT)
• *Thomas Mangan (2/11/2023 9:50 AM IDT)
• *Daniel Chong Jyh Tar (2/11/2023 10:52 AM IDT)
• *Vladimir Volevich (2/11/2023 12:30 PM IDT)
• *Arthur Vause (2/11/2023 1:08 PM IDT)
• *Matt Cristina (2/11/2023 6:57 PM IDT)
• Fabio Michele Negroni (2/11/2023 8:24 PM IDT)
• *Ray Greiss (2/11/2023 9:45 PM IDT)
• *Hakan Summakoğlu (2/11/2023 11:11 PM IDT)
• Adrian Neacsu (3/11/2023 12:54 AM IDT)
• *Andrew Gauld (3/11/2023 1:45 AM IDT)
• *John Spurgeon (3/11/2023 5:43 AM IDT)
• *Ralf Jonas (3/11/2023 8:36 AM IDT)
• *Phong Kah Ho (3/11/2023 2:27 PM IDT)
• Guillaume Escamocher (3/11/2023 4:48 PM IDT)
• *Tim Walters (3/11/2023 10:19 PM IDT)
• *Michael Branicky (4/11/2023 1:03 AM IDT)
• *Dillon Davis (4/11/2023 8:20 AM IDT)
• Julien Vincent Pradier (4/11/2023 10:16 AM IDT)
• *Cameron Ritson (4/11/2023 10:45 AM IDT)
• *David Greer (4/11/2023 7:52 PM IDT)
• *Nyles Heise (4/11/2023 10:07 PM IDT)
• *Julien Vincent Pradier (5/11/2023 1:12 AM IDT)
• *Evan Schor (5/11/2023 3:54 AM IDT)
• *John Spurgeon (5/11/2023 7:40 AM IDT)
• *Clive Tong (5/11/2023 10:10 AM IDT)
• Gyozo Nagy (5/11/2023 11:24 AM IDT)
• *Prashant Wankhede (5/11/2023 5:46 PM IDT)
• *Todd Will (5/11/2023 7:35 PM IDT)
• *Yi Jiang (6/11/2023 7:16 AM IDT)
• *Oleg Vlasii (6/11/2023 9:08 AM IDT)
• *Dieter Beckerle (6/11/2023 12:31 PM IDT)
• *Latchezar Christov (6/11/2023 5:37 PM IDT)
• *Serino Dario (6/11/2023 6:54 PM IDT)
• *Kang Jin Cho (6/11/2023 7:43 PM IDT)
• *Alexander Marschoun (7/11/2023 12:07 AM IDT)
• *Wenjie Yang (7/11/2023 12:52 AM IDT)
• *Shouky Dan & Tamir Ganor (7/11/2023 10:36 AM IDT)
• *Uoti Urpala (7/11/2023 3:29 PM IDT)
• *Dominik Reichl (7/11/2023 8:55 PM IDT)
• *Harald Bögeholz (8/11/2023 8:41 PM IDT)
• Amos Guler (8/11/2023 9:09 PM IDT)
• *Kai Guttmann (9/11/2023 12:29 AM IDT)
• *Dezhi Zhao (9/11/2023 7:09 PM IDT)
• Marcel Caria (10/11/2023 12:38 AM IDT)
• *Guy Daniel Hadas (11/11/2023 3:15 PM IDT)
• Sachal Mahajan (11/11/2023 7:18 PM IDT)
• *Abhinav Bana (12/11/2023 8:06 AM IDT)
• *Armin Krauss (12/11/2023 6:16 PM IDT)
• *Alex Fleischer (12/11/2023 8:17 PM IDT)
• *José Eduardo Gaboardi de Carvalho (12/11/2023 9:33 PM IDT)
• *Fakih Karademir (13/11/2023 12:26 PM IDT)
• *Alain Michiels (13/11/2023 3:55 PM IDT)
• *Andreas Knüpfer (14/11/2023 3:12 PM IDT)
• Ashfaque Shaikh (14/11/2023 5:09 PM IDT)
• *Andreas Eisele (15/11/2023 12:28 AM IDT)
• *Alok Menghrajani (16/11/2023 11:11 AM IDT)
• *Sergey Koposov (16/11/2023 8:59 PM IDT)
• *David F.H. Dunkley (18/11/2023 2:52 PM IDT)
• Adrienne Stanley (19/11/2023 3:12 AM IDT)
• Christoph Baumgarten (19/11/2023 9:22 PM IDT)
• *Rajesh Sathiyanarayanan (20/11/2023 1:46 PM IDT)
• *Marco Bellocchi (21/11/2023 2:15 AM IDT)
• *Victor Chang (21/11/2023 6:19 AM IDT)
• *Karl Mahlburg (22/11/2023 12:38 AM IDT)
• *Daniel Bitin (23/11/2023 9:16 PM IDT)
• *Motty Porat (24/11/2023 1:24 AM IDT)
• *Michael Wei (25/11/2023 5:19 AM IDT)
• *Grant Boudreaux (26/11/2023 3:39 PM IDT)
• *Oscar Volpatti (28/11/2023 6:22 AM IDT)
• *Dario Filatrella (28/11/2023 2:09 PM IDT)
• *Sebastian Arellano-Rubach & Kenny Huang & Eleanora Melkonian & Allen Yang (28/11/2023 7:01 PM IDT)
• *Isaac Greenleaf (29/11/2023 3:48 AM IDT)
• *Chris Shannon (29/11/2023 8:29 AM IDT)
• Greg Janée (29/11/2023 9:18 PM IDT)
• Vaskor Basak (29/11/2023 10:30 PM IDT)
• *Jack Qiu & Soham Chakraborty & Lucas Craiu & Raymond Wu (1/12/2023 2:52 AM IDT)
• *Li Li (1/12/2023 10:02 AM IDT)
• *James Song & Jarmin Weng & William Li (2/12/2023 6:41 AM IDT)
• Radu-Alexandru Todor (4/12/2023 3:42 AM IDT)
• *Reiner Martin (5/12/2023 12:50 AM IDT)
• *Daniel Copeland (6/12/2023 1:42 AM IDT)