The New Sudoku Players' Forum

by **coloin** » Thu Aug 15, 2013 8:58 pm

This is a follow-on post to ask for patterns that they dont have puzzles here

A while ago i posted here on various patterns of clues which dont have puzzles.
Somewhat unsatisfactorily proof was distinctly lacking however.
So this thread takes it furthur - if it is possible.

Serg and blue have taken careful work to tabulate patterns which cant have puzzles with proof.
one clue box patterns
investigation of one band free patterns
investigation of one crossing free patterns

Other relevant threads
minimal patterns
number of non-equivalent patterns having n clues
number of minimal puzzles per ed valid pattern with n clues

Proof that patterns dont have puzzles is established either by
iterating through all possible ED options for the clues
or
showing that all ways to fill the empty spaces in a puzzle will always have an unavoidable set not hit by a clue.

Potential patterns can be disregarded if they are solely composed of clues from proven invalid maximal patterns.

3 Invalid patterns

1.Trivially this was first done with this pattern which needs 1 clue in 2 rows [always at least 1 UA]
2.Three empty box pattern was shown - to require one clue. [always at least 1 UA]here.
3.this also means that the four box pattern therefore requires at least two clues and this is indeed the case. [always at least 2 UAs]

Code: Select all: Maximal invalid pattern #1.+---+---+---+ #2.+---+---+---+ |...|...|...| |...|...|xxx| |...|...|...| |...|...|xxx| |xxx|xxx|xxx| |...|...|xxx| +---+---+---+ +---+---+---+ |xxx|xxx|xxx| |...|xxx|xxx| |xxx|xxx|xxx| |...|xxx|xxx| |xxx|xxx|xxx| |...|xxx|xxx| +---+---+---+ +---+---+---+ |xxx|xxx|xxx| |xxx|xxx|xxx| |xxx|xxx|xxx| |xxx|xxx|xxx| |xxx|xxx|xxx| |xxx|xxx|xxx| +---+---+---+ +---+---+---+ Valid puzzle example with one added clue 1.+---+---+---+ 2.+---+---+---+ |...|...|..6| |7..|...|298| |...|...|...| |...|...|536| |123|456|789| |...|...|471| +---+---+---+ +---+---+---+ |812|547|963| |...|981|623| |674|293|518| |...|364|857| |539|861|274| |...|572|914| +---+---+---+ +---+---+---+ |756|938|421| |123|456|789| |298|174|635| |678|293|145| |341|625|897| |495|817|362| +---+---+---+ +---+---+---+ Valid puzzle example with two added clues +---+---+---+ +---+---+---+ |...|...|xxx| |5..|...|672| |...|...|xxx| |...|...|134| |...|...|xxx| |...|...|895| +---+---+---+ +---+---+---+ |...|...|xxx| |...|9..|428| |...|...|xxx| |...|...|517| |...|...|xxx| |...|...|963| +---+---+---+ +---+---+---+ |xxx|xxx|xxx| |123|456|789| |xxx|xxx|xxx| |749|218|356| |xxx|xxx|xxx| |658|379|241| +---+---+---+ +---+---+---+ Maximal invalid pattern #3.+---+---+---+ |x..|x..|xxx| |...|...|xxx| |...|...|xxx| +---+---+---+ |...|...|xxx| |...|...|xxx| |...|...|xxx| +---+---+---+ |xxx|xxx|xxx| |xxx|xxx|xxx| |xxx|xxx|xxx| +---+---+---+

4.Red Ed classically
showed that this pattern would always have an uncovered unavoidable set [UA].
The computation was made many times easier using the fact that the empty area had many planes of symmetry.

Code: Select all: +---+---+---+ +---+---+---+ |xxx|xxx|xxx| |...|..x|..x| |xxx|...|xxx| |...|..x|..x| |xxx|...|xxx| |..x|..x|..x| +---+---+---+ +---+---+---+ |x..|...|..x| |...|xxx|xxx| |x..|.x.|..x| -> |...|xxx|xxx| |x..|...|..x| |xxx|xxx|xxx| +---+---+---+ +---+---+---+ |xxx|...|xxx| |...|xxx|xxx| |xxx|...|xxx| |...|xxx|xxx| |xxx|xxx|xxx| |xxx|xxx|xxx| +---+---+---+ +---+---+---+ [morph]

a variation produced similarly is maximal......with no clue in central box

Code: Select all: +---+---+---+ +---+---+---+ |xxx|xxx|xxx| |...|..x|.xx| |xxx|...|xxx| |...|..x|.xx| |xxx|...|xxx| |...|..x|.xx| +---+---+---+ +---+---+---+ |x..|...|.xx| |...|xxx|xxx| |x..|...|.xx| -> |...|xxx|xxx| |x..|...|.xx| |xxx|xxx|xxx| +---+---+---+ +---+---+---+ |xxx|...|xxx| |...|xxx|xxx| |xxx|xxx|xxx| |xxx|xxx|xxx| |xxx|xxx|xxx| |xxx|xxx|xxx| +---+---+---+ +---+---+---+ [morph]

3 clues in the 49 cells cant therefore give valid puzzles

Code: Select all: +---+---+---+ |...|..x|.xx| |...|...|.xx| |...|...|.xx| +---+---+---+ |...|...|.xx| |...|...|.xx| |x..|..x|.xx| +---+---+---+ |...|...|.xx| |xxx|xxx|xxx| |xxx|xxx|xxx| +---+---+---+

4 clues in the 49 empty cells are can give valid puzzles

But these 2 ED ways can be shown to be invalid

