Tuesday, 8th October 2024
Puzzles Solved Yesterday: 120
Forum Index
 
10x10 - 1s and 2s
Slithy
Kwon-Tom Addict
Puzzles: 381
Best Total: 2h 56m 10s
Posted - 2022.01.06 23:18:37
> My SAT solver assures me the solution is unique but I cannot make any meaningful progress.
> Solvers:  9

Wow.

Any comments on what magic was involved, and how long the incantation took?
Darklady
Kwon-Tom Obsessive
Puzzles: 5369
Best Total: 9m 37s
Posted - 2022.01.07 06:22:04
My time was 9:26. I don't remember precisely what sequence I did, but it was something like this:



This was as far as I could get easily, and it involved a highlander deduction (green) and a slightly non-obvious lookahead (blue). From there, the 2 I circled in orange stood out, because if you put an X below its lower-right corner it becomes another potential location for highlander deductions.

(In general, highlander deductionsー"there can be only one [solution]", therefore any path that would produce multiple solutions must be wrongーare very powerful when dealing with difficult puzzles. They require knowing that there is in fact a unique solution, of course.)





Two explorations starting from the points circled in blue both quickly lead to dead ends. The second created a new potential highlander location over on the left edge of the puzzle, so I started focusing there:



Again, potential highlander circled in orange, starting point of explorations circled in blue.



This one didn't turn out to be a great spot to start an exploration, but enough of the puzzle had been solved that it went pretty quickly.





And done.

Thanks for the puzzle, it was fun!
Slithy
Kwon-Tom Addict
Puzzles: 381
Best Total: 2h 56m 10s
Posted - 2022.01.09 10:15:03
Quote:
Originally Posted by Darklady
... something like this...

Thank you for your many pointers.  So far I have only 11 of the crosses on your first board, so still some way to go

Also glad you enjoyed it.  I intend to produce more, but while generation only take a second or so, testing them takes much longer and their quality and difficulty seem quite unpredictable.
foilman
Kwon-Tom Admin
Puzzles: 3567
Best Total: 24m 6s
Posted - 2022.01.18 12:44:17
I've just solved your other hard 1s & 2s puzzle - #544 - that was a big challenge!
Slithy
Kwon-Tom Addict
Puzzles: 381
Best Total: 2h 56m 10s
Posted - 2022.01.18 14:17:52
I'm glad to hear someone else finds them difficult as they are frankly too hard for me.  Even with DarkLady's pointers the first took me a couple of hours and I've only managed one of the others.  Below I attach a beast (go on, I'll be right behind you and if anyone is interested I can now easily upload more of the smaller ones.

My approach so far has been based on trying to spread information as evenly and diffusely as possible, leading to the predominance on 1s and 2s.  As it doesn't look interesting to head any further in that direction I'm going to try to introduce some structure or lumpiness in a way that will make them more approachable and hopefully more interesting.

40x30:2b1a2b2a211b1a2d2a22e1a2c112a2a2a1121b2a2a2a2a1e22112a211c2b
1b01d2c11a21a221a221a22a1b1a11a1b1g122a1a212b1d1a2b1b11b1211222a2
222a2f12a11a12a221a12a1c1e2a1a22b21a2a1a2a1222a1211e2a22a22a1b2b2
b1211b1122d2a2121a2f211a11a2a212d11b2112112a21b21a12a122d2b12a22a1
212a2a21i11222a1221g2a1b2a2c2a221d2b2a221b21a112222b2a11b1b22a1a2b
1a2112a122d1a22a2a221a22a2d1a11c2a1b2a1a1a2a1b12a211a2c21a22b2c21a
2a1a21a12b12121111d2a2a1c1a22c2b22a22b1b1a1c2c22a12b22c122b121a212
e112a1b121b21a1d1a2a12a2a2c2112a2111a12a11121e2b2a2122b2122b212f1b
222b11222a2b2f22a2b2a1b2a12a11e2b1b2221222c21a2b121a21a2b111a12111
2b2b2c1122a21d2a22b1a222b2a2b121212a12a22222d11c1c211c12a12g11a1c1
1a2221c1a212a1b1c2b222a2b22111a111a22a2a11212a2a22b1a1211b2211b1a2
a11a12a12a22b2c1c11b1b221222a2a12c2b112b21a11221a2b212b212c12a12a2
a222c221c21a212122c121a1a121d12b111a1122b12b2a212221b1222b22a2d1a2
2a22b12c2b222b2b1d2a2c1111a11a1b1c1111b2b1a12b1b111a1a1a222d212a22a
2c11a232b


