Alright, I finally got a solver for my GM20 game. I did not expect it to be so tough...
So the goal of the game is to clear the board by selecting adjacent tiles that have a total of 20 points. Sometimes it is possible to end up with an unsolvable board depending on how it is played (though it is rare). I wanted a solver to detect these situations. What I did not realize, is that the game design was working against me... The problem is that, as more zeros are added, the solutions get more and more complex and the number of distinct possible paths increase exponentially. After many failed implementations, I have something that works “enough”, but as seen in the gif it often shits itself on the last turn.
Basically how it works is that I have a bunch of “explorers” that flail around semi-randomly until one finds a solution. If after a set amount of steps none of them found one, the board is considered unsolvable. The explorers are smart enough to backtrack if stuck and not take the same direction twice, so they’re good most of the times. The algorithm is also made so that it can be spread over many frames, so the game doesn’t freeze.
Anyway, I’m happy the hard part’s done