| Intersection colors | Tilps
Kwon-Tom Obsessive
Puzzles: 6504
Best Total: 20m 22s | Posted - 2009.11.25 04:36:37
I was thinking about the following pattern and trying to work out how to write a generalized set of logic which covers it
I came up with an idea, but I'm having difficulty convincing myself that it is actually generally useful, as opposed to only useful for this scenario.
In this example, the color of the intersection at 2,2 is equal to the color of the of the square 1,1. The color of the intersection at 5,2 is the same as the color at square 5,2. The color of the intersection at 2,5 is undefined, and the color of the intersection at 5,5 is the same as all of its surrounding squares.
Once defined we can see that they get propagated by chains of locked 2's (inverting color once for each 2).
So in this example we have found a contradiction because the intersection colors at each end are defined to be opposite by 2 propagation, but the intersections at each end are also defined to both be the outside color.
In this puzzle we can prove the bottom of the 1 must be true, because 0's have the same color for each intersection, and so the outside color flows from the bottom right up to the 0 and down to the 1, where the two crosses give us a cell color.
In this scenario a trial of the top of the 1 in the middle would fail.
But all in all, I'm not yet convinced that its utility is very great.
Thoughts? | Differ
Kwon-Tom Fan
Puzzles: 35 | Posted - 2009.11.25 08:25:26
I'm working on a color-based solver; if you want I can give you my docs (which are currently incomplete).
Anything you can do with lines, you can do with less complexity using colors. If you're feeling especially masochistic, you can use colors to mimic the functionality of lines, although I would not recommend it. There's no point using a generalized algorithm to represent a specialized one.
Major strengths of colors are the ability to represent arbitrary interactions between arbitrary sets of squares, the easy data structures, prevention of redoing work that is already done, no-cost extension of lookahead length during runtime, and the excellent heuristics in choosing where to look ahead. I think your solver goes down the grid and across, looking for stuff to do, which is not very efficient at all.
Minor strengths are the immediate resolving of trivial problems (i.e. a line goes into an intersection with 2 crosses, what happens), easier threading (maybe), and guarantee of a closed loop(s).
I have found two weaknesses. The first is the requirement for a special case when colors alternate around an intersection, which is represented in lines by the restriction of 2 lines max per intersection. An example is http://upload.wikimedia.org/wikipedia/en/d/da/Slitherlink-line2.png which is not easily resolved. The second is the simple case of 2 adjacent 3's, which involves no self-enclosed islands of colors. Both are only resolved in the second to last step of my current algorithm unless special cases are used.
Currently I'm trying to figure out how to resolve the deadlocks on simultaneous read/write on structures. I'll probably procrastinate and eventually leave multithreading out entirely.
Also colors look nicer, especially when you have multiple colors. That should be a factor too. =) |
|