2  1 2  2 211  1 2    2 22     1 2   112
2 2 1121  2 2 2 2 1     22112 211   2 
1  01    2   11 21 221 221 22 1  1 11 1
1       122 1 212  1    1 2  1  11  121
1222 2222 2      12 11 12 221 12 1   1 
   2 1 22  21 2 1 2 1222 1211     2 22 2
2 1  2  2  1211  1122    2 2121 2      2
11 11 2 212    11  2112112 21  21 12 122
    2  12 22 1212 2 21         11222 122
1       2 1  2 2   2 221    2  2 221  21
112222  2 11  1  22 1 2  1 2112 122   
1 22 2 221 22 2    1 11   2 1  2 1 1 2 1
  12 211 2   21 22  2   21 2 1 21 12  12
121111    2 2 1   1 22   2  22 22  1  1
1   2   22 12  22   122  121 212     112
1  121  21 1    1 2 12 2 2   2112 2111
12 11121     2  2 2122  2122  212      1
  222  11222 2  2      22 2  2 1  2 12 1
1     2  1  2221222   21 2  121 21 2  11
1 121112  2  2   1122 21    2 22  1 222
2 2  121212 12 22222    11   1   211   
12 12       11 1   11 2221   1 212 1  1
  2  222 2  22111 111 22 2 11212 2 22  1
1211  2211  1 2 11 12 12 22  2   1   11
  1  221222 2 12   2  112  21 11221 2  2
12  212   12 12 2 222   221   21 212122
  121 1 121    12  111 1122  12  2 21222
1  1222  22 2    1 22 22  12   2  222  2
  1    2 2   1111 11 1  1   1111  2  1 1
Last edited by Slithy - 2022.11.18 08:24:37
Slithy
Kwon-Tom Addict
Puzzles: 381
Best Total: 2h 56m 10s
Posted - 2022.11.14 21:46:48
This is a 10x10 puzzle and solution.

This is the cloud of near-solutions that satisfy all the clues but contain multiple loops that are all longer than 6.

Rather pretty, I think, and perhaps a useful diagnostic
MondSemmel
Kwon-Tom Obsessive
Puzzles: 6159
Best Total: 7m 47s
Posted - 2022.11.15 10:33:58
Quote:
Originally Posted by Slithy
This is the cloud of near-solutions that satisfy all the clues but contain multiple loops that are all longer than 6.

Rather pretty, I think, and perhaps a useful diagnostic

Pretty indeed! Is there a way for you to display the cloud such that the parts of the loop that are always the same (like the section in the top right) are just a single thin or thick line in a different color, vs. the parts of the cloud that differ between solutions?

Or another way to make the image clearer would be to color all cells (incl. number clues) which have unique line solutions, in a different color from all cells which have multiple line solutions.

I'm thinking that there's indeed something to learn from this depiction, but the current image is too busy for me to parse properly.
Slithy
Kwon-Tom Addict
Puzzles: 381
Best Total: 2h 56m 10s
Posted - 2022.11.16 15:00:49
More work is definitely needed as it hasn't proved as useful as I hoped.  Colouring helps a little; in this one the scale runs from blue are for solutions that contain the shortest loops and yellow the longest (here actually the true solution).

https://photos.app.goo.gl/PX195Cxx1xWLiWN46