Code: Select all: +---+---+---+ +---+---+---+ |x..|x..|.xx| |x..|.x.|.xx| |...|...|.xx| |...|...|.xx| |...|...|.xx| |...|...|.xx| +---+---+---+ +---+---+---+ |x..|x..|.xx| |x..|x..|.xx| |...|...|.xx| |...|...|.xx| |...|...|.xx| |...|...|.xx| +---+---+---+ +---+---+---+ |...|...|.xx| |...|...|.xx| |xxx|xxx|xxx| |xxx|xxx|xxx| |xxx|xxx|xxx| |xxx|xxx|xxx| +---+---+---+ +---+---+---+ [blue]

here
And these 4 other ED ways can be shown to have valid puzzles [blue]

Code: Select all: +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ |x..|.x.|.xx| |x..|x..|.xx| |x..|.x.|.xx| |x..|...|.xx| |...|...|.xx| |...|...|.xx| |...|...|.xx| |...|.x.|.xx| |...|...|.xx| |...|...|.xx| |...|...|.xx| |...|...|.xx| +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ |...|x..|.xx| |...|x..|.xx| |.x.|x..|.xx| |...|x..|.xx| |x..|...|.xx| |x..|...|.xx| |...|...|.xx| |.x.|...|.xx| |...|...|.xx| |...|...|.xx| |...|...|.xx| |...|...|.xx| +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ |...|...|.xx| |...|...|.xx| |...|...|.xx| |...|...|.xx| |xxx|xxx|xxx| |xxx|xxx|xxx| |xxx|xxx|xxx| |xxx|xxx|xxx| |xxx|xxx|xxx| |xxx|xxx|xxx| |xxx|xxx|xxx| |xxx|xxx|xxx| +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+

Finally blue also easily proved that a crossing pattern with 2 rows and 2 columns
was shown to always need more than one clue [always at 2 least UAs] and his methods gave rise to many other maximal patterns.

Code: Select all: +---+---+---+ +---+---+---+ |...|...|...| |2..|...|...| |...|...|...| |.6.|...|...| |..x|xxx|xxx| |..4|861|792| +---+---+---+ +---+---+---+ |..x|xxx|xxx| |..9|123|846| |..x|xxx|xxx| |..2|456|379| |..x|xxx|xxx| |..6|789|215| +---+---+---+ +---+---+---+ |..x|xxx|xxx| |..1|937|528| |..x|xxx|xxx| |..3|548|167| |..x|xxx|xxx| |..5|612|934| +---+---+---+ +---+---+---+ needs 2 clues

More to follow

by **coloin** » Thu Aug 15, 2013 8:59 pm

Here are the patterns which have been proven.

These patterns need at least 1 clue added

Code: Select all: Needs 1 clue Needs 1 clue Needs 1 clue +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ |...|...|...| |...|...|xxx| |...|...|xxx| |123|...|495| |...|...|...| |...|...|xxx| |...|...|xxx| |456|...|783| |xxx|xxx|xxx| |...|...|xxx| |...|...|xxx| |789|...|612| +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ |xxx|xxx|xxx| |...|xxx|xxx| |...|xxx|...| |...|143|...| |xxx|xxx|xxx| |...|xxx|xxx| |...|xxx|...| |...|657|...| |xxx|xxx|xxx| |...|xxx|xxx| |...|xxx|...| |...|829|...| +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ |xxx|xxx|xxx| |xxx|xxx|xxx| |xxx|...|xxx| |...|...|879| |xxx|xxx|xxx| |xxx|xxx|xxx| |xxx|...|xxx| |.9.|...|354| |xxx|xxx|xxx| |xxx|xxx|xxx| |xxx|...|xxx| |...|...|126| +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ [JPF]

These patterns need at least 2 clues added

Code: Select all: +---+---+---+ +---+---+---+ +---+---+---+ |...|...|...| |...|...|...| |...|...|xxx| |...|...|...| |...|...|...| |...|...|xxx| |...|...|...| |..x|xxx|xxx| |...|...|xxx| +---+---+---+ +---+---+---+ +---+---+---+ |xxx|xxx|xxx| |..x|xxx|xxx| |...|...|xxx| |xxx|xxx|xxx| |..x|xxx|xxx| |...|...|xxx| |xxx|xxx|xxx| |..x|xxx|xxx| |...|...|xxx| +---+---+---+ +---+---+---+ +---+---+---+ |xxx|xxx|xxx| |..x|xxx|xxx| |xxx|xxx|xxx| |xxx|xxx|xxx| |..x|xxx|xxx| |xxx|xxx|xxx| |xxx|xxx|xxx| |..x|xxx|xxx| |xxx|xxx|xxx| +---+---+---+ +---+---+---+ +---+---+---+

These patterns need at least 3 clues added

Code: Select all: +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ |...|...|...| |.1.|...|...| |...|...|...| |...|...|...| |...|...|..x| |...|...|...| |...|.9.|5..| |...|...|..x| |...|...|..x| |...|..x|...| |...|...|...| |...|...|...| |...|..x|...| |..x|...|...| |..x|...|...| +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ |...|xxx|xxx| |...|978|324| |...|xxx|xxx| |...|xxx|xxx| |...|xxx|xxx| |...|xxx|xxx| |...|625|971| |xxx|xxx|xxx| |...|xxx|xxx| |...|xxx|xxx| |...|xxx|xxx| |...|314|856| |xxx|xxx|xxx| |xxx|xxx|xxx| |...|xxx|xxx| +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ |xxx|xxx|xxx| |123|456|789| |xxx|xxx|xxx| |xxx|xxx|xxx| |...|xxx|xxx| |xxx|xxx|xxx| |745|189|632| |xxx|xxx|xxx| |xxx|xxx|xxx| |xxx|xxx|xxx| |xxx|xxx|xxx| |689|237|415| |xxx|xxx|xxx| |xxx|xxx|xxx| |xxx|xxx|xxx| +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ invalid patterns [Serg] +---+---+---+ +---+---+---+ +---+---+---+ |...|...|xxx| |592|...|...| |...|...|xxx| |...|...|xxx| |471|...|...| |...|...|xxx| |...|...|xxx| |683|...|...| |...|...|xxx| +---+---+---+ +---+---+---+ +---+---+---| |...|xxx|...| |...|367|...| |...|xxx|...| |...|xxx|...| |...|189|.7.| |.x.|xxx|...| |...|xxx|...| |1..|425|...| |...|xxx|...| +---+---+---+ +---+---+---+ +---+---+---+ |xxx|...|...| |...|...|827| |xxx|...|...| |xxx|...|...| |...|...|956| |xxx|...|...| |xxx|...|...| |...|2..|314| |xxx|.xx|...| +---+---+---+ +---+---+---+ valid 3plus27 puzzle, +---+---+---+ maximal invalid pattern [JPF] I generated all the ED 237083 ways to fill B1B5B9. There was no puzzle adding 2 clues. On adding 3 clues to approx 1/3 of all the 237083 B1B5B9there were 200 27plus3 puzzles, so probably there are around 600 of such 27plus3 puzzles. [Proved now that there are 684]

