Help for Weekly Unsolvable #324

Post the puzzle or solving technique that's causing you trouble and someone will help

Re: Help for Weekly Unsolvable #324

Postby SpAce » Wed Dec 12, 2018 1:01 am

RSW wrote:
SpAce wrote:Based on your output, my manual picking did result in fewer trials, but perhaps I was just lucky.

I have to correct something about that earlier statement of mine: the comparison didn't make any sense, of course, because the technique sets were quite different. My trials used much more complex techniques, so of course fewer were needed. Therefore nothing can be concluded about the relative quality of the guesses.

This is an area that I intend to pursue. I agree that there should be better ways of choosing the best cell for T&E.

Good. It would be interesting to hear if you find any improvements. Seems that picking the guesses is (or at least used to be) a somewhat open question even in the fast brute force champagne mentioned.

It seems to me that the existence of a valid solution is sufficient documentation.

Sufficient but not necessarily satisfactory. Of course that's just an arbitrary personal preference, nothing else.

However, there could certainly be more than one solution, and the only way to find that out for sure would be to solve it with purely logical techniques, or else do an exhaustive brute force solution to see if the solution is unique.

True, but even T&E does produce a path of purely logical techniques (just not very elegant ones) if only guessed (but proved) contradictions but not guessed solutions are accepted. If applied that way and a solution is found without using uniqueness techniques, then it also proves the uniqueness of the solution. The way I originally applied T&E to this problem did not, because I didn't disable uniqueness techniques (and there were a couple of Hidden Rectangles in the path), but it does if I do (those few HRs had probably no impact whatsoever). Thus I would count that as one reason why T&E with only contradictions is more satisfactory. (Then again, I would certainly not stop using uniqueness techniques for that reason when solving manually.)

SpAce wrote:Also, as others have mentioned, that's not where you want to stop if you want to prove the uniqueness of the solution.

The purpose my solver is to find one valid solution and give an explanation of the steps, not find all possible solutions of an improperly formed puzzle. That would be the job for a brute force solver, and I would approach that with entirely different programming methods.

Proving the uniqueness of a solution and finding all solutions of an invalid puzzle are two different things. For the latter you need a brute force solver, but not for the former (as explained above). I'm mostly conjecturing here, but to me it seems that a pure T&E process without uniqueness techniques should be able to tell you these things:

  1. If it finds a solution using contradictions only, then you know it's a valid puzzle.
  2. If not (1), but it can find a solution by guessing, then you know the puzzle must have multiple solutions.
  3. If not (1) or (2), then you know the puzzle has no solution.
SpAce wrote:One more thing. I wouldn't call it T&E if you accept a found solution and stop at that. In my books that term only applies when you're hunting for contradictions, i.e. errors, which prove a choice wrong. Otherwise it's Trial&Success, or lucky guessing :) It's a subtle distinction, but I think that's how T&E is usually defined on this forum (or maybe I've just bought someone's propaganda).

That would be true only if the solver was lucky enough to reach a solution without making any wrong guesses. While that could happen, it would be very unlikely.

Well, you're right that only the last step of such a solution would be T&S. It would still be one too many T&S steps than my preferred way which is T&E all the way.

Sorry. I didn't answer your question about whether it involved nested guesses. Yes, it did. As many as 8 at one point.
It turned out to be relatively easy to add an additional log file that includes all dead ends.

Ok, that's what I thought had to happen. Thanks for confirming it. Btw, if you don't want to collect those long logs for the internal branches, you could just add a counter and report the number of nested guesses needed to find each contradiction. I think that would be enough information on the main log to indicate the complexity of each trial step (when the applicable technique set is known).
SpAce
 
Posts: 1021
Joined: 22 May 2017

Re: Help for Weekly Unsolvable #324

Postby champagne » Wed Dec 12, 2018 2:31 am

StrmCkr wrote:
a.1) the band is valid
a.2) the band can be cleaned applying the logical rules*
locked in box
locked in row
b) other bands of the digits are cleaned applying the same rule in column
c) new assigned rows of the bands are identified and the corresponding cleaning is done for other digits.


wouldn't the same effect apply to stacks as well?


Right, but having an heavily band oriented frame, it's faster to guess. Any stack property is tougher to code in this frame

In the original code, cells having only one left candidate were not searched and the guess was done only in priority for bi values in band (row/box).

Don't forget that the target is here to find as quick as possible whether the puzzle has a unique solution.
fss2 use quite a different frame and strategy with a similar performance.
champagne
2017 Supporter
 
Posts: 6790
Joined: 02 August 2007
Location: France Brittany

Re: Help for Weekly Unsolvable #324

Postby StrmCkr » Thu Dec 13, 2018 10:09 am

Couldn't you do a transpose move set on the grid and swap rows for Colums and perform the same update instead of reimplmemting more code and frame work.

Food for thought.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 942
Joined: 05 September 2006

Re: Help for Weekly Unsolvable #324

Postby champagne » Thu Dec 13, 2018 11:49 am

StrmCkr wrote:Couldn't you do a transpose move set on the grid and swap rows for Colums and perform the same update instead of reimplmemting more code and frame work.

Food for thought.

this is widely used in my "solver" code, but much too costly in the brute force
champagne
2017 Supporter
 
Posts: 6790
Joined: 02 August 2007
Location: France Brittany

Previous

Return to Help with puzzles and solving techniques