There is a further small gain from just showing a smaller cloud, here I've deleted near-solutions in which any loop is under 30 long, which makes the complexity a little more digestible.

https://photos.app.goo.gl/qc1xvMBC5SPMZatN8

... and in the best cases that is enough to make the structure very clear.

https://photos.app.goo.gl/TFYwannD3HPbE6x3A

There are a couple of more problems, though, the most fundamental being that I'm really not certain on interpretation.  I've just published Hard9, which I chose from my last batch because it has substantial lengths on which the cloud is unanimous and the cloud has only one member with a minimum loop length over 40.  Both suggested to me that it would be relatively easy... and maybe I am missing something, but even with this map sitting in front of me to tell me where to look for contradictions it does not seem any easier that I can tell!

So I am going to try to pin down what if anything that cloud is saying, probably by looking at the entropy of each edge.  If entropy does prove a useful summary it suggests a plot with just a single line coloured by entropy (or possibly the proportion of the cloud that contain that edge) but as yet this is speculation...
MondSemmel
Kwon-Tom Obsessive
Puzzles: 6159
Best Total: 7m 47s
Posted - 2022.11.17 10:07:31
> So I am going to try to pin down what if anything that cloud is saying

Here's my interpretation:

The sections where all cloud solutions agree are those parts of the solution that are unique even if we drop the Slither Link rule that there must only be one loop.

Any solution that would be valid if we allowed multiple loops often involve "action at a distance" and in harder puzzles require knowledge of other regions of the puzzle to solve. These sections of the puzzle can/should only be solved once as many unique sections of the solution have been identified as possible.

Does that make sense?

EDIT: By the way, this thread would be easier to read if you added lots of line breaks to the "40x30:2b1a2b2a211b1a2d..." puzzle beast code in one of your earlier comments.
Last edited by MondSemmel - 2022.11.17 10:10:41
Slithy
Kwon-Tom Addict
Puzzles: 381
Best Total: 2h 56m 10s
Posted - 2022.11.18 08:53:27
Quote:
Originally Posted by MondSemmel
this thread would be easier to read if you added lots of line breaks to the "40x30:2b1a2b2a211b1a2d..." puzzle beast code

Much better

Quote:
Originally Posted by MondSemmel
The sections where all cloud solutions agree are those parts of the solution that are unique even if we drop the Slither Link rule that there must only be one loop.  ...  "action at a distance"

I agree, and I was seeking large clouds with the idea that this would make action at a distance more important, and with substantial minimum loop lengths with the idea that that distance should be substantial.  I still tend to think both ideas have some value, but as puzzles are already highly selected it may be that diminishing returns have set in and more is no longer noticeably better?  Or the entropy concept might be more important, because the size of the cloud matters less than how evenly it covers the board?
Last edited by Slithy - 2022.11.18 08:56:16
Slithy
Kwon-Tom Addict
Puzzles: 381
Best Total: 2h 56m 10s
Posted - 2022.11.21 12:02:45
...

This is a cleaner visualisation that just uses the proportion of the cloud present on each edge to colour them.  It loses a little charm and you can no longer see associations, but it gains on clarity. 

I could make unanimous edges stand out a bit more, but for my purposes this probably does enough.  I think puzzles that look a nice, even orange on this plot should be particularly hard. Testing that, and discovering whether they are interesting or just obnoxious will require experiment
MondSemmel
Kwon-Tom Obsessive
Puzzles: 6159
Best Total: 7m 47s
Posted - 2022.11.21 12:52:58
Quote:
Originally Posted by Slithy
...

This is a cleaner visualisation that just uses the proportion of the cloud present on each edge to colour them.  It loses a little charm and you can no longer see associations, but it gains on clarity. 

I could make unanimous edges stand out a bit more, but for my purposes this probably does enough.  I think puzzles that look a nice, even orange on this plot should be particularly hard. Testing that, and discovering whether they are interesting or just obnoxious will require experiment
That looks great! One way I see to further improve this visualization for little effort would be to remove all the blue dotted lines which indicate a probability of 0; either leave them empty (white) or replace them with crosses, whichever option looks less cluttered. In either case, that would allow the yellow (unanimous) edges to stand out a lot more.

