Ponder This Challenge - June 2025 - Jumping frog game

This puzzle was suggested by Gyozo Nagy - thanks!

We play the following game on an $N\times N$ board: We control a frog that starts somewhere on the board. The cells of the board can be either white ("empty"), blue ("visited"), or red ("forbidden"). At the beginning of the game, the whole board is white except for a blue cell where the frog starts. On each step of the game, the frog moves to one of the eight adjacent cells. We denote the possible moves with the letters A, B,...,H clockwise around the current cell, such that A is a move to the cell directly to the right, B is a move to the cell below and to the right, and so on around the current location of the frog. To move to a cell, the following conditions must apply:

1. The cell must be white.
2. The next cell in the same direction (if it exists) can be red or white but not blue. If no cell exists in the same direction, this constraint can be ignored.

After the move is performed, the cell now containing the frog turns from white to blue.
In addition, the next cell in the same direction (the one that could not be blue), if it exists, becomes red (or remains red if it was already that color).

The goal of the game is to reach a state where only non-white cells remain on the board (the number of red or blue cells does not matter).

For example, in a 4x4 board starting from (0,0) (the top-left corner), performing the sequence of moves "ABHCDBEFDGH" results in a fully colored board with 4 red cells.

Your goal: Solve the game for a 20x20 board starting from (0,0). Give your solution as a string of letters as shown above.

A bonus "*" will be given for solving the game for a 10x10 board starting from (4,4).

Solution

• Click here to view the solution

  June 2025 Solution:

  Solutions, in string form:

  Main challange:
  
  
  CHCHCHCHCHCHCHCHCHCHCHCHCHCHCHCHCHCHBGDBEBEBEBEBEBEBEBEBEBEBEBEBEBEBEBEBDAFDGDGDGDGDGDGDGDGDG   
  
  DGDGDGDGDGDGDGDFCHFAFAFAFAFAFAFAFAFAFAFAFAFAFHEBHCHCHCHCHCHCHCHCHCHCHCHCHCHBGDBEBEBEBEBEBEBEB   
  
  EBEBEBDAFDGDGDGDGDGDGDGDGDGDGDFCHFAFAFAFAFAFAFAFHEBHCHCHCHCHCHCHCHBGDBEBEBEBEBDAFDGDGDGDGDFCH   
  
  FAFGBGBGBGBG
  
  
  
  
  Bonus:
  
  ADADADADCHCHCHCAGAGFEHAFEHAFHGDGEDCFGDFCBDADCDCDBEFGHGEGHFGBGHC
  

  The main challenge can be tricky to solve via search algorithms due to the sheer board size; however, if one tries to play the game manually, it is relatively easy to notice and exploit some simple patterns that can effectively handle any board. The 10x10 case is more tricky due to the starting point in the middle, but in this case the board size allows relatively easy computer search.

  For those who wish to play the game themselves, an html implementation can be found [here]
  The solutions, in image form:

Solvers

