Connect with us:    

IBM Research YouTube IBM Research Blog

Ponder This

Welcome to our monthly puzzles.
You are cordially invited to match wits with some of the best minds in IBM Research.

April 2023 - Challenge

<< March May >>

A game is played on an n\times n grid of lightbulbs. We are given an initial state where some of the bulbs are off and some are on. Then, at every step:

  1. A bulb in the off state is chosen.

  2. The bulb is turned on, and every other bulb in the row and in the column of the bulb is toggled: If it was on, it turns off, and vice versa.

The goal of the game is to reach a grid where all the light bulbs are on. We use a coordinate system where the grid cell at column x and row y, with 1\le x,y \le n is denoted by (x,y) , where (1,1) is the bottom-left grid cell. A solution is denoted by a list of coordinates of the corresponding bulbs.

For example, given the initial grid state

0011
1101
0110
0001
Cell (1,3) is 1 while (3,1) is 0, and a solution is given by:
[(1, 1), (2, 4), (2, 3), (4, 4)]
As can be seen by following the changes:


0011       1011       0100       0000       1111
1101 (1,1) 0101 (2,4) 0001 (2,3) 1110 (4,4) 1111
0110  -->  1110  -->  1010  -->  1110  -->  1111
0001       1110       1010       1110       1111
Your goal: Find a solution for the initial state of this 24\times 24 grid:

000001000000000001110011
110100010110101000010011
011101110000001101001110
000110111000110101101100
101101011010010011101010
111000100101110100101000
110001011100000000000101
100000010001100000000010
000110010010110110101001
011101101011111011100000
011000101010111011111100
100011110010000100100111
000111010010100010001110
011001010001001111110101
110001000010111000100000
000000101100101000101001
111001010010010011110110
100000110001111111011010
110100000011100100110010
101000110111001110010000
110000000010011100100101
111111011011111100010101
000000000110101011100000
110001111100000011001111
A bonus "*" will be given for finding a solution with less than 430 steps for this 30\times 30 grid:

110001000000100101110011001000
010100001100011101010111100110
000110011010011111100010100010
111101110110011101110100110001
000110001000100011001101100010
101111001110110010111101001111
001110000101101001101000001101
111001110000101011111111110100
110000000000110111111001100100
111001110100111110001110111011
111010100010010100000001101100
010111110011001111110100001001
010100111011000001100000011010
010001010110111100100111001101
111111010001011100101100110110
101000110110010111111011001001
111011000100101111101001100010
101001100011010100010000100001
111111100111111110010111110010
010000010000011001001010010011
111010110011011111101100110110
011100110001101001100000000110
111110100101010000100011011010
111100011111000011110001001111
111000111111101011111011100100
101011000011001110101011000011
001101011101000001100101101001
010010100000011011100101010001
010111101001110100010110010010
110000011010111110100110000010

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: 01/04/2023 @ 10:00 AM EST
Solution: 10/05/2023 @ 09:00 AM EST
List Updated: 15/05/2023 @ 08:35 AM EST

People who answered correctly:

*Lazar Ilic(29/3/2023 7:24 PM IDT)
Yuping Luo(30/3/2023 6:58 AM IDT)
Gaétan Berthe(30/3/2023 8:57 PM IDT)
*Dominik Reichl(30/3/2023 9:24 PM IDT)
*Lorenz Reichel(30/3/2023 11:24 PM IDT)
*Bert Dobbelaere(30/3/2023 11:39 PM IDT)
*Nyles Heise(31/3/2023 8:24 AM IDT)
*Latchezar Christov(31/3/2023 3:36 PM IDT)
*Lorenzo Gianferrari Pini(31/3/2023 3:41 PM IDT)
Alex Fleischer(31/3/2023 7:30 PM IDT)
Uoti Urpala(1/4/2023 4:51 AM IDT)
*Harald Bögeholz(1/4/2023 6:13 AM IDT)
Daniel Stanley(1/4/2023 10:40 AM IDT)
Richard Gosiorovsky(1/4/2023 3:03 PM IDT)
*Bertram Felgenhauer(1/4/2023 6:03 PM IDT)
*Yan-Wu He(2/4/2023 3:18 PM IDT)
*Alper Halbutogullari(2/4/2023 7:03 PM IDT)
*Rob Pratt(2/4/2023 7:08 PM IDT)
*Martin Thorne(2/4/2023 10:50 PM IDT)
*Gary M. Gerken(2/4/2023 10:58 PM IDT)
*Reiner Martin(2/4/2023 11:02 PM IDT)
*Todd Will(2/4/2023 11:27 PM IDT)
*Daniel Chong Jyh Tar(3/4/2023 7:22 PM IDT)
*Tim Walters(4/4/2023 2:55 AM IDT)
*Lyes Belhoul(4/4/2023 4:42 AM IDT)
Sanandan Swaminathan(4/4/2023 10:17 AM IDT)
*Jan Pfeifer(4/4/2023 11:19 PM IDT)
John Goh(5/4/2023 9:29 AM IDT)
*Stéphane Higueret(6/4/2023 9:04 PM IDT)
*K S(7/4/2023 12:20 AM IDT)
*Sean Egan(7/4/2023 9:56 PM IDT)
*Amir Sarid(8/4/2023 2:21 AM IDT)
*Nimrod Ashkenazi(8/4/2023 5:48 PM IDT)
*Evan Schor(9/4/2023 12:41 AM IDT)
Vladimir Volevich(9/4/2023 4:37 PM IDT)
*Daniel Bitin(9/4/2023 11:45 PM IDT)
*Amos Guler(10/4/2023 12:21 PM IDT)
*Guy Daniel Hadas(10/4/2023 12:50 PM IDT)
*Ralf Jonas(11/4/2023 1:55 PM IDT)
*Peter Moser(11/4/2023 8:56 PM IDT)
*Marco Bellocchi(13/4/2023 1:57 PM IDT)
*David Eisenstat(13/4/2023 4:51 PM IDT)
*Hakan Summakoğlu(13/4/2023 10:52 PM IDT)
*Maksym Voznyy(16/4/2023 4:26 AM IDT)
*Sai Kiran Mayakuntla(16/4/2023 7:03 PM IDT)
*David Greer(16/4/2023 11:26 PM IDT)
Evan Semet(17/4/2023 4:51 AM IDT)
Rayan Swidan(18/4/2023 2:23 AM IDT)
Reda Kebbaj(19/4/2023 3:11 AM IDT)
*Dieter Beckerle(20/4/2023 11:10 PM IDT)
*Ralf Bonse(21/4/2023 12:53 PM IDT)
*Julien Pradier(21/4/2023 2:47 PM IDT)
*Kang Jin Cho(22/4/2023 9:19 PM IDT)
Phil Proudman(23/4/2023 8:50 PM IDT)
Anders Bisbjerg Madsen(23/4/2023 10:55 PM IDT)
*Michael Catalano-Johnson(24/4/2023 5:19 AM IDT)
*Ethan Watkins(25/4/2023 6:06 AM IDT)
*John Tromp(25/4/2023 11:25 AM IDT)
*Daniel Copeland & Raphael(25/4/2023 8:51 PM IDT)
Christoph Baumgarten(26/4/2023 2:16 PM IDT)
Jim Clare(26/4/2023 5:46 PM IDT)
*Andreas Puccio(27/4/2023 5:43 PM IDT)
Abhinav Bana(28/4/2023 10:11 AM IDT)
*Paul Shaw(28/4/2023 6:38 PM IDT)
*Motty Porat(29/4/2023 2:14 AM IDT)
*Daniel Lincke(29/4/2023 1:37 PM IDT)
*David F.H. Dunkley(30/4/2023 4:28 PM IDT)
*Carl Löndahl(30/4/2023 4:32 PM IDT)
*Kai Guttmann(30/4/2023 10:53 PM IDT)
*Oscar Volpatti(1/5/2023 7:56 PM IDT)
*Vaskor Basak(2/5/2023 1:59 AM IDT)
*Karl Mahlburg(2/5/2023 3:07 AM IDT)
*Li Li(2/5/2023 8:52 AM IDT)
Michael Schuresko(3/5/2023 2:57 AM IDT)
*Govind Raj Jujare(3/5/2023 4:13 AM IDT)
Hansraj Nahata(3/5/2023 5:07 AM IDT)
Matt Cristina(4/5/2023 11:58 PM IDT)
Radu-Alexandru Todor(5/5/2023 3:45 AM IDT)
*Shouky Dan & Tamir Ganor(8/5/2023 9:12 AM IDT)