Sudoku Players' Forum (clone)

Thank you Denis.
These patterns are not 4-colorable. You proved that they are not 3-colorable (which should not be in T&E(2), given there are multiple instances of four restricted cells in the same house?). I should have been more explicit.

I would run them through CSP-Rules myself (and have done so for simpler things), but it turns out my resources are insufficient for these kinds of proof (I'm only on a Macbook Air with 8GB RAM).

ryokousha wrote:These patterns are not 4-colorable. You proved that they are not 3-colorable. I should have been more explicit.

What I proved is a positive result: as 3-digit patterns, all these patterns can be proven contradictory in T&E(2); they don't require T&E(3) for this.
I don't know your definition of 4-colourable in Sudoku. I know the definition in graph theory, but it doesn't seem to apply in any useful straightforward way to Sudoku.
Or are you talking of 4-digit patterns ?

ryokousha wrote:I would run them through CSP-Rules myself (and have done so for simpler things), but it turns out my resources are insufficient for these kinds of proof (I'm only on a Macbook Air with 8GB RAM).

I hadn't noted how much memory was required, so I re-launched all (i.e. the 30 patterns), with function call:

Code: Select all

(solve-n-grids-after-first-p-from-k-digit-pattern-string-file 3 "ryokousha-5chr.txt" 0 30)

1) in T&E(2), i.e. with settings:
(bind ?*TE2* TRUE)

Code: Select all

- 20.5 MB (sic: MB not GB)
- total time: 4.19 s

2) for the more precise result, i.e. with settings:
(bind ?*Bivalue-Chains* TRUE)
(bind ?*Whips* TRUE)
(bind ?*z-Chains* TRUE)
(bind ?*all-chains-max-length* 3)
(bind ?*TE1* TRUE)

Code: Select all

- 1.53 GB
- total time: 2 mn 5 s

The point of these patterns is: they don't work if the marked cells are restricted to four values, i.e. you should run

Code: Select all

(solve-k-digit-pattern-string 4 "..................11.1..1........1...1.1..1..11..1...1.1..111..1..1.....1..1.....")

etc. - which then does take significantly more resources.

It should be obvious they do not work for 3.

I do agree with you that the terms "colorable" and "chromatic" are problematic in a sudoku context. Currently I try to use "n-chromatic" only for patterns for which the graph induced by the marked cells (i.e. the connection graph between these cells) is n-chromatic in the graph-theoretical sense.
This does not necessarily imply that the pattern is n-colorable in sudoku (so the cells in question may or may not be restricted to n values).
The "sausage roll" pattern is a good example for this: in my terminology it would be 3-chromatic, but not 3-colorable.

Anyway this is only my private usage of the terms, but it is clear we have to be a bit careful.

After the surge of T&E(3) puzzles, I thought we were still talking of 3-digit patterns.

ryokousha wrote:The point of these patterns is: they don't work if the marked cells are restricted to four values, i.e. you should run

Code: Select all

(solve-k-digit-pattern-string 4 "..................11.1..1........1...1.1..1..11..1...1.1..111..1..1.....1..1.....")

etc. - which then does take significantly more resources.
It should be obvious they do not work for 3.

Not so obvious, as it requires T&E(S2, 1) + W3

As for 4, you can run the above command in T&E(3). Of course, it will take more time and memory than running it in T&E(2), especially as I've never tried to optimise my T&E procedures.

As a result of doing this, the following is no longer true (the proof required only 1 mn 17 s and 33.7 MB):

ryokousha wrote:This is a 20 cell minimal arising from those. We have not yet found any proof that this can't be 4-colored.

Code: Select all

------------------------------
  .  .  . | .  .  . | .  .  .
  .  .  . | .  .  . | .  .  .
  X  X  . | X  .  . | X  .  .
------------------------------
  .  .  . | .  .  . | X  .  .
  .  X  . | X  .  . | X  .  .
  X  X  . | .  X  . | .  .  X
------------------------------
  .  X  . | .  X  X | X  .  .
  X  .  . | X  .  . | .  .  .
  X  .  . | X  .  . | .  .  .
------------------------------
..................11.1..1........1...1.1..1..11..1...1.1..111..1..1.....1..1.....


[/quote]

denis_berthier wrote:Not so obvious, as it requires T&E(S2, 1) + W3

It is obvious since there are more than 3 restricted cells within several houses, so the pattern cannot possibly be 3-colorable.
Also this deduction can't require T&E(S2, 1) + W3. Could it be the code assuming the pattern is (n+1)-colorable if you check for n-colorability?

I was (just barely) able to run CSP-Rules with T&E(3) enabled:

Code: Select all