These patterns need at least 4 clues added

Code: Select all: 4.1 +---+---+---+ +---+---+---+ |...|...|...| |...|.1.|...| |...|...|...| |.2.|...|...| |...|...|...| |...|3..|...| +---+---+---+ +---+---+---+ |...|...|...| |..3|...|...| |...|...|...| |...|...|...| |xxx|xxx|xxx| |814|795|632| +---+---+---+ +---+---+---+ |xxx|xxx|xxx| |147|256|389| |xxx|xxx|xxx| |258|139|467| |xxx|xxx|xxx| |369|478|125| +---+---+---+ needs 4 clues +---+---+---+ valid 36plus4 -blue there are lots of them ... (> 34000). This one came from a "27+8" with a 4-clue row. Fixing the clues in the first 5 rows.... It has 280 similar ways to rotate the 36 clues - Its difficult to choose the 36clues - so the above way is the best way to find them. It is the minimum - If 3 clues are in band 1, 1 clue is needed in rows 4&5 as we have here, If 2 clues are in band 1, it looks like 4 clues are needed in rows 4&5. 4.2 +---+---+---+ +---+---+---+ |...|...|.xx| |...|..4|.31| |...|...|.xx| |.9.|...|.82| |...|...|.xx| |...|...|.59| +---+---+---+ +---+---+---+ |...|...|.xx| |...|...|.26| |...|...|.xx| |...|.5.|.98| |...|...|.xx| |3..|...|.47| +---+---+---+ +---+---+---+ |...|...|.xx| |...|...|.14| |xxx|xxx|xxx| |158|497|263| |xxx|xxx|xxx| |429|613|875| +---+---+---+ +---+---+---+ 4 ED patterns [out of the 6 are valid] [blue]

These patterns need at least 5 clues added

Code: Select all: This Needs 5 clues... but If empty box 1 needs 7 clues +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ |...|...|...| |1..|..2|...| |1..|.2.|...| |...|.1.|...| |...|...|...| |...|...|..3| |...|...|.3.| |...|2..|.3.| |...|...|...| |.4.|...|...| |...|...|...| |...|...|...| +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ |...|xxx|xxx| |...|293|651| |...|862|574| |.1.|653|948| |...|xxx|xxx| |...|654|987| |..4|735|189| |..3|481|672| |...|xxx|xxx| |.5.|781|432| |...|491|362| |...|729|351| +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ |...|xxx|xxx| |...|176|329| |3..|216|895| |4..|578|193| |...|xxx|xxx| |...|529|148| |.5.|384|217| |.5.|192|864| |...|xxx|xxx| |...|438|576| |...|957|643| |...|364|527| +---+---+---+ +---+---+---+ 5 +---+---+---+ 6 +---+---+---+ 7

This pattern needs at least 7 clues added

Code: Select all: +---+---+---+ +---+---+---+ |...|...|...| |...|...|...| |...|...|...| |...|...|..1| |...|...|...| |...|.23|...| +---+---+---+ +---+---+---+ |...|...|...| |...|...|...| |...|...|...| |...|4..|..5| |...|...|...| |.26|...|...| +---+---+---+ +---+---+---+ |xxx|xxx|xxx| |4..|..2|.3.| |xxx|xxx|xxx| |5.3|..6|.78| |xxx|xxx|xxx| |8..|1..|6..| +---+---+---+ +---+---+---+ 18C puzzle with 7 clues in the first 2 bands

The initial 27plus4plus3 was found by champagne here and all 27plus4plus3 were identified.

Thise pattern needs at least 12 clues added

Code: Select all: Adding 12 clues to B4578 is never enough +---+---+---+ |...|...|xxx| |...|...|xxx| |...|...|xxx| +---+---+---+ |yyy|yyy|...| |yyy|yyy|...| |yyy|yyy|...| +---+---+---+ |yyy|yyy|...| |yyy|yyy|...| |yyy|yyy|...| +---+---+---+ +---+---+---+ |...|...|128| |...|...|345| |...|...|967| +---+---+---+ |.2.|...|...| |.64|.7.|...| |...|.53|...| +---+---+---+ |38.|...|...| |6..|2..|...| |...|461|...| +---+---+---+ Valid 9plus13 verified by exhaustive search by blue that 9plus12 didn't exist

And the big one of course proved again by McQuire and verified by blue/champagne that an empty grid needs 17 clues

Code: Select all: +---+---+---+ |...|...|...| |...|...|...| |...|...|...| +---+---+---+ |...|...|...| |...|...|...| |...|...|...| +---+---+---+ |...|...|...| |...|...|...| |...|...|...| +---+---+---+ , no 16C exists All 49158 17C puzzles [ and no more] was proved by champagne

