reset password
Author Message
rabbott
Posts: 1649
Posted 10:24 Nov 03, 2019 |

On Saturday, Danny Tran presented a solution to Scouts in Boats. It didn't occur to me at the time, but that is not a planning problem. (It's not a planning problem because it doesn't ask for a sequence of transitions from a start state to a final state. It is more like N-Queens in which one is asked to arrange elements in a framework in a way that obeys certain constraints. The fact that part of the framework structure is called "Days" doesn't make it a planning problem.)

Even so, it's an interesting problem. This model solves Levels 1, 2, and 4 fairly easily. (A number of redundant constraints are required to make it run in a reasonable time.) It runs forever on Level 3, neither solving it nor declaring it unsatisfiable. A discussion below the puzzle says that Level 3 is broken. But a reply says that it is now fixed. In addition, the current level 3 satisfies the criteria the original commenter says is required for there to be a solution.

I don't know why the model works so well on the other three Levels but not on Level 3. If anyone has any ideas, please post them

 

P.S. The problem has lots of symmetries: the boats can be in multiple orders on any day, and the days can be in multiple orders. Since it's possible to compare sets using '<', I tried adding constraints to block those symmetries, but they only slowed down the solver! Even something as simple as requiring Scout 'a' to be in the first boat every day slows down the solver.

 

Last edited by rabbott at 10:38 Nov 03, 2019.