GRID 0 HAS NO SOLUTION : NO CANDIDATE FOR FOR CN-CELL c7n2
MOST COMPLEX RULE TRIED = Z[4]
Puzzle ..................11.1..1........1...1.1..1..11..1...1.1..111..1..1.....1..1..... :
init-time = 0.05s, solve-time = 54m 3.85s, total-time = 54m 3.9s
***********************************************************************************************
***  SudoRules 20.1.s based on CSP-Rules 2.1.s, config = T&E(W+SFin+TridFW, 3)
***  Using CLIPS 6.32-r819
***  Running on MacBook Air Intel Core i5 1,6 GHz, 8 GB RAM, MacOS HighSierra 10.13.6
***  Download from: https://github.com/denis-berthier/CSP-Rules-V2.1
***********************************************************************************************


btw. Marek told on discord he has a proof it is in T&E(3), so I was expecting that. He also gave an elegant proof of impossibility based on a senior exocet and two possible resulting bivalue odddagons.

ryokousha wrote:

denis_berthier wrote:Not so obvious, as it requires T&E(S2, 1) + W3

It is obvious since there are more than 3 restricted cells within several houses, so the pattern cannot possibly be 3-colorable.

This supposes you don't care about the T&E complexity of the proof.

Optimizing for MEMORY instead of SPEED seems to help:

Code: Select all

GRID 0 HAS NO SOLUTION : NO CANDIDATE FOR FOR CN-CELL c7n2
MOST COMPLEX RULE TRIED = Z[4]
Puzzle ..................11.1..1........1...1.1..1..11..1...1.1..111..1..1.....1..1..... :
init-time = 0.05s, solve-time = 6m 0.85s, total-time = 6m 0.9s
***********************************************************************************************
***  SudoRules 20.1.m based on CSP-Rules 2.1.m, config = T&E(W+SFin, 2)
***  Using CLIPS 6.32-r819
***  Running on MacBook Air Intel Core i5 1,6 GHz, 8 GB RAM, MacOS HighSierra 10.13.6
***  Download from: https://github.com/denis-berthier/CSP-Rules-V2.1
***********************************************************************************************


So it is in T&E(W+SFin, 2).

ryokousha wrote:I was (just barely) able to run CSP-Rules with T&E(3) enabled:

Code: Select all

GRID 0 HAS NO SOLUTION : NO CANDIDATE FOR FOR CN-CELL c7n2
MOST COMPLEX RULE TRIED = Z[4]
Puzzle ..................11.1..1........1...1.1..1..11..1...1.1..111..1..1.....1..1..... :
init-time = 0.05s, solve-time = 54m 3.85s, total-time = 54m 3.9s
***********************************************************************************************
***  SudoRules 20.1.s based on CSP-Rules 2.1.s, config = T&E(W+SFin+TridFW, 3)
***  Using CLIPS 6.32-r819
***  Running on MacBook Air Intel Core i5 1,6 GHz, 8 GB RAM, MacOS HighSierra 10.13.6
***  Download from: https://github.com/denis-berthier/CSP-Rules-V2.1
***********************************************************************************************


Obviously, you are not running the proof in T&E(3) but in T&E(W+SFin+TridFW, 3).
That's why your computation time is so long.
You forgot to disable the rules activated by default in the config file.

ryokousha wrote:btw. Marek told on discord he has a proof it is in T&E(3), so I was expecting that.

As he doesn't have a solver, I guess he used SudoRules. There's no way one could find manually a proof in T&E(3).

ryokousha wrote:He also gave an elegant proof of impossibility based on a senior exocet and two possible resulting bivalue odddagons.

In terms of complexity, I don't think this is better than T&E(3). I'm waiting to see it published on a public site.

Thank you. Marek just educated me on the same thing.
I'll run it again with all the stuff deactivated. Sorry I'm new to CSP-Rules and frankly don't understand much of the terminology yet.

For Marek's proof, he did not claim anything for the T&E depth of the senior exocet proof. He might speak for himself on the proof that the pattern is in T&E(3).

Edit: It is indeed in T&E(BRT, 3), but not in T&E(BRT, 2).

denis_berthier wrote:

ryokousha wrote:btw. Marek told on discord he has a proof it is in T&E(3), so I was expecting that.

As he doesn't have a solver, I guess he used SudoRules. There's no way one could find manually a proof in T&E(3).

I'll take it as a compliment.
Knowing about the exocet made it quite easy, actually.

(After the quads (which are themselves in T&E(3))
Depth 1 and 2: 1r7c5 2r7c6 (no loss of generality here).
The finish on depth 3 was quite lengthy, I'll only write the sequence of candidates which (if I didn't make a mistake) break with singles:
3r3c4, 4r3c4, 3r5c4, 4r5c4, 1r6c9, 2r6c9, 1r3c1, 2r3c1, 3r6c1, 4r6c1, 3r3c7, 4r3c7, 1r3c2, 2r3c2, 3r5c2, 4r5c2, 1r6c2, 2r6c2, 3r6c2, 4r6c2
no digit left in r6c2

As there was no loss of generality at depth 1 and 2, analogous proofs exist for other options at these depths.

