RSW wrote:If you're going to use T&E then I don't see any particular problem in deciding how to go about it.
Well, it's of course a simple programming problem (unless you want to fully optimize it), but I was talking about human solving. There it pays off to make the guesses as educated as possible, because no one wants to run a zillion trials manually (especially on paper).
Once you've exhausted all logical solution techniques, just pick a cell with the fewest candidates
Or a unit with the fewest possible cells for a digit? I did consider candidates with bilocation strong-links too, but they didn't seem as potential in this case (turns out they weren't either). Even though I was using a software helper for this exercise, I made some mental predictions about the potential before picking the candidates to test. When a program runs those tests, it doesn't have to be so picky of course, and it's probably more efficient to use very simple heuristics like that. For a human solver it's different, because the actual testing can be very tedious. Based on your output, my manual picking did result in fewer trials, but perhaps I was just lucky.
and then continue on under the assumption that you've made the correct choice (using the full set of logical techniques again) until one of the following happens:
1. Puzzle solved. You're done!
I'm not! I'm not done if I happen to hit a backdoor and find a solution. How would you document that as a proof? Even if using T&E, I'd like to be able to produce a solve path that proves the solution via a set of proven eliminations. Yes, someone can argue that a solved grid is a proof too, but it's just not the same. Here's an example of a puzzle where I found a backdoor accidentally while looking for chains (pure pencil&paper solving), but it really didn't make me happy. In the end I went back and solved the rest of it with actual elimination steps, too, because it just wasn't a satisfying finish otherwise. With a super-hard puzzle I might reconsider that position.
Also, as others have mentioned, that's not where you want to stop if you want to prove the uniqueness of the solution. Of course that has any practical meaning for software solving only. Obviously you can't use any uniqueness techniques (except some special cases) then either (which would be pretty dumb from a manual solver's point of view). If you know beforehand that the puzzle has a unique solution (which is all I would manually solve), then this point is meaningless of course.
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). 2. Reached a contradiction, so go back to the last cell that you guessed and try a different guess.
3. Reached another impasse without solving the puzzle. So, guess the value of another cell and continue.
Yes, this is the trivial backtracking algorithm, and as such it does apply to manual T&E as well. My real question is about finding good heuristics for picking the tested candidates (or combinations of them) to make the process as manually-applicable as possible. There's no point in trying to mimic a software solver's brute force algorithm manually (unless, of course, it happens to have excellent heuristics).
## All Logic Strategies exhausted at top level. Starting new branch level 1.
## Choosing cell having fewest candidates: r5c3: [5,6]
## Level 1, trying r5c3=5: Leads to contradiction. Backtracking...
How did it find a contradiction? I ran my tests with the SudokuWiki solver and even its full technique set (including krakens) couldn't find a direct contradiction with 5r5c3 when tried as the first candidate. (It's possible with a a nested guess, but I rather tried the other bivalue cell which worked directly). Did your program use a nested guess to find the contradiction? If so, I think it should be shown in the output. If not, then what kind of a technique set does your program use to test those paths? In any case, I think it would be valuable information to show how complicated those trial steps were. This doesn't really tell us anything what happened behind the scenes (it's just a blackbox brute-force move).
## Level 1, trying r5c3=6: Leads to solution.
As eleven pointed out, this output is a bit confusing. Does your program actually test that case? Why would it, since you already found a contradiction for its bivalue cellmate and know that 6r5c3 must be the true candidate (if the puzzle has a solution at all)? Then again, if it's not really tested but it's just an assumption, then it's misleading (unless your program knows beforehand that the puzzle has at least one solution).
Btw, it might be a good idea to put long outputs into a hidden text block:
Software Output: Show
