Project Euler 313 - Sliding game

Official link:

Thought Process

I recreated the game and essentially did a Breadth First Search to solve for small cases of S(m, n). Below I give my code, this was a fun problem in itself, but not very difficult.

From this some obvious patterns emerged

Essentially, we have the following:

This was not surprising as I anticipated a recursive solution since after some moves a board can essentially result in a smaller board (cutting off the useless parts which we will no longer touch).

From here, you can either notice more patterns or count solutions manually in many ways, I went the following path to get the answer. Take note of this page: to understand the first line.

Interactive Code

Enter a number (yourinput)

Code will output the number of grids such that S(m, n) = p*p where p < yourinput