What isn't feasible manually is to proof whether the pattern was also in T&E(2), all I could say was that it seemed unlikely.
(Had I actually used a solver, this wouldn't have been an issue.)

Marek

marek stefanik wrote:

denis_berthier wrote:

ryokousha wrote:btw. Marek told on discord he has a proof it is in T&E(3), so I was expecting that.

As he doesn't have a solver, I guess he used SudoRules. There's no way one could find manually a proof in T&E(3).

I'll take it as a compliment.

I was talking of a direct proof in T&E(3). But anyway, your proof is smart.
I can't see any exocet in it.

Here is the exocet proof:

Code: Select all

         1234           1234                  1234
.------------------.------------------.------------------.
| .     .     .    | .     .     .    | .     .     .    |
| .     .     .    | .     .     .    | .     .     .    |
| 1234  1234  .    | 1234  .     .    | 1234  .     .    |  \1234
:------------------+------------------+------------------:
| .     .     .    | .     .     .    |T1234  .     .    |
| .     1234  .    | 1234  .     .    | 1234  .     .    |  \1234
| 1234 T1234  .    | .     1234  .    | .     .     1234 |
:------------------+------------------+------------------:
| .     1234  .    | .    B1234 B1234 | 1234  .     .    |
| 1234  .     .    | 1234  .     .    | .     .     .    |
| 1234  .     .    | 1234  .     .    | .     .     .    |
'------------------'------------------'------------------'

senior exocet base (1234)r7c56, targets r4c7 r6c2, cross-lines c247, cover houses r35
(Note that the cross-lines contain 1234 quadruples, therefore each of them must appear in the marked cells)

WLOG, let the digit in r4c7 be 1 and the digit in r6c2 2.
Base cells are restricted to 12, cover-house elims 12r3c1, pairs in b8.

Code: Select all

.------------------.------------------.------------------.
| .     .     .    | .     .     .    | .     .     .    |
| .     .     .    | .     .     .    | .     .     .    |
| 34    134   .    | 12    .     .    | 234   .     .    |
:------------------+------------------+------------------:
| .     .     .    | .     .     .    | 1     .     .    |
| .     134   .    | 12    .     .    | 234   .     .    |
| 134   2     .    | .     134   .    | .     .     34   |
:------------------+------------------+------------------:
| .     34    .    | .     12    12   | 34    .     .    |
| 1234  .     .    | 34    .     .    | .     .     .    |
| 1234  .     .    | 34    .     .    | .     .     .    |
'------------------'------------------'------------------'

Suppose r3c4=1:
singles: 1c2, 2c4 (in full quads)

Code: Select all

.------------------.------------------.------------------.
| .     .     .    | .     .     .    | .     .     .    |
| .     .     .    | .     .     .    | .     .     .    |
|#34   #34    .    | 1     .     .    | 234   .     .    |
:------------------+------------------+------------------:
| .     .     .    | .     .     .    | 1     .     .    |
| .     1     .    | 2     .     .    |#34    .     .    |
|#34    2     .    | .     134   .    | .     .    #34   |
:------------------+------------------+------------------:
| .    #34    .    | .     12    12   |#34    .     .    |
| 1234  .     .    | 34    .     .    | .     .     .    |
| 1234  .     .    | 34    .     .    | .     .     .    |
'------------------'------------------'------------------'

#-marked cells are a bivalue oddagon, ie. contra.

Therefore r3c4=2:
singles: 1c4, 1r6 (in full quads)

Code: Select all

.------------------.------------------.------------------.
| .     .     .    | .     .     .    | .     .     .    |
| .     .     .    | .     .     .    | .     .     .    |
|#34    134   .    | 2     .     .    |#34    .     .    |
:------------------+------------------+------------------:
| .     .     .    | .     .     .    | 1     .     .    |
| .     34    .    | 1     .     .    | 234   .     .    |
| 1     2     .    | .     34    .    | .     .     34   |
:------------------+------------------+------------------:
| .    #34    .    | .     12    12   |#34    .     .    |
|#234   .     .    | 34    .     .    | .     .     .    |
|#234   .     .    | 34    .     .    | .     .     .    |
'------------------'------------------'------------------'

#-marked cells contain a 2 in b7 and a bivalue oddagon, ie. contra.

The pattern is not 4-chromatic.

Marek

Nice.

Interesting patterns, though i guess not relevant in solving real sudokus. But who knows, it woudn't be my first wrong sudoku guess

.
I agree that such patterns are very unlikely to yield real sudoku puzzles.

However, using SudoRules function "solve-n-grids-after-first-p-from-k-digit-pattern-string-file", I've done some calculations that show notable differences between them.
In Ryokousha's above list of 30 4-digit patterns, 16 can be proved contradictory in the restricted version of T&E(3) that relies only on the k-cells: 1 2 3 4 5 6 7 9 10 11 12 13 14 19 21 26
This may suggest that the rest would lead to potentially harder puzzles (if they had any puzzle at all - which remains the big question in all this thread).