Ponder This Challenge - April 2023 - Lightbulb grid game

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

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:

Your goal: Find a solution for the initial state of this $24\times 24$ grid:

A bonus "*" will be given for finding a solution with less than 430 steps for this $30\times 30$ grid:

Solution

• Click here to view the solution

  April 2023 Solution:

  The riddle is a variant of the “lights out” game, with the additional constraint that only “off” lamps can be turned on. The usually solution for lights out is based on solving a system of linear equations Ax=1 where A is the adjacency matrix of the corresponding graph, with the assumption that all lamps are turned off at the beginning. This can be adapted to solve the current riddle by:

  1. Changing the goal vector 1 according to the board’s initial state.
  2. After finding a solution, choosing an order in which each time an “off” lamp is used. Naïve heuristics usually solve this quickly.

  One possible solution, found by David Greer, is:

  [(12, 10), (21, 15), (23, 19), (14, 17), (18, 15), (20, 13), (10, 20), (23, 22), (1, 15), (16, 2), (23, 4), (12, 5), (20, 2), (14, 5), (15, 24), (6, 6), (19, 3), (3, 1), (9, 20), (20, 20), (5, 23), (3, 14), (2, 16), (18, 16), (22, 16), (6, 14), (13, 18), (19, 1), (11, 3), (15, 5), (2, 20), (2, 7), (4, 11), (13, 24), (15, 21), (10, 16), (20, 24), (24, 12), (15, 2), (21, 16), (8, 12), (14, 21), (5, 5), (4, 17), (8, 4), (13, 19), (3, 4), (24, 10), (5, 17), (14, 11), (9, 1), (23, 12), (10, 3), (22, 23), (11, 18), (6, 13), (23, 6), (6, 20), (13, 23), (10, 18), (1, 5), (22, 12), (5, 7), (16, 23), (15, 4), (4, 4), (19, 7), (11, 2), (17, 13), (11, 24), (14, 15), (1, 9), (5, 8), (11, 4), (24, 3), (4, 15), (20, 19), (11, 9), (8, 22), (15, 11), (11, 5), (8, 19), (6, 21), (19, 24), (13, 22), (3, 7), (23, 16), (8, 21), (16, 22), (2, 13), (14, 1), (1, 23), (13, 7), (17, 12), (22, 21), (20, 6), (24, 15), (10, 4), (12, 11), (17, 3), (20, 16), (24, 4), (22, 2), (19, 6), (19, 17), (21, 20), (18, 4), (4, 21), (22, 14), (18, 22), (24, 14), (21, 19), (9, 10), (23, 5), (1, 14), (24, 23), (16, 21), (7, 7), (22, 18), (2, 22), (12, 12), (11, 13), (15, 3), (6, 3), (22, 22), (24, 1), (13, 3), (11, 8), (2, 15), (18, 14), (19, 21), (3, 17), (18, 13), (11, 22), (10, 17), (12, 9), (24, 6), (7, 13), (5, 12), (18, 24), (22, 17), (20, 1), (18, 19), (9, 3), (15, 7), (4, 5), (4, 6), (8, 2), (5, 20), (11, 21), (24, 11), (4, 7), (16, 8), (2, 5), (2, 17), (24, 16), (9, 22), (12, 7), (12, 3), (18, 3), (17, 14), (23, 3), (4, 22), (21, 7), (16, 6), (13, 16), (9, 6), (2, 2), (12, 21), (1, 1), (17, 23), (1, 24), (4, 2), (3, 23), (1, 12), (18, 21), (20, 14), (4, 19), (7, 5), (17, 4), (15, 18), (10, 9), (5, 1), (19, 14), (18, 23), (14, 10), (9, 12), (21, 24), (22, 19), (4, 13), (21, 6), (1, 20), (16, 1), (7, 6), (6, 9), (11, 20), (4, 12), (1, 17), (1, 8), (21, 18), (10, 11), (10, 8), (19, 15), (11, 23), (21, 10), (7, 18), (12, 22), (4, 8), (3, 2), (7, 19), (13, 2), (23, 2), (8, 18), (1, 22), (7, 24), (24, 13), (12, 14), (24, 22), (14, 13), (5, 21), (22, 7), (16, 17), (12, 18), (5, 2), (12, 17), (9, 24), (5, 4), (5, 19), (2, 14), (7, 10), (18, 17), (3, 15), (14, 14), (6, 8), (17, 17), (1, 21), (2, 18), (10, 7), (7, 1), (20, 17), (1, 19), (13, 17), (17, 19), (17, 15), (18, 5), (3, 13), (1, 4), (5, 11), (2, 6), (19, 5), (15, 23), (15, 12), (15, 6), (19, 9), (1, 7), (7, 12), (22, 20), (20, 4), (1, 13), (12, 24), (19, 10), (3, 16), (4, 1), (16, 20), (3, 22), (6, 1), (14, 23), (14, 2), (23, 11), (12, 19), (22, 5), (21, 1), (1, 3), (2, 10), (10, 13), (6, 11), (23, 24), (24, 21), (19, 23), (11, 16)] [(2,28), (8,25), (5,21), (6,20), (1,18), (12,17), (13,16), (14,14), (19,12), (16,11), (9, 10), (17,9), (15,7), (27,6), (23,4), (3,3), (28,1), (30, 11), (21, 10), (5, 18), (18, 4), (25, 12), (23, 7), (30, 7), (13, 2), (22, 13), (30, 22), (12, 5), (20, 6), (29, 1), (25, 6), (17, 20), (9, 14), (4, 15), (11, 29), (19, 19), (10, 25), (17, 4), (27, 9), (27, 15), (26, 16), (1, 17), (9, 2), (10, 12), (7, 12), (8, 15), (25, 2), (4, 22), (5, 1), (12, 19), (16, 4), (23, 14), (12, 24), (22, 5), (6, 27), (30, 29), (27, 1), (11, 2), (16, 13), (18, 10), (27, 16), (22, 16), (10, 5), (23, 8), (27, 28), (12, 20), (14, 29), (18, 7), (8, 27), (6, 9), (2, 19), (2, 29), (2, 22), (13, 4), (3, 23), (30, 2), (10, 23), (3, 8), (26, 5), (11, 30), (29, 25), (1, 15), (4, 23), (12, 13), (25, 30), (11, 17), (16, 27), (12, 2), (26, 29), (21, 27), (23, 18), (1, 9), (24, 25), (29, 10), (30, 23), (3, 5), (14, 7), (25, 21), (10, 26), (26, 22), (28, 22), (22, 21), (13, 20), (7, 20), (29, 24), (25, 10), (26, 30), (14, 4), (4, 5), (1, 4), (11, 18), (16, 30), (27, 19), (6, 5), (25, 19), (23, 10), (1, 8), (29, 15), (21, 2), (3, 11), (24, 19), (1, 28), (1, 23), (11, 23), (19, 22), (23, 25), (1, 13), (21, 29), (8, 23), (26, 15), (25, 8), (17, 11), (5, 8), (14, 2), (21, 25), (21, 8), (29, 18), (26, 13), (11, 7), (16, 3), (23, 29), (23, 23), (5, 26), (5, 19), (2, 25), (23, 20), (14, 8), (6, 19), (15, 18), (12, 25), (11, 10), (16, 25), (20, 7), (22, 10), (23, 3), (28, 12), (5, 11), (6, 23), (25, 15), (20, 24), (27, 3), (11, 12), (4, 4), (15, 4), (22, 3), (27, 10), (8, 20), (30, 30), (13, 30), (29, 28), (11, 28), (8, 14), (8, 12), (24, 6), (29, 23), (7, 21), (15, 20), (20, 8), (15, 24), (18, 5), (2, 23), (14, 6), (16, 19), (5, 5), (16, 18), (22, 25), (29, 7), (27, 11), (21, 30), (28, 28), (19, 27), (19, 20), (18, 8), (24, 14), (4, 7), (22, 8), (24, 4), (20, 26), (1, 22), (2, 4), (14, 18), (26, 18), (14, 27), (16, 2), (10, 30), (16, 22), (4, 30), (17, 23), (15, 23), (1, 11), (28, 23), (7, 30), (6, 13), (30, 26), (7, 18), (30, 17), (28, 24), (26, 11), (7, 24), (17, 22), (13, 10), (30, 25), (6, 3), (16, 6), (13, 18), (17, 17), (15, 19), (15, 25), (6, 6), (23, 30), (15, 29), (28, 3), (15, 27), (8, 3), (11, 8), (12, 3), (18, 28), (10, 14), (25, 14), (18, 3), (5, 2), (22, 12), (22, 22), (28, 4), (14, 22), (26, 10), (3, 24), (4, 25), (28, 11), (27, 30), (22, 17), (7, 29), (29, 21), (23, 5), (3, 27), (24, 24), (12, 28), (17, 5), (6, 18), (19, 30), (2, 27), (29, 19), (19, 8), (21, 19), (18, 18), (4, 13), (9, 11), (21, 14), (7, 3), (9, 12), (7, 10), (13, 7), (28, 18), (29, 30), (30, 8), (21, 11), (20, 5), (7, 22), (29, 11), (25, 24), (20, 12), (12, 8), (26, 19), (18, 2), (6, 7), (18, 13), (16, 9), (29, 12), (18, 9), (27, 8), (10, 2), (10, 7), (27, 14), (12, 14), (3, 13), (5, 6), (13, 24), (18, 11), (11, 6), (16, 5), (28, 29), (29, 22), (19, 11), (25, 28), (15, 5), (17, 16), (24, 2), (8, 19), (17, 26), (5, 7), (21, 21), (13, 23), (25, 20), (21, 13), (1, 3), (7, 6), (5, 24), (19, 15), (4, 18), (3, 17), (4, 12), (13, 26), (3, 28), (24, 12), (26, 3), (1, 27), (10, 6), (11, 25), (19, 5), (9, 29), (7, 9), (13, 3), (11, 1), (26, 26), (9, 3), (30, 4), (21, 6), (10, 13), (10, 22), (6, 1), (22, 24), (1, 30), (10, 19), (24, 3), (2, 2), (17, 19), (20, 25), (11, 24), (9, 16), (1, 5), (29, 13), (4, 28), (11, 20), (9, 21), (28, 21), (27, 12), (9, 17), (13, 11), (23, 9), (29, 27), (24, 17), (6, 10), (17, 15), (9, 26), (29, 16), (4, 16), (22, 4), (23, 15), (26, 12), (12, 21), (6, 11), (28, 14), (7, 26), (24, 20), (18, 14), (19, 24), (25, 4), (24, 27), (18, 6), (13, 28), (4, 9), (19, 21), (24, 7), (22, 1), (25, 5), (26, 24), (9, 9), (22, 15), (25, 16), (10, 21), (6, 28), (27, 24), (11, 22), (19, 23), (16, 7), (13, 22), (14, 15), (30, 21), (30, 3), (6, 2), (10, 4), (14, 13), (6, 30), (5, 9), (29, 9), (9, 20), (29, 14), (24, 13), (16, 15), (26, 21), (12, 1), (5, 17), (3, 1), (2, 30), (23, 16), (5, 4), (14, 9), (21, 16), (7, 5), (10, 17), (22, 30), (3, 18), (23, 2), (17, 18), (3, 15), (11, 26), (12, 11), (16, 29), (2, 8)]

Solvers

• *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)