title: Better algorithm for determining sequence of moves needed to reach a success state in game
body: <p>I have been playing <a href="http://g.fromgame.com/game/13/" rel="nofollow noreferrer">simple game</a> that I have been attempting to solve recently.</p>
  <p>The game is as follows:</p>
  <p>There are 81 squares of different colors on a 9x9 grid. For each square, we may consider its four neighbors in the up, down, left, or right direction. If two or more neighboring squares are the same color, you have the option to click on those squares to eliminate them.</p>
  <p>The &quot;gap&quot; left by the eliminated squares will be filled by the rule: the remaining squares shift down first if there are any vertical gaps, and then to the left if there are any horizontal gaps.</p>
  <p>A success state is when you have eliminated all 81 squares. A failure state is when there are squares remaining on the board that you cannot click (i.e. no remaining square has a neighbor of the same color). A <strong>game state</strong> will refer to any intermediate state between and including when we begin with 81 squares and proceed to either a success or failure state.</p>
  <p>My current strategy and program involve determining all possible options of a game state by running a BFS to see which squares are connected. Then, I randomly choose any valid option (we can think of options as a list of coordinates we can click on) and simulate the result until I hit a failure state or a success state.</p>
  <p>Each sequence of random choices is recorded and stored in a list. If I hit a failure state, I backtrack a random number of steps back and continue the stimulation. If there are enough failures or dead ends, I start over entirely.</p>
  <p>Here is my <a href="https://github.com/richardkyu/eliminatestars" rel="nofollow noreferrer">implementation</a> of my strategy. The program works by first configuring a picture of the starting game state from the <strong>image_grid.py file</strong>, specified in the <strong>selected_image</strong> variable (pictures are stored in the imgs folder). After selecting the desired picture, one can run the <strong>refactored_game_solution.py</strong> and the program will work to determine a sequence that leads to a successful state. For instance, for the image &quot;sample3.png&quot;, the sequence that was determined after running was:</p>
  <p><a href="https://i.stack.imgur.com/1gEn2.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/1gEn2.png" alt="enter image description here" /></a></p>
  <p>Note that the coordinate system is (-y,x). For example, (6,6) means go down 7 spaces and to the right 7 spaces and click on this square.</p>
  <p>I have been running into problems when there are more colors, such as 6 colors instead of 2 colors in that the program does not seem to finish solving ever.</p>
  <p>Thus, I am wondering if there is a better way to approach this (potentially an algorithm?) than random brute-forcing and if there is a way to determine if a beginning game state is solvable.</p>
  <p>Thanks for reading through.</p>