search

smack42 / DriftingDroids

DriftingDroids - yet another Ricochet Robots solver program
https://github.com/smack42/DriftingDroids/wiki
GNU General Public License v3.0
41 stars 12 forks source link

puzzle that just hangs with no timeout #12

Closed smack42 closed 6 years ago

smack42 commented 6 years ago

reported via BoardGameGeek https://boardgamegeek.com/article/29708792#29708792

Hi Michael

Really enjoy using this program, thanks for making it.

After a few weeks with no issues (except the occasional timeout due to solution requiring >16 steps), I've come across a puzzle that just hangs with no timeout) per the below screenshot.

smack42 commented 6 years ago

The screenshot posted at BGG shows a custom board 8x8 with 5 robots.

This is the saved board state:

!DriftingDroids_game!ECF20C7D!AAABM3jaY2BgYOAAYVYgwQXlaAOxERAzATEDIxQw
MDJgAkYGJGFGVC6aMkY4E6YUwWdEiDAiG4aikkR7GeEOp8wBUCFTZgYIyQgAutIBMQ==!

It's a solution01 position, which means that the active robot can reach the goal in zero or one moves (in this example it's one move).

smack42 commented 6 years ago

The solver finished after 2240 seconds (almost 38 minutes!) and found some 11-move solutions, including many duplicates. This is the expected result of the "solution01 solver mode" that doesn't store any visited positions because it must be able to visit them more than once. That's why it runs very slowly and discovers some solutions several times. So this is not really a bug but just a result of the "slow solution01" special case.

smack42 commented 6 years ago

Ideas for improvements:

smack42 commented 6 years ago

I've found a way to speed up the "solution01 mode" and committed a code change. The example board given here is now solved in less than 1 second. The solver finds one solution of 11 moves. So, this issue seems to be closed, just have to do more tests...

smack42 commented 6 years ago

closed by release 1.3.7