• *Bertram Felgenhauer (29/5/2025 5:45 PM IDT)
• *Lazar Ilic (29/5/2025 8:07 PM IDT)
• *John Tromp (30/5/2025 12:58 AM IDT)
• *King Pig (30/5/2025 3:44 AM IDT)
• *Sanandan Swaminathan (30/5/2025 12:09 PM IDT)
• *Alper Halbutogullari (30/5/2025 3:02 PM IDT)
• *Jordan Payette (30/5/2025 3:52 PM IDT)
• *Bert Dobbelaere (30/5/2025 4:04 PM IDT)
• *Shirish Chinchalkar (30/5/2025 10:29 PM IDT)
• *Ankit Aggarwal (31/5/2025 1:43 AM IDT)
• *Griffin Pinney (31/5/2025 5:07 AM IDT)
• *Stephen Ebert (31/5/2025 5:50 AM IDT)
• *Loukas Sidiropoulos (31/5/2025 6:17 PM IDT)
• *Gary M. Gerken (31/5/2025 6:26 PM IDT)
• *Resnina (Kulshaeva) Tathyana (31/5/2025 8:21 PM IDT)
• *Motty Porat (31/5/2025 8:36 PM IDT)
• *Gyozo Nagy (1/6/2025 12:03 AM IDT)
• *Sri Mallikarjun J (1/6/2025 9:45 AM IDT)
• *Yi Jiang (1/6/2025 11:42 AM IDT)
• *Harald Bögeholz (1/6/2025 2:14 PM IDT)
• *Juergen Koehl (1/6/2025 8:01 PM IDT)
• *Klaus Nagel (1/6/2025 10:29 PM IDT)
• *Latchezar Christov (1/6/2025 11:53 PM IDT)
• *Lorenz Reichel (2/6/2025 2:26 PM IDT)
• *Jiri Spitalsky (2/6/2025 4:12 PM IDT)
• *Paul Revenant (3/6/2025 12:59 AM IDT)
• *Daniel Bitin (3/6/2025 3:59 PM IDT)
• *Martin Thorne (3/6/2025 7:10 PM IDT)
• *Vladimir Volevich (4/6/2025 12:53 PM IDT)
• *Fakih Karademir (4/6/2025 10:14 PM IDT)
• *Kevin Bauer (5/6/2025 12:37 AM IDT)
• Dan Ismailescu (5/6/2025 10:37 PM IDT)
• *Dominik Reichl (6/6/2025 12:52 PM IDT)
• *Nadir S. (6/6/2025 10:24 PM IDT)
• *Hakan Summakoğlu (7/6/2025 5:54 PM IDT)
• *Erik Hostens (8/6/2025 9:42 AM IDT)
• *Sean Kuwamoto (8/6/2025 9:47 AM IDT)
• *Camden Chappelle (9/6/2025 3:57 AM IDT)
• *Marcel Caria (9/6/2025 2:00 PM IDT)
• Mithil Ramteke (9/6/2025 7:15 PM IDT)
• *Mark Mammel (10/6/2025 3:14 AM IDT)
• Fabio Michele Negroni (10/6/2025 5:09 PM IDT)
• *Yash Kumar Kasaudhan (12/6/2025 9:21 AM IDT)
• Ansh Kasaudhan (12/6/2025 9:26 AM IDT)
• *Kang Jin Cho (12/6/2025 10:58 AM IDT)
• *Ankit Chakraborty (12/6/2025 3:23 PM IDT)
• *Paul Lupascu (13/6/2025 7:41 AM IDT)
• *Franciraldo Cavalcante (14/6/2025 2:21 AM IDT)
• *Peter Moser (14/6/2025 11:19 AM IDT)
• *David F.H. Dunkley (15/6/2025 2:20 AM IDT)
• *Dieter Beckerle (15/6/2025 11:51 AM IDT)
• *Nischal Agrawal (16/6/2025 9:26 AM IDT)
• *Prakhar Kapoor (16/6/2025 3:05 PM IDT)
• *Justin Snopek (16/6/2025 6:24 PM IDT)
• *Gábor Zavarkó (17/6/2025 3:18 PM IDT)
• *Nyles Heise (20/6/2025 5:40 AM IDT)
• *Nicholas Patel (21/6/2025 8:49 AM IDT)
• *Evert van Dijken (23/6/2025 9:39 AM IDT)
• *Daniel Chong Jyh Tar (23/6/2025 7:32 PM IDT)
• *Frank Schoeps (23/6/2025 9:40 PM IDT)
• *Keith S (24/6/2025 4:52 AM IDT)
• Christoph Baumgarten (24/6/2025 7:34 AM IDT)
• *Micheal Malki (24/6/2025 3:03 PM IDT)
• Dan Dima (26/6/2025 6:48 PM IDT)
• *Zoltan Haindrich (26/6/2025 7:00 PM IDT)
• *Christopher Bender (26/6/2025 11:03 PM IDT)
• *Marco Bellocchi (27/6/2025 1:25 AM IDT)
• Stefan Wirth (27/6/2025 5:22 AM IDT)
• *Alexander Martin (28/6/2025 10:19 AM IDT)
• Reiner Martin (28/6/2025 11:48 AM IDT)
• *Karl Mahlburg (29/6/2025 4:46 AM IDT)
• *David Greer (29/6/2025 12:23 PM IDT)
• Robin Guilliou (30/6/2025 6:10 PM IDT)
• *Evan Semet (1/7/2025 2:26 AM IDT)
• Jason Bono (2/7/2025 2:44 AM IDT)
• Reda Kebbaj (2/7/2025 2:54 AM IDT)
• *Stéphane Higueret (3/7/2025 1:25 PM IDT)
• *Li Li (4/7/2025 11:07 AM IDT)
• *Jackson La Vallee (4/7/2025 11:48 PM IDT)
• Radu-Alexandru Todor (5/7/2025 5:41 AM IDT)
• *Govind Jujare (7/7/2025 11:30 AM IDT)