| logical thinking |
tilps
Kwon-Tom Obsessive
Puzzles: 6720
Best Total: 18m 37s | 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
Kwon-Tom Admin
Puzzles: 3614
Best Total: 24m 6s | 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
Kwon-Tom Admin
Puzzles: 3614
Best Total: 24m 6s | 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
Kwon-Tom Obsessive
Puzzles: 6720
Best Total: 18m 37s | 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
Kwon-Tom Admin
Puzzles: 3614
Best Total: 24m 6s | Posted - 2006.06.01 13:58:32
Indeed! If you come up with a good solution, let me know...  |
tilps
Kwon-Tom Obsessive
Puzzles: 6720
Best Total: 18m 37s | 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
Kwon-Tom Obsessive
Puzzles: 1293
Best Total: 20m 57s | Posted - 2006.06.01 14:35:52
Quote: Originally Posted by drnull |
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
Kwon-Tom Obsessive
Puzzles: 6720
Best Total: 18m 37s | Posted - 2006.06.01 14:43:03
Quote: Originally Posted by mathmaniac Quote: Originally Posted by drnull |
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
Kwon-Tom Obsessive
Puzzles: 1293
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
Kwon-Tom Obsessive
Puzzles: 6720
Best Total: 18m 37s | 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
Kwon-Tom Obsessive
Puzzles: 3258
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
Kwon-Tom Admin
Puzzles: 3614
Best Total: 24m 6s | Posted - 2006.06.02 15:34:15
Yes it is. |
procrastinator
Kwon-Tom 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
Kwon-Tom Obsessive
Puzzles: 3258
Best Total: 13m 42s | Posted - 2006.06.02 22:15:27
Nor mine. But then, I'm not the person you're quoting!  |
tilps
Kwon-Tom Obsessive
Puzzles: 6720
Best Total: 18m 37s | 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
Kwon-Tom 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/anit-locked edges around the four corners of an empty square.
Last edited by PuzzleLover - 2006.06.26 05:51:22 |
procrastinator
Kwon-Tom Obsessive
Puzzles: 1083
Best Total: 12m 56s | Posted - 2006.06.26 05:40:23
Quote: Originally Posted by puzzlelover |
Not possible. Maybe put another 1 next to the existing one?
But yes, you can often combine number-of-lines-into-an-area with some other piece of logic to make progress even when the area still has multiple openings. |
PuzzleLover
Kwon-Tom Obsessive
Puzzles: 1033
Best Total: 38m 17s | Posted - 2006.06.26 05:51:03
Quote: Originally Posted by procrastinator Quote: Originally Posted by puzzlelover |
Not possible. Maybe put another 1 next to the existing one? But yes, you can often combine number-of-lines-into-an-area with some other piece of logic to make progress even when the area still has multiple openings. |
|
drnull
Kwon-Tom Obsessive
Puzzles: 1053
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/anit-locked 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
Kwon-Tom Obsessive
Puzzles: 5680
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 "n2-3 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 |