by **coloin** » Thu Aug 15, 2013 9:03 pm

And these are ? unproven patterns with n clues to be added - in order of possible ease !
Probably they are all correct ! Apologies if they have indeed been proven in former posts.....

The fact that we hav not got proof probably means that it is not an easy task !

Code: Select all: Adding 1 clue is never enough 1+---+---+---+ +---+---+---+ |xxx|xxx|xxx| |982|356|174| |x..|...|..x| |7..|...|..8| |x..|...|..x| |3..|...|..6| +---+---+---+ +---+---+---+ |x..|...|..x| |1..|...|..2| |x..|...|..x| |2.9|...|..3| |x..|...|..x| |4..|.1.|..5| +---+---+---+ +---+---+---+ |x..|...|..x| |5..|...|..7| |x..|...|..x| |8..|...|..9| |xxx|xxx|xxx| |673|289|541| +---+---+---+ +---+---+---+ valid 32plus2 puzzle [jovi_al01] EDIT this is proven as its the basic magic 40 pattern by red ed above

Code: Select all: Adding 2 clues is never enough ? 2+---+---+---+ +---+---+---+ |xxx|xxx|xxx| |123|456|789| |xxx|xxx|xxx| |476|298|153| |...|...|...| |...|...|...| +---+---+---+ +---+---+---+ |xxx|xxx|xxx| |795|682|341| |xxx|xxx|xxx| |864|135|297| |...|...|...| |...|...|...| +---+---+---+ +---+---+---+ |...|...|...| |.3.|7..|...| |...|...|...| |...|...|5..| |...|...|...| |...|...|...| +---+---+---+ +---+---+---+ valid 36plus3 puzzle EDIT this is proven as 2 clues in a band cant have an empty 3-tuple in the 2nd band]

Code: Select all: Adding 3 clues is never enough ? 3+---+---++--- +---+---+---+ |...|...|...| |.9.|..5|...| |...|...|...| |...|...|...| |...|...|...| |2..|...|...| +---+---+---+ +---+---+---+ |...|...|xxx| |...|...|295| |...|...|xxx| |...|...|831| |...|...|xxx| |...|9..|467| +---+---+---+ +---+---+---+ |xxx|xxx|xxx| |123|456|789| |xxx|xxx|xxx| |968|712|354| |xxx|xxx|xxx| |574|839|126| +---+---+---+ +---+---+---+ valid 36plus4 puzzle 4+---+---+---+ +---+---+---+ |...|...|...| |.3.|..2|...| |...|...|...| |...|...|..4| |...|...|...| |...|...|..5| +---+---+---+ +---+---+---+ |...|xxx|...| |...|123|...| |...|xxx|...| |...|456|...| |...|xxx|...| |...|789|...| +---+---+---+ +---+---+---+ |xxx|...|xxx| |195|...|348| |xxx|...|xxx| |284|...|756| |xxx|...|xxx| |376|...|219| +---+---+---+ +---+---+---+ valid 27plus4 puzzle [JPF] 5+---+---+---+ +---+---+---+ |...|...|..,| |...|...|...| |...|...|..,| |...|1..|...| |...|...|..,| |23.|...|...| +---+---+---+ +---+---+---+ |...|...|xxx| |...|.4.|562| |...|...|xxx| |...|...|731| |...|...|xxx| |...|...|849| +---+---+---+ +---+---+---+ |xxx|xxx|xxx| |678|921|453| |xxx|xxx|xxx| |451|837|926| |xxx|xxx|xxx| |923|465|178| +---+---+---+ +---+---+---+ valid 36plus4 puzzle [JPF] 6+---+---+---+ +---+---+---+ |xxx|...|...| |123|...|...| |xxx|...|...| |456|...|...| |xxx|...|...| |789|...|...| +---+---+---+ +---+---+---+ |...|...|...| |...|.5.|...| |...|...|...| |..2|...|..1| |...|...|...| |...|.4.|...| +---+---+---+ +---+---+---+ |...|xxx|xxx| |...|784|539| |...|xxx|xxx| |...|293|617| |...|xxx|xxx| |...|165|428| +---+---+---+ +---+---+---+ valid 27plus4 puzzle [JPF] +---+---+---+ +---+---+---+ |xxx|xxx|xxx| |123|456|789| |xxx|...|...| |564|...|...| |xxx|...|...| |789|...|...| +---+---+---+ +---+---+---+ |x..|...|...| |4..|...|...| |...|x.x|...| |...|2.8|...| |...|...|..x| |...|...|..1| +---+---+---+ +---+---+---+ |...|...|xxx| |...|...|912| |...|...|xxx| |...|...|374| |xxx|xxx|xxx| |912|734|568| +---+---+---+ +---+---+---+ valid 30plus4 puzzle

Code: Select all: Adding 4 clues is never enough ? 7+---+---+---+ +---+---+---+ +---+---+---+ |x..|...|..x| |9..|...|..7| |2..|...|..8| |x..|...|..x| |3..|87.|..2| |7..|3.9|..6| |x..|...|..x| |64.|...|..3| |5..|...|..1| +---+---+---+ +---+---+---+ +---+---+---+ |x..|...|..x| |46.|...|..8| |6..|.8.|..7| |x..|...|..x| |2..|.3.|..1| |3..|...|..2| |x..|...|..x| |5..|...|..4| |4.9|...|3.5| +---+---+---+ +---+---+---+ +---+---+---+ |x..|...|..x| |7..|...|..6| |8..|...|..4| |x..|...|..x| |8..|...|..5| |9..|...|..3| |xxx|xxx|xxx| |123|456|789| |123|456|789| +---+---+---+ +---+---+---+ +---+---+---+ valid 25plus5 clue 8+---+---+---+ +---+---+---+ |xxx|xxx|xxx| |123|456|789| |...|...|...| |...|...|..1| |...|...|...| |...|.9.|...| +---+---+---+ +---+---+---+ |xxx|xxx|xxx| |891|243|567| |...|...|...| |4..|...|...| |...|...|...| |...|...|9..| +---+---+---+ +---+---+---+ |...|...|...| |...|..1|...| |...|...|...| |...|...|...| |xxx|xxx|xxx| |965|872|413| +---+---+---+ +---+---+---+ valid 27plus5 clues [only one found] :!: :!: EDIT many can be found... so perhaps a plus 4 exists ! :oops:

