November 2023 - Challenge
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 from1 6 2 4 9 5 3 8 10 7 11 12 13 15 14 0and apply the sequence of steps
[14, 11, 7, 10, 9, 5, 6 ,2, 3, 7, 11, 14]we arrive at the sorted board
1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 0
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.
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
Challenge:
29/10/2023 @ 11:10 AM EST
Solution:
05/12/2023 @ 12:00 PM EST
List Updated:
16/01/2024 @ 10:20 AM EST
People who answered correctly:
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)