Writing a CP-SAT solver for diagonal slitherlink puzzles

[Neil Aggarwal]

Hello everyone:

I found some references on using CP-SAT to write a solver for sudoku
puzzles. That seems very interesting.

So, I am thinking of writing a solver for my diagonal slitherlink puzzles
to see if it is more elegant than the current solver I wrote.

If you are unfamiliar with this type of puzzle, I am attaching a sample
puzzle.

So far, I am thinking of modeling it this way:
Each potential line will be represented by an integer which may have a
value of 0 (not connected) or 1 (connected).
For each intersection, I will put a constraint that the sum of the values
of the lines which meet there is either 0 or 2.
For each box with a given, I will put a constraint that the sum of the
values
of the lines which belong to the box add up to the given value.

I don't see how to write a constraint to enforce the requirement of a
single loop.

Any thoughts? Is there a better way to model it?

Thank you,
Neil

--
Neil Aggarwal, (972) 834-1565, http://www.propfinancing.com
We offer 30 year loans on single family houses!

[Laurent Perron]

https://github.com/google/or-tools/blob/stable/examples/cpp/slitherlink_sat.cc ?

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

--
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.
To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/f1ffbfc631eddc5461fc11a65ffe7987%40mail.gmail.com.

[Neil Aggarwal]

> https://github.com/google/or-tools/blob/stable/examples/cpp/slitherlink_sat.cc ?

 

I did not realize there was an example.  Thanks for the link.

 

That code is pretty cryptic.  It is going to take me a while to unpack it.

[Neil Aggarwal]

I tried to follow the example and some resources on the web.

I wrote a simple class to solve a slitherlink, see attached.

 

I am not getting any solutions and the solver status says infeasible.

 

I must be misunderstanding how the circuit constraint works.

 

Anyone have any guidance?  I appreciate your help.

[Neil Aggarwal]

I realized I was not supposed to put not() on the loops so I removed
that, but it is still giving me infeasible.  I am attaching my updated

class.

 

I am not sure what to do now.