Code: Select all: Adding 5 clues is never enough ? 9+---+---+---+ |...|...|...| |...|...|...| |...|...|...| +---+---+---+ |...|...|xxx| |...|...|xxx| |...|...|xxx| +---+---+---+ |...|xxx|xxx| |...|xxx|xxx| |...|xxx|xxx| +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ |72.|...|...| |...|.8.|...| |...|...|...| |...|..3|...| |...|5..|...| |..5|...|...| |1..|7..|...| |.65|...|...| |..6|...|...| |2.7|...|...| |.26|...|...| |..7|...|...| +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ |...|...|217| |...|5..|197| |..8|...|197| |8..|...|214| |..4|3..|685| |...|...|635| |...|.2.|685| |...|...|678| |...|...|394| |6..|...|284| |...|...|324| |...|...|395| +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ |...|485|963| |...|821|963| |...|487|961| |...|754|963| |...|971|852| |...|764|852| |...|163|852| |3..|169|852| |...|632|741| |...|935|471| |...|952|743| |...|832|741| +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ |...|6..|...| |...|69.|...| |9.2|...|...| |3..|...|...| |3..|...|...| |74.|...|...| +---+---+---+ +---+---+---+ |.6.|...|189| |...|...|317| |.8.|...|675| |..6|...|295| |...|...|324| |...|...|684| +---+---+---+ +---+---+---+ |...|514|963| |...|821|963| |...|793|852| |...|764|852| |...|862|741| |...|953|741| +---+---+---+ +---+---+---+ valid 27plus6 puzzles, with various empty boxes - all JPF

Code: Select all: Adding 6 clues is never enough ? 10+---+---+---+ +---+---+---+ |...|...|..x| |...|..7|..1| |...|...|..x| |5..|.4.|..2| |...|...|..x| |...|...|..3| +---+---+---+ +---+---+---+ |...|...|..x| |.1.|3..|..4| |...|...|..x| |...|1..|..5| |...|...|..x| |2..|...|..6| +---+---+---+ +---+---+---+ |...|...|xxx| |...|...|367| |...|...|xxx| |...|...|258| |xxx|xxx|xxx| |763|852|149| +---+---+---+ +---+---+---+ valid 21plus7 An almost complete search by blue found 1400 21plus7s. I couldnt find anymore than 1374 - making a 21plus6 very very unlikely [there would be many 21plus6plus1s - which wernt found ]

Code: Select all: Adding 7 clues is never enough ? 11+---+---+---+ +---+---+---+ |xxx|xxx|xxx| |123|456|789| |...|...|...| |...|...|..1| |...|...|...| |...|3..|...| +---+---+---+ +---+---+---+ |...|...|...| |...|.71|...| |...|...|...| |...|...|...| |...|...|...| |..6|...|4..| +---+---+---+ +---+---+---+ |...|...|...| |.7.|...|...| |...|...|...| |...|...|6..| |xxx|xxx|xxx| |518|692|347| +---+---+---+ +---+---+---+ valid 18plus8 12+---+---+---+ +---+---+---+ +---+---+---+ |xxx|...|...| |647|3..|1..| |123|..7|...| |xxx|...|...| |831|...|4..| |456|...|.9.| |xxx|...|...| |529|...|...| |789|...|...| +---+---+---+ +---+---+---+ +---+---+---+ |...|xxx|...| |.6.|123|...| |...|284|...| |...|xxx|...| |...|456|...| |...|396|..5| |...|xxx|...| |...|789|...| |2..|751|...| +---+---+---+ +---+---+---+ +---+---+---+ |...|...|...| |.1.|...|...| |...|...|.2.| |...|...|...| |...|...|.9.| |.1.|...|7..| |...|...|...| |...|...|.58| |...|.4.|...| +---+---+---+ +---+---+---+ +---+---+---+ [JPF] valid 18plus8 13+---+---+---+ +---+---+---+ |...|...|..x| |.8.|.6.|..1| |...|...|..x| |..5|...|..2| |...|...|..x| |...|...|..3| +---+---+---+ +---+---+---+ |...|...|..x| |...|.1.|..4| |...|...|..x| |..3|7..|..5| |...|...|..x| |...|...|..6| +---+---+---+ +---+---+---+ |...|...|..x| |.6.|...|..7| |...|...|..x| |...|3..|..8| |xxx|xxx|xxx| |147|285|369| +---+---+---+ +---+---+---+ only 3 17plus8s found Confirmed by blue - and they have rotational symmetry +-------+-------+-------+ +-------+-------+-------+ +-------+-------+-------+ | . . . | . 4 . | . . . | | . . . | . 4 . | . . . | | . . . | . 4 . | . . . | | . . . | . 2 . | 1 . . | | . . . | . 2 . | 1 . . | | . . . | . 2 . | 1 . . | | . . 6 | . 9 . | . 3 . | | . . 6 | . 9 . | . 3 . | | . . 6 | . 9 . | . 7 . | +-------+-------+-------+ +-------+-------+-------+ +-------+-------+-------+ | . . . | . 7 . | . . 4 | | . . . | . 7 . | . 6 . | | . . . | . 7 . | . 6 . | | 1 2 3 | 4 5 6 | 7 8 9 | | 1 2 3 | 4 5 6 | 7 8 9 | | 1 2 3 | 4 5 6 | 7 8 9 | | 6 . . | . 3 . | . . . | | . 4 . | . 3 . | . . . | | . 4 . | . 3 . | . . . | +-------+-------+-------+ +-------+-------+-------+ +-------+-------+-------+ | . 7 . | . 1 . | 4 . . | | . 7 . | . 1 . | 4 . . | | . 3 . | . 1 . | 4 . . | | . . 9 | . 8 . | . . . | | . . 9 | . 8 . | . . . | | . . 9 | . 8 . | . . . | | . . . | . 6 . | . . . | | . . . | . 6 . | . . . | | . . . | . 6 . | . . . | +-------+-------+-------+ +-------+-------+-------+ +-------+-------+-------+ ....4........2.1....6.9..3.....7...41234567896...3.....7..1.4....9.8........6.... ....4........2.1....6.9..3.....7..6.123456789.4..3.....7..1.4....9.8........6.... ....4........2.1....6.9..7.....7..6.123456789.4..3.....3..1.4....9.8........6....

