Guessing, and T&E have of course been discussed in depth before. One particular thread from 2013 in particular has plenty to say about it:
http://forum.enjoysudoku.com/one-flew-over-the-backdoors-t31086-45.html
BLISS is a "Basic Logical Implication & Singles Solver". It is strictly non-recursive, and apart from Singles uses just one additional "technique", the logical implication. When all singles have been exhausted, we test all candidates (r,c,d) as follows:
- Let PM be the current pencilmark state. Let PM1 be the state obtained from setting (r,c) = d, then checking for singles(DoSingles). Let PM0 the corresponding state obtained from (r,c) != d + DoSingles.
- if any cell is solved, (rr, cc) = dd, in both PM0 and PM1, but not in PM, then the implication is that (rr, cc) = dd
- if for any cell (rr, cc) = dd is eliminated in both PM0 and PM1, but not in PM, then the implication is that (rr, cc) != dd
This process is repeated for all unsolved cells, and until such time as we find no implications, OR we stumble across a backdoor. For, if the puzzle is valid, and it is only valid puzzles I am interested in, then any PM1 or PM0 can be a fully solved puzzle. So the "B" in BLISS could equally stand for backdoors, as they are simply a by-product of the solving process.
Clearly BLISS will solve any puzzle that has a singles backdoor, and of course any "singles only" puzzle, so we will restrict the discussion to those puzzles which are NOT singles only, and do not have a singles backdoor of size 1. I am interested in exploring how BLISS copes with "hard" puzzles.
I will post some more details below, and an example. But before I go on, I need to ask a question!
In the thread mentioned above, we have the following:
denis_berthier wrote:Another vaguely related topic is the depth of T&E necessary to solve any puzzle. Contrary to the backdoor size 2 conjecture, the T&E(2) conjecture has resisted all the newly found hard 9x9 puzzles.
Backdoor size and T&E depth correspond to opposite views of solving:
- backdoor size is the minimum number of values that must be guessed in order to solve a puzzle with Singles only
- T&E-depth is the minimum depth of T&E that must be used in order to be able to solve a puzzle with Singles only without accepting any guessing (a candidate is accepted as a value iff all the other candidates for the same CSP variable have been proven to be impossible)
I understand the "backdoor 2 conjecture" is ancient history, of course, in fact my learned colleague Mladen has produced 279 puzzles with no backdoor 3's. More on that later.
But the "T&E(2) conjecture" intrigues me. BLISS can work with pairs of cells, of course, so let's call that "BLISS(2)". My question is, is single-cell mode BLISS effectively a "T&E(1)" solver, and would BLISS(2) be equivalent to "T&E(2)"? Can it really be described as a "T&E" solver at all?
Cheers
MM
