The New Sudoku Players' Forum

Website · by **denis_berthier** » Sat Feb 20, 2021 6:01 am

The bivalue conjecture

In science, a conjecture is not a vague idea:
- it must be precisely formulated;
- it must be supported by sufficiently strong evidence, making it reasonably believable;
- obviously, it must not have trivial counter-examples. (This is a very useful constraint, as it allows to refine the conjecture in the first stages of its formulation.)

In spite of mountains of evidence, proving that a conjecture is true may remain very difficult. For instance, long ago, I've made the conjecture that all the 9x9 Sudoku puzzles were in T&E(0, 1 or 2) and, a little later, the much stronger conjecture that they are indeed in B7B. I have checked both conjectures on all the hardest known puzzles (produced by the intensive work of many people) and I've found no counter-example. However, they still remain conjectures as I have no formal proof of their validity (and not the least idea of how such proofs could be found).
The fact that the B7B conjecture has no known counter-example provides huge supporting evidence for the weaker T&E(2) conjecture.

1) Preliminary definitions
Let me first give a few elementary definitions, based on my super-symmetric view of Sudoku that doesn't make any difference between the different types of CSP-Variables (or between the four 2D-spaces):
- a pair of different candidates is rc-bivalue if they are the only two candidates for a CSP-Variable of type rc (bivalue in usual Sudoku parlance)
- a pair of different candidates is rn-bivalue if they are the only two candidates for a CSP-Variable of type rn (bilocal in usual Sudoku parlance)
- a pair of different candidates is cn-bivalue if they are the only two candidates for a CSP-Variable of type cn (bilocal in usual Sudoku parlance)
- a pair of different candidates is bn-bivalue if they are the only two candidates for a CSP-Variable of type bn (bilocal in usual Sudoku parlance)

This can be stated in a more intuitive form, using the Extended Sudoku Board representation, as:
- a pair of different candidates is rc-bivalue if they are the only two candidates in a rc-cell
- a pair of different candidates is rn-bivalue if they are the only two candidates in a rn-cell
- a pair of different candidates is cn-bivalue if they are the only two candidates in a cn-cell
- a pair of different candidates is bn-bivalue if they are the only two candidates in a bn-cell

A pair of different candidates is bivalue if it is rc-bivalue or rn-bivalue or cn-bivalue or bn-bivalue.

Notice that:
- in Sudoku, a pair of different candidates can be bivalue at the same time in different ways (indeed in at most two ways in Sudoku);
- this notion of a bivalue pair can be defined in any CSP (a pair of different candidates is bivalue if they are the only two candidates for some CSP-Variable) and it is indeed widely used in all the applications of CSP-Rules: FutoRules, KakuRules, Slitherlink...
- the simplest chains, bivalue-chains, are based on bivalue pairs and they are a generic notion in CSP-Rules;
- all the generic chain rules in SudoRules are extensions of bivalue chains.
All this shows that "bivalue" is a fundamental concept.

As usual, a valid puzzle is a puzzle with one and only one solution.

2) The bivalue conjecture
For any valid puzzle P:
- either P can be solved by ECP and Singles
- or, after ECP and Singles have been fully applied, P has at least one bivalue pair of candidates.
ECP = Elementary Constraints Propagation, i.e. use of direct contradictions from Singles for eliminations.