Code: Select all: Adding 8 clues is never enough ? 14 +---+---+---+ +---+---+---+ |...|...|...| |...|...|...| |...|...|...| |...|12.|...| |...|...|...| |.38|...|...| +---+---+---+ +---+---+---+ |...|...|...| |...|...|2..| |...|...|...| |...|..3|...| |...|...|...| |..3|9.8|...| +---+---+---+ +---+---+---+ |...|...|xxx| |...|...|123| |...|...|xxx| |...|...|456| |xxx|xxx|xxx| |126|345|789| +---+---+---+ +---+---+---+ valid 15plus9 [blue] Only 3 15plus9s of this pattern were found initially 123456789456......789..................6.1....9......5.4..8..........6........3.1 123456789456......789.......4.......6............9..1.........4.3..8..........6.1 123456789456......789.......4.......6............9..1.......4...3..8..........6.1 A 4th one subsequently found independantly by coloin and blue which has a different non-repeating 15 clue base This must make the chances of finding any more very slim 123456789457......896.....................16.....89......6........1.36...8....... [ morphed above] 15+---+---+---+ +---+---+---+ |...|...|...| |...|...|...| |...|...|...| |...|..6|..4| |...|...|...| |.87|...|...| +---+---+---+ +---+---+---+ |...|...|...| |3..|...|...| |...|...|...| |...|.8.|2..| |...|...|...| |6..|...|..1| +---+---+---+ +---+---+---+ |...|xxx|xxx| |...|694|123| |...|xxx|xxx| |...|873|456| |...|xxx|xxx| |...|521|789| +---+---+---+ +---+---+---+ valid 18plus9 puzzle 16+---+---+---+ +---+---+---+ |XXX|XXX|XXX| |123|456|789| |XXX|XXX|XXX| |476|298|153| |...|...|...| |...|...|.6.| +---+---+---+ +---+---+---+ |...|...|...| |..5|.8.|...| |...|...|...| |...|1..|2.7| |...|...|...| |...|...|...| +---+---+---+ +---+---+---+ |...|...|...| |..9|...|...| |...|...|...| |...|7.1|...| |...|...|...| |...|...|...| +---+---+---+ +---+---+---+ valid 18plus9 puzzle

Code: Select all: Adding 11 clues is never enough ? 17+---+---+---+ 18+---+---+---+ |...|...|...| |xxx|xxx|xxx| |...|...|...| |...|...|...| |...|...|...| |...|...|...| +---+---+---+ +---+---+---+ |...|xxx|...| |...|...|...| |...|xxx|...| |...|...|...| |...|xxx|...| |...|...|...| +---+---+---+ +---+---+---+ |...|...|...| |...|...|...| |...|...|...| |...|...|...| |...|...|...| |...|...|...| +---+---+---+ +---+---+---+ only 9plus12s have been found

see 9plus12 game

by **coloin** » Thu Aug 15, 2013 9:25 pm

Actually on reading eleven's post here where he proved that the map

Code: Select all: 111 112 999

does not have valid puzzle
On furthur thinking ......EDIT
also

Code: Select all: 011 299 999

does not have a valid puzzle

But before we can say

Code: Select all: 9+---+---+---+ |...|...|...| |...|...|...| |...|...|...| +---+---+---+ |...|...|...| |...|...|...| |...|...|...| +---+---+---+ |xxx|xxx|xxx| |xxx|xxx|xxx| |xxx|xxx|xxx| +---+---+---+ Adding 7 clues will not give a valid puzzle - EDIt - a few and actually all of the possible 27plus7 puzzles have actually been found

i reckon one would actually need to prove
EDIT rather a lot more than i have shown here .......see later post !

Code: Select all: 012 012 012 022 013 004 211 121 112 111 111 111 999 999 999 999 999 999

C

by **Serg** » Fri Aug 16, 2013 4:03 pm

Hi, coloin!
You consider rather interesting classes of patterns, but, I think, proof of these conjectures would have limited practical usage. For example, knowlege of all maximal patterns having 2 free bands (the 3rd band must consist of boxes containing 9 clues each; I think there should be several hundreds of such patterns) will be (I think) much more effective than rule "Each 2 bands of any valid puzzle must contain more 7 clues". (Maybe you remember my experiment in filtering out 18-clue vertically symmetric patterns - your rule considered (if it could be proven) could exclude about 7300 patterns from 200000 only.)

Anyway, it would be interesting to study your conjectures. Unfortunately I cannot see any smart way to do such search, but instead - a huge amount of patterns that must be analysed. Maybe someone can propose shorter way of proving your conjectures. I'll ponder methods of doing that.

I'll be out of Internet next week (on vacations), so I'll have possibility to reply to you posts in a week only.

Serg

