Ricochet Robots Solver
I wrote one of these to solve the daily challenge at the now-defunct &lt;<a href="https:&#x2F;&#x2F;www.robotreboot.com&#x2F;challenge" rel="nofollow noreferrer">https:&#x2F;&#x2F;www.robotreboot.com&#x2F;challenge</a>&gt;. Four robots, no mirrors. I did not bother with an A* search or robot sorting, because each daily challenge contains five different goals searched for from the same starting board configuration. Instead I search for all of them at once with the same breadth-first search. Even without those algorithmic optimizations, it can find a 17-move solution---like the following puzzle from Nov. 25th, 2022 (the &quot;r&quot; square is the goal for the red robot)---in about 30 seconds on my laptop using less than 400 MB of memory. I&#x27;m sure it would be faster on a faster machine.<p><pre><code>    +---+-----------------+---------+
    |   |                 |         |
    |   +   +-+       +   +         |
    |         |       |             |
    |         +       +-+       +-+ |
    |                             | |
    | +                           + |
    | |                             |
    | +-+                 +         |
    |    R                |         |
    |         +-+       +-+       +-+
    |         |                     |
    +-+     + +             +-+     |
    |       |               |r      |
    |     +-+     +---+     +       |
    |             |   |             |
    |             |   |             |
    |             |   |             |
    | +-+     +-+ +---+     +-+     |
    |Y  |  G  |               |     |
    |   +     +               +   +-+
    |                               |
    +-+                             |
    |      B                        |
    |                 +-+           |
    |                 |             |
    |             +   +         +   |
    |             |             |   |
    |   +       +-+         +   +-+ |
    |   |                   |       |
    |   +-+     +         +-+   +   |
    |           |               |   |
    +-----------+---------------+---+
</code></pre>
Solving this board required examining 30,427,896 unique states.<p>One of the things I found that improved the speed the most was simply reducing the memory usage.<p>The &quot;visited states&quot; test is just a 2**32 bit (2**27 byte) table indexed by the 32-bit combined robot positions. For most problems, most of the pages in that table will never even get mapped, but at worst the whole thing is 128 MB. There are probably clever ways to permute the indices of the robot positions to get better cache coherency in the table lookups, but I did not bother.<p>The state in the breadth-first search queue is just the 32-bit combined robot positions. No back-pointers are stored to recover the solution(s). Instead, a side-table keeps track of the index in the queue where the number of moves increases (since all entries are ordered by the number of moves required to get there), and upon reaching a goal the solution is recovered by back-tracking one move at a time and searching the relevant portion of the queue for a state plus a move that gets us to the next state. This sounds slow (and it is! printing the solution now takes a non-negligible fraction of the runtime), but it is actually faster than storing back-pointers in the queue. The queue size grows exponentially with the number of moves¹, but you do not need to search for the last move in your solution, because you were just making it when you reached that goal. So you avoid having to read through a large portion of the queue just by skipping that last level, and you avoid having to <i>write</i> the extra data for the whole queue. Assuming your back pointer would have been a 32-bit queue index, that cuts the data written in half. You also don&#x27;t have to check the &quot;visited states&quot; table during back-tracking, so you avoid lots of cache pressure that was present when filling the queue the first time.<p>¹: At least for long enough to reach any single robot goal... if you search for all reachable <i>combinations</i> of robot positions, eventually you run out of unvisited states and the number of newly reachable states starts shrinking again until it hits almost nothing, at somewhere approaching 100 moves. For a given board, roughly 2&#x2F;3rds of the 3,937,437,000 possible combinations of robot positions are reachable, giving a maximum memory usage of about 10 GB.