3) Supporting facts
As of now, what are the facts supporting this bivalue conjecture?
I've scanned two very different collections of puzzles without finding any counter-example:
- the first 21375 puzzles of the controlled-bias collection (https://github.com/denis-berthier/Controlled-bias_Sudoku_generator_and_collection)
- the full collection of 26370 hardest puzzles by eleven.

These collections are as opposed as one may imagine:
- the first is randomly generated and made of puzzles of all levels of difficulty in T&E(0 or 1);
- the second is among the hardest known puzzles (all in T&E(2).

[Edit: Also tried champagne's last list of hardest:
- the first 20,000
- the last 20,000]

4) Anecdotic comments
In another thread (http://forum.enjoysudoku.com/is-there-a-puzzle-with-no-3d-trivalue-cell-t38587.html), I wondered about trivalue triplets of candidates. But this relied on my false belief that, long ago, I had seen a puzzle with no bivalue pairs. After Coloin talked about Fata Morgana (which has no rc-bivalue pair, but has other bivalue pairs), I realised that, in my souvenirs, bivalue and rc-bivalue might have got mixed up.
In order to avoid any confusion due to what I wrote in the other thread, I preferred opening a new one for clearly stating this conjecture.

(If someone wants to use CSP-Rules to check the conjecture on other large collections, contact me; I'll send you code for a few functions not yet present in the current release of CSP-Rules.)

by **coloin** » Sat Feb 20, 2021 11:28 am

In looking for puzzles with fewest "bivalues"
I looked at a few puzzles ... ideally they would have clues in box count of 222222222, and clue value distribution of 22222222.
Unfortunately there are very few 18C puzzles which have an ED > x/x/6.6

A while back I searched very hard for more diamond 20C puzzles , this one has favourable clue distribution [222223322]
... and my eye can only see 3 "bivalues" ... envolving the high frequency clues

Code: Select all: ...........1.....3.4..5.97.2....8.....31......6..7..4....2....8......76..5..6..9. ED=11.1/11.1/9.4

Code: Select all: +-------------------------+-------------------------+-------------------------+ | 356789 23789 256789 | 346789 123489 1234679 | 124568 1258 12456 | | 56789 2789 1 | 46789 2489 24679 | 24568 258 3 | | 368 4 268 | 368 5 1236 | 9 7 126 | +-------------------------+-------------------------+-------------------------+ | 2 179 4579 | 34569 349 8 | 1356 135 15679 | | 45789 789 3 | 1 249 24569 | 2568 258 25679 | | 1589 6 589 | 359 7 2359 | 12358 4 1259 | +-------------------------+-------------------------+-------------------------+ | 134679 1379 4679 | 2 1349 134579 | 1345 135 8 | | 13489 12389 2489 | 34589 13489 13459 | 7 6 1245 | | 13478 5 2478 | 3478 6 1347 | 1234 9 124 | +-------------------------+-------------------------+-------------------------+

Website · by **denis_berthier** » Sat Feb 20, 2021 12:56 pm

coloin wrote:In looking for puzzles with fewest "bivalues"
I looked at a few puzzles ... ideally they would have clues in box count of 222222222, and clue value distribution of 22222222.
Unfortunately there are very few 18C puzzles which have an ED > x/x/6.6

A while back I searched very hard for more diamond 20C puzzles , this one has favourable clue distribution [222223322]
... and my eye can only see 3 "bivalues" ... envolving the high frequency clues
Code: Select all
...........1.....3.4..5.97.2....8.....31......6..7..4....2....8......76..5..6..9. ED=11.1/11.1/9.4

Code: Select all
+-------------------------+-------------------------+-------------------------+ | 356789 23789 256789 | 346789 123489 1234679 | 124568 1258 12456 | | 56789 2789 1 | 46789 2489 24679 | 24568 258 3 | | 368 4 268 | 368 5 1236 | 9 7 126 | +-------------------------+-------------------------+-------------------------+ | 2 179 4579 | 34569 349 8 | 1356 135 15679 | | 45789 789 3 | 1 249 24569 | 2568 258 25679 | | 1589 6 589 | 359 7 2359 | 12358 4 1259 | +-------------------------+-------------------------+-------------------------+ | 134679 1379 4679 | 2 1349 134579 | 1345 135 8 | | 13489 12389 2489 | 34589 13489 13459 | 7 6 1245 | | 13478 5 2478 | 3478 6 1347 | 1234 9 124 | +-------------------------+-------------------------+-------------------------+

SudoRules finds 9 bivalue pairs:

Code: Select all: f-10913 (bivalue 0 136 139 231) f-10915 (bivalue 0 142 161 441) f-10917 (bivalue 0 443 451 444) f-10919 (bivalue 0 644 656 456) f-10921 (bivalue 0 348 378 383) f-10923 (bivalue 0 749 759 467) f-10925 (bivalue 0 749 759 397) f-10927 (bivalue 0 671 673 476) f-10929 (bivalue 0 671 673 276)

but some pairs are bivalue for two CSP-Variables:

Code: Select all: f-10923 (bivalue 0 749 759 467) f-10925 (bivalue 0 749 759 397) and f-10927 (bivalue 0 671 673 476) f-10929 (bivalue 0 671 673 276)

so, you can count 7 or 9, depending on the context of use.

This makes me think that, when I print the resolution state after after the initial Singles, I could have an option to also print the other three 2D-spaces instead of only the rc one.

by **nazaz** » Sun Feb 28, 2021 11:46 pm

Code: Select all: .3.21.45.41..5..235.23.41.61.5..234.72.43.5.1.431.5..225..41.3...15.32.43.482..15

Website · by **denis_berthier** » Mon Mar 01, 2021 6:08 am

nazaz wrote:
Code: Select all
.3.21.45.41..5..235.23.41.61.5..234.72.43.5.1.431.5..225..41.3...15.32.43.482..15

Hi nazaz,
First, welcome on this forum.
For a first post, this is a great contribution.

Not only is it the first puzzle proposed with no bivalue pair; it's also the first I can remember with SER 9.0 that can't be solved with whips only or braids only: it is NOT in T&E(1). It requires g-whips (and it becomes relatively easy when g-whips are allowed):

g-whip solution: Show

Could you tell us how you found it?

Website · by **denis_berthier** » Mon Mar 01, 2021 6:45 am

A single example is enough to invalidate a conjecture, whatever amount of supporting evidence it can have.
While nazaz found this counter-example, I had some program running on an old computer, scanning champagne's collection of hardest. I found no counter-example in the first 200,000.

by **nazaz** » Mon Mar 01, 2021 8:08 am

Hi. It was found partly by construction, partly by random search. The construction was to have (1,2,3,4,5) each occurring nine times, leaving four candidates for every constraint, plus one each of (6,7,8) in the hope of "pinning down" the completions to just a single grid. Then I just applied that recipe to random grids until I got a hit, but you could do that part exhaustively I guess.

Website · by **denis_berthier** » Tue Mar 02, 2021 3:11 am

nazaz wrote:Hi. It was found partly by construction, partly by random search. The construction was to have (1,2,3,4,5) each occurring nine times, leaving four candidates for every constraint, plus one each of (6,7,8) in the hope of "pinning down" the completions to just a single grid. Then I just applied that recipe to random grids until I got a hit, but you could do that part exhaustively I guess.

Good.
What do you think of my original, much weaker (therefore much harder to disprove) conjecture that, after Singles, there is no unsolved puzzle with no bivalue and no trivalue cell?

by **mith** » Sun Mar 07, 2021 1:42 am

Assuming I'm understanding what is/isn't covered by ECP, here's another example, based on Endor Fins 2 (also SER 9.0):

Code: Select all: .86.79..54.985.76.75...698..9.5..8765.768..2986..975..9.871.65.6.59.8..7.7..65.98

I don't think it's possible to take this approach for the stronger version; a 999991110 distribution is already rare, but aside from that with a 999911110 distribution it's not possible to place the four unique givens without creating trivalue cells. (This doesn't rule out a minimal with an early non-singles step, of course, though it's hard to imagine such a minimal that doesn't have bivalue or trivalue cells on one of the non-unique givens, if there are any not totally filled.)

Website · by **denis_berthier** » Sun Mar 07, 2021 3:53 am

mith wrote:Assuming I'm understanding what is/isn't covered by ECP, here's another example, based on Endor Fins 2 (also SER 9.0):

Code: Select all
.86.79..54.985.76.75...698..9.5..8765.768..2986..975..9.871.65.6.59.8..7.7..65.98

I don't think it's possible to take this approach for the stronger version; a 999991110 distribution is already rare, but aside from that with a 999911110 distribution it's not possible to place the four unique givens without creating trivalue cells. (This doesn't rule out a minimal with an early non-singles step, of course, though it's hard to imagine such a minimal that doesn't have bivalue or trivalue cells on one of the non-unique givens, if there are any not totally filled.)

ECP is Elementary Constraints Propagation, from decided values (including givens) to the candidates they make impossible.
After ECP and Singles have been applied (there is no Single), we have the following RESOLUTION STATE:

Code: Select all: 123 8 6 1234 7 9 1234 134 5 4 123 9 8 5 123 7 6 123 7 5 123 1234 234 6 9 8 1234 123 9 1234 5 234 1234 8 7 6 5 134 7 6 8 134 134 2 9 8 6 1234 1234 9 7 5 134 134 9 234 8 7 1 234 6 5 234 6 1234 5 9 234 8 1234 134 7 123 7 1234 234 6 5 1234 9 8

As you can check, there is a rn-bivalue pair (and it's the only bivalue pair):
(bivalue 0 263 264 262)
in row 6 number 2 is only in columns 3 and 4

For a SER 9.0, this puzzle is relatively easy (in W5).
BTW, the bivalue or trivalue conjecture is not stronger than the bivalue one, as I had inadvertently written: it is much weaker and therefore much harder to disprove if false.

by **mith** » Sun Mar 07, 2021 7:51 pm

Ah, missed that. Ok, a bit harder to find to find a grid that works, but I did find one from the 17c solution grids:

Code: Select all: 73.4...62..2.7634..4623.1.746.7.2..3.786.342.2.3.4.67.6.732...4.2..6473.3.49.72.6 SER 9.3 from ..54..8...12...............46.7............21........86...21.........73.....5.... SER 1.5

Code: Select all: .-----------------.-----------------.-----------------. | 7 3 159 | 4 1589 1589 | 589 6 2 | | 1589 1589 2 | 158 7 6 | 3 4 589 | | 589 4 6 | 2 3 589 | 1 589 7 | :-----------------+-----------------+-----------------: | 4 6 159 | 7 1589 2 | 589 1589 3 | | 159 7 8 | 6 159 3 | 4 2 159 | | 2 159 3 | 158 4 1589 | 6 7 1589 | :-----------------+-----------------+-----------------: | 6 1589 7 | 3 2 158 | 589 1589 4 | | 1589 2 159 | 158 6 4 | 7 3 1589 | | 3 158 4 | 9 158 7 | 2 158 6 | '-----------------'-----------------'-----------------'

For one of these to work, you need the following:
1. 5 of the digits are completely given (45 givens total).
2. Three cells must be chosen from the empty cells left by those 45 givens. These three cells must be in different bands and stacks.
3. Filling three different digits in those cells must yield a unique solution. (In the examples I'm looking at, which already have a unique solution up to digit permutation, this just means the values of those cells must be different in the solution.)
4. Filling these three cells, along with the other 45 givens, must not leave any row/box or column/box intersection completely filled. (This means the 45 givens can't already filled a row/box or column/box intersection, and also that there is exactly one cell that can be potentially be chosen for each box - the cell for which both its row and its column have two empty cells in that box.)
5. The intersection of one cell's row with another cell's column must be filled with a given.

Most of the ones I looked at had an option which met all the criteria but the last, leaving one bivalue cell at that intersection. The Endor Fins 2 attempt breaks 4 (due to 876 in r4c789).

by **999_Springs** » Sun Mar 07, 2021 8:31 pm

nazaz wrote:Hi. It was found partly by construction, partly by random search. The construction was to have (1,2,3,4,5) each occurring nine times, leaving four candidates for every constraint, plus one each of (6,7,8) in the hope of "pinning down" the completions to just a single grid. Then I just applied that recipe to random grids until I got a hit, but you could do that part exhaustively I guess.

hi nazaz,

well done for constructing such a puzzle

you and mith and denis might like to know that dobrichev did an exhaustive search of all possible puzzles with 48 clues that have 5 digits all filled in and 1 each of 3 other digits, like the one you found, in 2011 and posted the hardest ones skfr 10+ here. there are 101 of them but that reduces to about 30 different ones after you do the singles at the start of some of them. there is a summary of overall skfr ratings for all 2432930 puzzles on the next page here

it could definitely be possible that some of those puzzles at the harder end have no bivalue or bilocation after you do all the singles and it would be very easy to check so thanks for coming up with that idea

i messaged dobrichev asking if he had the rest of the collection a while ago, i was looking into the 9.3+ range because i wanted some seeds for my thread on max clues for each se rating, but he said he didn't have them

edit: i have checked that the 5th and 6th puzzles in dobrichev's list have no bivalue or bilocation. there could be many more

dobrichev wrote:
Code: Select all
97.85.63.56.7..9.8..8.69.7589.5.6..7.56.7.89.4.79.856.6...857.97.529..86.896.7.5. 10.2 10.2 9.4 85.79.63.67.8..9.5..9.56.8778.5.9.6.9.564..78..6.785.95.7.8..9619..6785..689.57.. 10.2 10.2 8.8

edit: coloin, if you are looking for a puzzle with no bivalue or bilocation, ed=6.6 will not cut it, because of the way se works the first step has to be in at least the middle of the nishio range 7.8+ unless it is a triplet or a swordfish. that's because forcing chains under se's construction rely on the existence of them to find eliminations. so 18s are the wrong place to look. turns out you were going in the wrong direction and 48s were the answer

Website · by **denis_berthier** » Mon Mar 08, 2021 5:06 am

mith wrote:Ah, missed that. Ok, a bit harder to find to find a grid that works, but I did find one from the 17c solution grids:
Code: Select all
73.4...62..2.7634..4623.1.746.7.2..3.786.342.2.3.4.67.6.732...4.2..6473.3.49.72.6 SER 9.3 from ..54..8...12...............46.7............21........86...21.........73.....5.... SER 1.5

For one of these to work, you need the following:
1. 5 of the digits are completely given (45 givens total).
2. Three cells must be chosen from the empty cells left by those 45 givens. These three cells must be in different bands and stacks.
3. Filling three different digits in those cells must yield a unique solution. (In the examples I'm looking at, which already have a unique solution up to digit permutation, this just means the values of those cells must be different in the solution.)
4. Filling these three cells, along with the other 45 givens, must not leave any row/box or column/box intersection completely filled. (This means the 45 givens can't already filled a row/box or column/box intersection, and also that there is exactly one cell that can be potentially be chosen for each box - the cell for which both its row and its column have two empty cells in that box.)
5. The intersection of one cell's row with another cell's column must be filled with a given.
Most of the ones I looked at had an option which met all the criteria but the last, leaving one bivalue cell at that intersection. The Endor Fins 2 attempt breaks 4 (due to 876 in r4c789).

Hi Mith
Great example and great explanations.

Website · by **denis_berthier** » Mon Mar 08, 2021 5:15 am

999_Springs wrote: dobrichev did an exhaustive search of all possible puzzles with 48 clues that have 5 digits all filled in and 1 each of 3 other digits, like the one you found, in 2011 and posted the hardest ones skfr 10+ here. there are 101 of them but that reduces to about 30 different ones after you do the singles at the start of some of them. there is a summary of overall skfr ratings for all 2432930 puzzles on the next page here
it could definitely be possible that some of those puzzles at the harder end have no bivalue or bilocation after you do all the singles and it would be very easy to check so thanks for coming up with that idea
i messaged dobrichev asking if he had the rest of the collection a while ago, i was looking into the 9.3+ range because i wanted some seeds for my thread on max clues for each se rating, but he said he didn't have them
edit: i have checked that the 5th and 6th puzzles in dobrichev's list have no bivalue or bilocation. there could be many more
dobrichev wrote:
Code: Select all
97.85.63.56.7..9.8..8.69.7589.5.6..7.56.7.89.4.79.856.6...857.97.529..86.896.7.5. 10.2 10.2 9.4 85.79.63.67.8..9.5..9.56.8778.5.9.6.9.564..78..6.785.95.7.8..9619..6785..689.57.. 10.2 10.2 8.8

Hi 999_Springs
Thanks for this interesting reference.
I've checked the full list of 101 puzzles there. Only 3 have no bivalue pairs: 5, 6 and 76

Code: Select all: #76: 76.85.9..95.7.46.8..8.96.5768.9..57...5.678.9.795.8.618.6..579.53..79.86.9768...5

I had a look at dobrichev's puzzle collections: https://sites.google.com/site/dobrichev/sudoku-puzzle-collections. I didn't find any with 48 givens, but the link may be of interest per se.

by **mith** » Mon Mar 08, 2021 6:50 pm

It's interesting that while nazaz's puzzle is not uniquely solvable by removing the three unique digits and filling a house, the three dobrichev puzzles are (and all of them reduce to the same ER with the relabel trick):

Code: Select all: 97.85.6..56.7..9.8..8.69.7589.5.6..7.56.7.89...79.856.6123857497.5.9..86.896.7.5. ED=7.6/7.6/2.6 85.79.6..67.8..9.5..9.5618778.5.926.9.56..378..6.785.95.7.8.496.9..6785..689.57.. ED=7.6/7.6/2.6 76.85.9..95.7..6.8..8.96.5768.9..57...5.678.9.795.8.6.816..579.523.79.8649768...5 ED=7.6/7.6/2.6

My 9.3 reduces to a 7.1:

Code: Select all: 73.4...62.12.7634..4623...746.7.2..3.7.6.342.253.4.67.68732...4.2..6473.394..72.6 ED=7.1/7.1/2.6

The New Sudoku Players' Forum

The bivalue conjecture

The bivalue conjecture

Re: The bivalue conjecture

Re: The bivalue conjecture

Re: The bivalue conjecture

Re: The bivalue conjecture

Re: The bivalue conjecture

Re: The bivalue conjecture

Re: The bivalue conjecture

Re: The bivalue conjecture

Re: The bivalue conjecture

Re: The bivalue conjecture

Re: The bivalue conjecture

Re: The bivalue conjecture

Re: The bivalue conjecture

Re: The bivalue conjecture