Solving Slitherlink puzzles

[Jim Bumgardner]

I'm curious if anyone has tried solving Slitherlink puzzles (or puzzles in the same family, such as Masyu) using or-tools?  Is it even possible, using the current implementation?

[Laurent Perron]

It should be.

You have the NoCycle constraint to express the unique path.

You can model using an array of Next() variables, with the convention that next(i) == i means node i is not active.

You need to link that to a counting model per node.

I hope this helps.

--Laurent

Le mar. 29 déc. 2015 à 00:02, Jim Bumgardner <jim.bum...@gmail.com> a écrit :

I'm curious if anyone has tried solving Slitherlink puzzles (or puzzles in the same family, such as Masyu) using or-tools?  Is it even possible, using the current implementation?

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Laurent Perron]

I have coded an initial version that does not enforce the hamiltonian path constraint, just the degree 0 or 2 per node.

I have tested it on 2 problems:

  first one: it produces 2 solutions, one that violates the path constraint, and the correct one.

  second one: it produces one valid solution of the problem.

The code is in examples/cpp/slitherlink.cc

I will look at the hamiltonian path constraint tomorrow.

Thanks

[Laurent Perron]

Hi

A complete version is here:

  https://github.com/google/or-tools/blob/master/examples/cpp/slitherlink.cc

I have one more rule to encode (around corners).

Thanks

[Jim Bumgardner]

Thank you so much for the Slitherlink example!  Feel free to grab sample puzzles if you need them from my website (krazydad.com/tablet).  I also produce a few Slitherlink variants, including Masyu, Cow & Cactus.   I will attempt to solve those using your example as a starter.

[Jim Bumgardner]

Am I correct in thinking that the extra logic you added for corners is a heuristic to speed solving, but not strictly necessary to find a solution?

Jim

[Laurent Perron]

Indeed, same as the odd sum for all columns, rows.

--Laurent

Le mer. 30 déc. 2015 à 18:32, Jim Bumgardner <jim.bum...@gmail.com> a écrit :

Am I correct in thinking that the extra logic you added for corners is a heuristic to speed solving, but not strictly necessary to find a solution?

Jim

--

[Laurent Perron]

And it is a redundant constraint. It does not remove solutions.

'Heuristics' is overloaded and could mean we could remove some solutions.

--Laurent

[Jim Bumgardner]

I'm attempting to port the C++ code to Python for readability.  Have all working but the Hamiltonian path.  

Is it possible to implement the constraint callback used for single-loop detection in Python?  I haven't found any Python examples that pass callback functions to the solver.

[Laurent Perron]

Hi, 

I pushed the full slitherlink code in python in examples/python/slitherlink,py

It contains 2 constraints written in python.

You need the latest code from github to make it run, I had to fix a few issues :-(

--Laurent

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

2015-12-31 20:04 GMT+01:00 Jim Bumgardner <jim.bum...@gmail.com>:

I'm attempting to port the C++ code to Python for readability.  Have all working but the Hamiltonian path.  

Is it possible to implement the constraint callback used for single-loop detection in Python?  I haven't found any Python examples that pass callback functions to the solver.

[Jim Bumgardner]

Thank you so much!  I'm glad this problem was the catalyst for a bug fix.

In my own implementation, I implemented the Jordan Curve constraint (for which you wrote the BooleanEvenSum class) this way, using solver.Sum:

  for y in range(height):
    row = [h_arcs[x][y] for x in xrange(width+1)]
    solver.Add( solver.Sum(row) % 2 == 0 )
  for x in range(width):
    column = [v_arcs[y][x] for y in xrange(height+1)]
    solver.Add( solver.Sum(column) % 2 == 0 )

However, I noticed that it actually worsened performance to include it.  Does implementing it as a PyConstraint class significantly improve performance?