by **Serg** » Sun Sep 29, 2013 5:26 am

Hi, coloin!
Here are a few simple consideration about your conjections:
- Coloin's rule 1 (not proven yet): any 2 bands (stacks) of valid sudoku puzzle must contain not less than 8 clues;
- Coloin's rule 2 (not proven yet): any 8 boxes of valid sudoku puzzle must contain not less than 12 clues.

If "Coloin's rule 1" is true, then any valid sudoku puzzle must have not less than 12 clues.

Proof.
Let's denote by S1, S2 and S3 sums of clues in B123, B456 and B789 bands. Suppose "Coloin's rule 1" is true. Then we'll have system of 3 inequalities:
1. S1 + S2 >= 8
2. S1 + S3 >= 8
3. S2 + S3 >= 8
Then we'll add all these inequalities and divide them by 2. We'll get inequality S1 + S2 + S3 >= 12. QED

In similar way it is possible to prove the statement: "If Coloin's rule 2 is true, then any valid sudoku puzzle must have not less than 14 clues".

Maybe both these observations are known to sudoku people. It is interesting - is it possible to prove opposite statements. For example, "If any valid sudoku puzzle has not less than 12 clues, then "Coloin's rule 1" is true"?

Serg

by **coloin** » Thu Oct 10, 2013 12:54 pm

Yes that logic is good ! - ut we are far from proving #9
i have omitted #15 which has been proven of course

Code: Select all: 15+---+---+---+ |...|...|...| |...|...|...| |...|...|...| +---+---+---+ |...|...|...| |...|...|...| |...|...|...| +---+---+---+ |...|...|...| |...|...|...| |...|...|...| +---+---+---+ needs 17 clues

So...............
having proved part of #9 - these patterns dont have valid puzzles

Code: Select all: 111 211 999

this is also invalid

Code: Select all: 003 999 999

and these have 3 empty boxes - so are invalid

Code: Select all: 011 012 012 005 004 040 999 999 999

which of these patterns has Serg already proved as invalid ?

Code: Select all: A.011 B.011 C.011 D.011 E.011 F.011 G.011 H.011 I.011 J.011 K.011 122 212 320 230 023 311 131 410 014 140 500 999 999 999 999 999 999 999 999 999 999 999 L.012 M.012 N.012 O.012 P.012 Q.012 R.012 S.012 T.012 U.012 V.012 W.012 X.012 211 121 112 130 310 301 103 031 013 400 220 202 022 999 999 999 999 999 999 999 999 999 999 999 999 999

Rather more pattterns than I first thought !

C

by **coloin** » Fri Oct 11, 2013 1:08 am

Well ..... looking back eleven has confirmed that

Code: Select all: 0 1 1 2 2 9 9 9 9

has no valid puzzles.

Therefore A,B,D,E,G,I and J are all invalid.

C

by **Serg** » Sat Oct 12, 2013 6:11 pm

Hi, coloin!
Some words about patterns having 7 clues in 2 bands (stacks).
I have slightly different list of possible maps for patterns, potentially having valid puzzles.
I didn't include maps being subsets of these (evident) maps:

Code: Select all: 003 009 999 099 999 999

Here is my list of 25 maps to be checked for having valid puzzles.

Code: Select all: M1 M2 M3 M4 M5 M6 M7 M8 M9 M10 M11 M12 M13 004 005 004 011 011 012 012 012 011 011 011 011 012 120 110 111 014 023 013 022 031 104 203 302 401 103 999 999 999 999 999 999 999 999 999 999 999 999 999 M14 M15 M16 M17 M18 M19 M20 M21 M22 M23 M24 M25 M26 M27 M28 012 012 011 011 011 011 012 012 012 013 022 111 013 021 021 202 301 113 122 212 311 112 121 211 111 111 112 201 301 202 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999

What maps can be excluded by 40-patterns list? Analisys shows we can add 3 "exclusive" maps not having valid puzzles to cited above 2 maps evidently not having valid puzzles.

Code: Select all: N1 based on P98 012 +-----+-----+-----+ 099 |. . .|. . .|x x x| 999 |. . .|. . .|x x x| |. . .|. . .|x x x| +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |x x x|x x x|x x x| +-----+-----+-----+ |. . .|x x x|x x x| |x x x|x x x|x x x| |x x x|x x x|x x x| +-----+-----+-----+ N2 based on P110 011 +-----+-----+-----+ 991 |. . .|. . x|x x x| 999 |. . .|. . x|x x x| |. . x|. . x|x x x| +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. x .|x x x|x x x| +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ N3 based on P123 011 +-----+-----+-----+ 299 |. . .|. x x|x x x| 999 |. . .|. x x|x x x| |. . .|. x x|x x x| +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |x x x|x x x|x x x| +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |x x x|x x x|x x x| +-----+-----+-----+

Applying these maps (N1-N3) enable us to exclude 14 maps from 25-map list. (I didn't use eleven's maps because they are not independenly comfirmed.) So, finally we have 14 maps to be checked. Here is list of maps, which potentially can have valid puzzles, with number of essentially different patterns for each map.

Code: Select all: Map Number of e-d patterns M1 .....42 M3 .....64 M13 ....182 M14 ....258 M15 ....156 M20 ....454 M21 ....442 M22 ....390 M23 ....270 M24 ....236 M25 ....394 M26 ....162 M27 ....144 M28 ....234 Total: 3428

So, to prove "Coloin's rule 1 (any 2 bands (stacks) of valid puzzle must contain greater than 7 clues)", one should do exhaustive search in 3428 patterns.

Serg

[Edited. I missed 3 maps (thanks to coloin for his correction). Now 28-maps list is presented.]
[Edited2. I calculated number of e-d patterns for M26-M28 maps and increased properly total number of patterns to be checked. (Previously published number of patterns - 3062 - was wrong.)]
[Edited3. As coloin pointed, we can filtered out maps M2 and M11 by "exclusive" map N2 applying. I removed these maps from the list of maps potentially having valid puzzles and corrected total number of potentially valid patterns.]

