logical thinking 
tilps KwonTom Obsessive Puzzles: 4293 Best Total: 20m 22s  Posted  2006.06.01 09:01:18 I forgot to mention that one, I was basing my answer too much off my computer program ... (which doesn't include everything I mentioned, yet) Dividing the mesh into areas with one exit and entry is kind of tricky in code compared to other operations. 
foilman KwonTom Admin Puzzles: 1720 Best Total: 24m 8s  Posted  2006.06.01 09:08:48 Very true... and that's one reason why sometimes puzzles here are classified as very hard when they're not... it's because my puzzle creator is not so good at spotting areas with limited exits. 
foilman KwonTom Admin Puzzles: 1720 Best Total: 24m 8s  Posted  2006.06.01 13:43:39 Actually, after looking through my code again, I've realised it does handle most cases of areas with an odd number of lines going into them.
It's actually quite a simple check  in simple terms it does something like this; pick an edge, put a cross in it, then trace all points accessible from one end and count the number of "line ends" encountered; if the result is odd, the edge should have a line in it. Similarly, if a line is tried and the result is an odd count, the edge should have a cross in it. Obviously there are a few enhancements (like not blindly trying every available edge!) but that's basically how it spots such enclosed areas.
Last edited by foilman  2006.06.01 13:46:18 
tilps KwonTom Obsessive Puzzles: 4293 Best Total: 20m 22s  Posted  2006.06.01 13:54:17 I think I was thinking of the more generalized issue shown here...
This is not a really good example, but I feel a larger example could be constructed, where the existance of a number inside an area proves the need for entrance and exit, but the search for odd number of line ends doesn't help.
Last edited by tilps  2006.06.01 13:58:10 
foilman KwonTom Admin Puzzles: 1720 Best Total: 24m 8s  Posted  2006.06.01 13:58:32 Indeed! If you come up with a good solution, let me know... 
tilps KwonTom Obsessive Puzzles: 4293 Best Total: 20m 22s  Posted  2006.06.01 14:15:09 Iterate all intersections  identify 'chokepoints'  block all chokepoints and 'floodfill' with different colors until entire mesh is covered  then check number of line ends in each colored area, and number of chokepoints touching  and ... do the right thing.
<rant for no good reason> Unfortunately for me, any algorithm which iterates over all intersections or edges or cells is too expensive to really consider applying after each forced move in a lookahead branch. I already have one of them which only triggers on some forced moves, for checking whether the loop has been closed prematurely, which I really need to optimise since it causes an obvious performance hit when I turn it on. The most obvious optimisation however, requires snapshotting of some of the mesh state before performing trial lookaheads, because it makes unperforming the trial lookaheads infeasible. Although... it looks like I will need to do the same for implementing my colouring solver anyway. </rant> 
mathmaniac KwonTom Obsessive Puzzles: 1198 Best Total: 20m 57s  Posted  2006.06.01 14:35:52
Quote: Originally Posted by drnull 4 x's: 
I just happened to be going and looking back at these puzzles and I noticed that this one needed 2 more x's and 2 lines.
Last edited by mathmaniac  2006.06.01 14:38:23 
tilps KwonTom Obsessive Puzzles: 4293 Best Total: 20m 22s  Posted  2006.06.01 14:43:03
Quote: Originally Posted by mathmaniac Quote: Originally Posted by drnull 4 x's: 
I just happened to be going and looking back at these puzzles and I noticed that this one needed 2 more x's and 2 lines. 
hrmm, I'm not seeing it  definitely only 4 x's for me. 4 options for 3, 2 of which are 6x and 2 line in common, but the other 2 only have 4x in common with the first two. 
mathmaniac KwonTom Obsessive Puzzles: 1198 Best Total: 20m 57s  Posted  2006.06.01 14:53:38 my bad! I was looking at it the wrong way! I had the x's here. thanks for righting me! 
tilps KwonTom Obsessive Puzzles: 4293 Best Total: 20m 22s  Posted  2006.06.02 14:33:09 Another piece of logic I use which I forgot to mention. (not coded in my program)  its also pretty obvious.
In this example, you know the end point near the one can't join to the end point near the two, because it traps an end point on its own. You don't have to consider every possible path, you can just 'draw the shortest path' and know it. By knowing which end point joins to another, you can sometimes rule out a stack of cases in your consideration. (or at least give you a better idea of where to look when you are stuck. 
astrokath KwonTom Obsessive Puzzles: 3093 Best Total: 13m 42s  Posted  2006.06.02 14:58:45 Isn't that just the same as the "conserving an even number of ends in a given region" rule? 
foilman KwonTom Admin Puzzles: 1720 Best Total: 24m 8s  Posted  2006.06.02 15:34:15 Yes it is. 
procrastinator KwonTom Obsessive Puzzles: 1083 Best Total: 12m 56s  Posted  2006.06.02 19:30:19
Quote: Originally Posted by tilps In this example, you know the end point near the one can't join to the end point near the two 
OK astrokath, that's something I do completely intuitively. The thought of things connecting the other way would never cross my conscious mind. 
astrokath KwonTom Obsessive Puzzles: 3093 Best Total: 13m 42s  Posted  2006.06.02 22:15:27 Nor mine. But then, I'm not the person you're quoting! 
tilps KwonTom Obsessive Puzzles: 4293 Best Total: 20m 22s  Posted  2006.06.03 05:26:33
Quote: Originally Posted by astrokath Isn't that just the same as the "conserving an even number of ends in a given region" rule? 
Yep, but I think of it seperately 
PuzzleLover KwonTom Obsessive Puzzles: 1033 Best Total: 38m 17s  Posted  2006.06.26 03:21:07 2 more x's:
There are probably a few more patterns derived from locked/anitlocked edges around the four corners of an empty square.
Last edited by PuzzleLover  2006.06.26 05:51:22 
procrastinator KwonTom Obsessive Puzzles: 1083 Best Total: 12m 56s  Posted  2006.06.26 05:40:23
Quote: Originally Posted by puzzlelover 2 more x's:

Not possible. Maybe put another 1 next to the existing one?
But yes, you can often combine numberoflinesintoanarea with some other piece of logic to make progress even when the area still has multiple openings. 
PuzzleLover KwonTom Obsessive Puzzles: 1033 Best Total: 38m 17s  Posted  2006.06.26 05:51:03
Quote: Originally Posted by procrastinator Quote: Originally Posted by puzzlelover 2 more x's:

Not possible. Maybe put another 1 next to the existing one? But yes, you can often combine numberoflinesintoanarea with some other piece of logic to make progress even when the area still has multiple openings. 
I added the extra 1 you noted, which the actual puzzle had. Guess I overabstracted. I assume you say impossible based on Highlander. 
drnull KwonTom Obsessive Puzzles: 901 Best Total: 23m 25s  Posted  2006.06.26 13:53:11
Quote: Originally Posted by puzzlelover 2 more x's:
There are probably a few more patterns derived from locked/anitlocked edges around the four corners of an empty square. 
The way I think about these is just an extension to the "drawing a line through the puzzle rule". We know that if you draw a line from one side to another, there has to be an even number of loop lines that cross that dividing line. However, it's also true that if you draw a circle (well, a connected circle inside the puzzle), then there have to be an even number of loop lines that cross that circle line. That's kinda hard to explain, but if you count what you have in this puzzle, (the count goes through all the lines and x's and ?'s) then you find that you have an even number of lines already. So you could add 2 more lines, or you could add no lines. Since the two ?'s are around the 1, then you can't add 2 lines. So they're both x's.
Oh yeah, and if the circle goes around any loop lines, then there better be some loop lines going out of that circle as well. 
Jankonyex KwonTom Obsessive Puzzles: 3787 Best Total: 9m 35s  Posted  2006.07.16 16:43:12 a = "1" can be chanded into one "2" + one "line" b = "3" can be changed into one "2" + one "cross" c = "3" can be changed into one "line" d = "3" can be extended to form "n23 diagonally"(n>0) and the new "3" with both b[2],c[2] [m] = "m possibilities", note that some of the combinations may lack some features compare with the original, of course some of them may also have another new thing(s) be deduced affected by the rest(s) or assumption(s) from the original.
2 x's: (this is 33 with b[1])
1 line, 2 x's: (with a[1])
2 lines: (with a[2],b[2],c[2],d)
1 line, 1 x: (with a[2],b[1])
1 line, 2 x's: (with a[2],b[2],c[2],d)
1 line, 1 x: (with a[2],b[1])
2 lines: (with a[1],b[2],c[2],d) "a" is not [2] because the other one make the effect directly.
1 x: (with a[4],b[1]) (an extension of my 4th or 6th pattern here.{by changing "cross" into "1"})
4 x's: (with a[4]b[2]c[2],d) (an extension of my 5th pattern here.{by changing "cross" into "1"})
2 lines: (with a[2]b[2]c[2],d) (an extension of my 3rd and 7th pattern here.{by changing "cross" into "1"})
1 line, 4x's: (with a[4])
1 x: (with a[4],"2" can also be changed into "1" + one "cross") (an extension of the above pattern.{by changing two "crosses" into one "1", that's why the "2" can be changed into "1" + one "cross" also})
2 lines, 1 x: (with b[1])
2 lines, 2 x's: (with b[2]) (an extension of the above pattern.)
by mathematical and logical method, in situation:
¡Ï¡@¡Ï¡@¡Ï ¡@¡@¡@¢²¢Ñ ¡Ï¡@¡Ï¡@¡Ï¢Ò¡Ï ¡@¢±¡@¢± ¡Ï¢Ï¡Ï¡@¡Ï ¡@¡@¢Ð ¡@¡@¡Ï
we have A+B+C+D=2 (lines or crosses) [ you can prove it if you like to ]
2 lines: (with b[2],d)
1 line, 2 x's: (with a[2],b[1],d) (an extension of the above pattern.)
1 line, 2 x's: (with a[1],b[2],d) (similar to the above pattern)
4 x's: (with a[3],b[1],d) (similar to the above pattern)
2 lines: (with b[1])
2 lines, 2 x's: (with a[2],b[4],c[2]) (extension of 3>1v1>3 pattern)
Last edited by Jankonyex  2006.12.13 09:30:20 