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:
- If it finds a solution using contradictions only, then you know it's a valid puzzle.
- If not (1), but it can find a solution by guessing, then you know the puzzle must have multiple solutions.
- 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 guessingIt'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).