Also, I don't know if there's anything one can do with this information, but I found a possibly interesting implication of the Slither Link rule that all loops must be closed: the edges that go into each node must sum to 0 (0%) or 2 (200%). In particular, if a yellow (certain) edge enters a node, the probabilities of the other 1-3 nodes must sum to 1. Maybe this constraint could be used to further simplify the visualisation somehow?
Last edited by MondSemmel - 2022.11.21 12:53:07
Slithy
Kwon-Tom Addict
Puzzles: 381
Best Total: 2h 56m 10s
Posted - 2022.11.22 14:39:45
Quote:
Originally Posted by MondSemmel
remove all the blue dotted lines which indicate a probability of 0

Fine idea; and in this version I've also made the 1s black so all colours are clearly intermediate values.

https://photos.app.goo.gl/KbkYXxmAezPMPxqN9

Quote:
Originally Posted by MondSemmel
edges that go into each node must sum to 0 (0%) or 2 (200%). ...  Maybe this constraint could be used to further simplify the visualisation somehow

Hmmm... quite likely, though I don't immediately see how?  Though I do think it already helps interpretation.  For example, looking at the top-left vertex of the 3 in the bottom right corner we must have 1 of [Up, Left] and 1 of [Down, Right]; the shadings tell us Left is common, Up rarer; and the other 2 very evenly split. 

I think this is in practice most of what the original plot told us.  I had been hoping the original would make it possible to see more distant associations but with large clouds it was just too busy.

Incidentally, the "0 or 2" vertex continuity constraint binds pretty hard.  Looking just at 1 vertex it allows 5 of 16 possible configurations and if we look at 4 adjacent vertices (and make the risky assumption I have counted correctly) then it allows only 160 of 4096.   Making the also-risky guess that it continues to scale the same way then if we fill in edges on a 10x10 board at random, maybe 1 in 10^26 would be continuous at every vertex... but I haven't checked
Darklady
Kwon-Tom Obsessive
Puzzles: 5369
Best Total: 9m 37s
Posted - 2022.11.29 12:46:51
Quote:
10x10 - Hard 10
Highest entropy yet, so possibly hardest.

just wanted to mention that I actually found this to be one of the easier ones

perhaps without highlander deductions it'd be much harder, but with them it's fairly straightforward to pin down the bottom half, followed by the upper-left
Slithy
Kwon-Tom Addict
Puzzles: 381
Best Total: 2h 56m 10s
Posted - 2022.11.29 13:50:07
Quote:
Originally Posted by Darklady
just wanted to mention that I actually found this to be one of the easier ones

perhaps without highlander deductions it'd be much harder, but with them it's fairly straightforward to pin down the bottom half, followed by the upper-left

Interesting, and opens up several lines of thought:
    * I'll take a look at the route you suggest, I just gave up!
    * Highlanders seem a particularly strong way to attack minimal puzzles like these and adding redundant clues to obstruct this line of reasoning has been on the "To do" list since you outlined your first solution.
    * I wonder if puzzles with the highest cloud entropy might tend to favour Highlanders?  High entropy means many edges  that near-solutions (MLS) are about equally likely to contain or not, and is typically associated with a large number of MLS.  My first thought was that more MLS meant harder because fewer trials would lead to a contradiction, but maybe more trials lead to Highlanders...?
    * It may be that entropy is not a good target.  Another would be to minimise the number of edges on which all MLS agree.
    * Back in February I made a Heart puzzle that had a unique solution with the clues placed either on their board or on an infinite sheet.  I have assumed these are equally difficult to solve but maybe I should check, as the latter substitutes Highlanders for the implied 0 border present n the former and the differences might be illuminating.

Any other comments on which were more or less interesting, or difficult?

Forum Index