by **coloin** » Sat Oct 12, 2013 7:00 pm

Yes very good ......
And yes, always better to do a complete run on it.
still a lot of patterns and there is many ways to fill in even the bottom band !

however i seem to have more than you and i havent included the 4 patterns with

111
xxx
999

which adds up to 28 in total ?
i did mine by eye - so i could be in error, except

you dont have

Code: Select all: 012 220 999 012 130 999 012 310 999

It may be easier with patterns with

Code: Select all: 011 xxx 999

As this is band 29 and there are only a few ways [edit 9] to complete it with 2 clues
here

C

by **Serg** » Sat Oct 12, 2013 8:49 pm

Hi, coloin!

coloin wrote:however i seem to have more than you and i havent included the 4 patterns with

111
xxx
999

which adds up to 28 in total ?

You are right. I missed 3 maps ("O", "P" and "V" in your list), but you missed my 4 maps (M3, M23, M24 and M25). So, it seems correct number of maps is 28. (I'll edit my post.)

Serg

by **coloin** » Mon Oct 14, 2013 7:10 pm

Looks like 28 maps
This maximal pattern gets rid of many

Code: Select all: P110 +-----+-----+-----+ |. . .|. . x|x x x| |. . .|. . x|x x x| |. . x|. . x|x x x| +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. x .|x x x|x x x| +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+

including M2 and M11

As the pattern
101
199
999 is invalid - which means there must always be 2 under the 1

giving
101
2?2
999
[P123] deems ? >2
so
101
222
999 is invalid [although in reality ? is probably is >/= 3]

The
011
0??
999 is covered in all circumstances with [P98]

So the 011 cases with 5 clues in the 2nd band are all invalid

C

by **coloin** » Tue Oct 15, 2013 12:51 am

So i think we have progressed to

Code: Select all: 101 222 999

is invalid
here is a

Code: Select all: 101 232 999 +---+---+---+ |5..|...|...| |...|...|6..| |...|...|...| +---+---+---+ |.1.|..3|.4.| |.7.|.4.|..5| |...|2..|...| +---+---+---+ |123|456|789| |765|892|134| |894|371|256| +---+---+---+

C

by **Serg** » Tue Oct 15, 2013 3:46 pm

Hi, coloin!

coloin wrote:Looks like 28 maps
This maximal pattern gets rid of many
Code: Select all
P110 +-----+-----+-----+ |. . .|. . x|x x x| |. . .|. . x|x x x| |. . x|. . x|x x x| +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. x .|x x x|x x x| +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+

including M2 and M11

Good point! We must exclude M2 and M11 maps (I'll edit my post with numbers of patterns). I was not carefull enough, but this news is pleasant

. I couldn't find other maps to be excluded by this rule.

coloin wrote:As the pattern
101
199
999 is invalid - which means there must always be 2 under the 1

giving
101
2?2
999
[P123] deems ? >2
so
101
222
999 is invalid [although in reality ? is probably is >/= 3]

The
011
0??
999 is covered in all circumstances with [P98]

So the 011 cases with 5 clues in the 2nd band are all invalid

I agree with your logic. If a map has band 011 (i.e. 1 empty box and 2 boxes containing exactly 1 clue each), then each remaining band must have 322 configuration, at least, to have valid puzzles. Hence any puzzle with band 011 must contain at least 9 clues in 2 bands or 16 clues in a puzzle to have valid puzzles.

I think we could go further if we could have list of possible patterns having 7 clues in 2 bands. Maximal patterns have higher exclusive potential than maps constructed on their bases. I think, we could obtain about 1000 possible patterns only if we would apply 40 maximal patterns to that list of potentially valid patterns. But I see another way of going forward in this direction. I hope in some time I'll be capable of studying "two-band-free" patterns. If it will be the case, we'll get exhaustive search results for possible patterns containing 7 clues in 2 bands.

Serg

by **coloin** » Sun Oct 20, 2013 10:08 pm

Well ..... i have been thinking too about how to proceed .....
On the adding the [3+4] clues to a band of 27.....
It struck me that one would "only" need to use one each of the 44 ganster representatives.
[The order of the 3 vertical clues in the band is academic]
i generated 1600 random [4+4+27]puzzles over the weekend.
I had hoped that maybe only a select few gangsterswould have puzzles - unfortunatly all but 3 of the 44 [1,40 & 44] had valid puzzles.

Anhow ..... probably i could add 5 clues to 5 boxes. addding 2 clues would complete the search.

I will see if that is possible with ganster 33 - it seemed to have a good few puzzles

EDIT - see above as 3+4+27 was found by champagne I should have searched for a 3+5+27 [ not 4+4+27] puzzle ....and then for a 3+4+27

C

The New Sudoku Players' Forum

Ask for patterns that they dont have puzzles 2

Ask for patterns that they dont have puzzles 2

Re: Ask for patterns that they dont have puzzles 2

Re: Ask for patterns that they dont have puzzles 2

Re: Ask for patterns that they dont have puzzles 2

Re: Ask for patterns that they dont have puzzles 2

Re: Ask for patterns that they dont have puzzles 2

Re: Ask for patterns that they dont have puzzles 2

Re: Ask for patterns that they dont have puzzles 2

Re: Ask for patterns that they dont have puzzles 2

Re: Ask for patterns that they dont have puzzles 2

Re: Ask for patterns that they dont have puzzles 2

Re: Ask for patterns that they dont have puzzles 2

Re: Ask for patterns that they dont have puzzles 2

Re: Ask for patterns that they dont have puzzles 2

Re: Ask for patterns that they dont have puzzles 2