puzzle that just hangs with no timeout

[smack42]

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]

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]

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]

Ideas for improvements:

• somehow speed up the "solution01 mode"
• add an option to allow the user to disable "solution01 mode"
• better algorithm to eliminate duplicate solutions

[smack42]

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]

closed by release 1.3.7