The New Sudoku Players' Forum

[coloin]

Code: Select all

+---+---+---+
|.23|456|789|
|4..|...|...|
|7..|...|...|
+---+---+---+
|8..|...|...|
|9..|...|...|
|2..|...|...|
+---+---+---+
|5..|...|...|
|3..|...|...|
|6..|...|...|
+---+---+---+ 16 clues

this takes no account of the box constraints

But 16 clues can define a large proportion of the grid to make one complete box, one complete row and one complete column -

Code: Select all

+---+---+---+              +---+---+---+
|..3|456|7.9|              |123|456|789|
|4.6|...|.5.|              |496|...|.5.|
|78.|...|...|              |785|...|...|
+---+---+---+              +---+---+---+
|3..|...|...|              |3..|...|...|
|8..|...|...|              |8..|...|...|
|5..|...|...|              |5..|...|...|
+---+---+---+              +---+---+---+
|9..|...|...|              |9..|...|...|
|2..|...|...|              |2..|...|...|
|...|...|...|              |6..|...|...|
+---+---+---+ 16 clues     +---+---+---+

Even better - more box envolvement

Code: Select all

+---+---+---+              +---+---+---+
|...|3.1|...|              |5.9|3.1|...|
|2.4|...|...|              |2.4|.95|13.|
|...|...|...|              |1.3|...|59.|
+---+---+---+              +---+---+---+
|8..|52.|...|              |891|523|...|
|...|...|9.1|              |35.|...|9.1|
|...|...|3..|              |74.|91.|3.5|
+---+---+---+              +---+---+---+
|..7|.4.|.5.|              |627|149|853|
|91.|...|...|              |915|.3.|...|
|.3.|...|...|              |438|.5.|.19|
+---+---+---+ 16 clues     +---+---+---+ 190 grid solutions

If we were unable to make fill a grid to this extent with 16 clues then this this might have been a proof for....
The number of grid solutions with 16 clues is always = 0 or > 1........[i.e. never 1]

It might be impossible getting this complete box/row/colum pattern with only 15 clues......therefore proof for ?15
C

[StrmCkr]

removed

[coloin]

Some of what you say StrmCkr - I can follow.

Many have tried [myself included ] to find a valid 16 clue unique puzzle.

Concluded that altough some grids came close - it was just about impossible for one not to have been found. It proved impossible to iterate through all the 3*10^16 ways to put 16 clues in a grid.[in a lifetime]

The closest that we got was the 16 clues in the SF grid that had 18 [9 of one clue and 9 of another] clue completions.

Code: Select all

+---+---+---+                   
|...|.4.|7..|                   
|.8.|...|...|                   
|.1.|...|.2.|                   
+---+---+---+                   
|...|8..|..6|                   
|7..|...|...|                   
|4..|...|2..|                   
+---+---+---+                   
|3.2|.7.|...|                   
|...|...|...|                   
|...|..6|.18|                   
+---+---+---+      16 clues,     
+---+---+---+                   
|63.|241|78.|                   
|284|76.|1.3|                   
|.17|.83|624|                   
+---+---+---+                   
|123|8.7|.46|                   
|7.6|432|8.1|                   
|4.8|61.|237|                   
+---+---+---+                   
|342|178|.6.|                   
|861|..4|372|                   
|.7.|326|418|                   
+---+---+---+   2 grid solutions , 18 clue completions.[any 5 or 9]

..9.4.7...8........1.....2....8....67........4.....2..3.2.7..................6.18
....4.7.5.8........1.....2....8....67........4.....2..3.2.7..................6.18
....4.7...8...5....1.....2....8....67........4.....2..3.2.7..................6.18
....4.7...8.....9..1.....2....8....67........4.....2..3.2.7..................6.18
....4.7...8.......51.....2....8....67........4.....2..3.2.7..................6.18
....4.7...8........1.9...2....8....67........4.....2..3.2.7..................6.18
....4.7...8........1.....2....85...67........4.....2..3.2.7..................6.18
....4.7...8........1.....2....8..9.67........4.....2..3.2.7..................6.18
....4.7...8........1.....2....8....679.......4.....2..3.2.7..................6.18
....4.7...8........1.....2....8....67......5.4.....2..3.2.7..................6.18
....4.7...8........1.....2....8....67........45....2..3.2.7..................6.18
....4.7...8........1.....2....8....67........4....92..3.2.7..................6.18
....4.7...8........1.....2....8....67........4.....2..3.2.7.5................6.18
....4.7...8........1.....2....8....67........4.....2..3.2.7...9..............6.18
....4.7...8........1.....2....8....67........4.....2..3.2.7.......5..........6.18
....4.7...8........1.....2....8....67........4.....2..3.2.7........9.........6.18
....4.7...8........1.....2....8....67........4.....2..3.2.7.............9....6.18
....4.7...8........1.....2....8....67........4.....2..3.2.7...............5..6.18

16 numbers reduces all but 2 pairings

This is a good example of this ! [Trivially it is 7 numbers]
............
1 given clue does reduces 8 options in the box and 12 others outside the box. - true.
............
So cross elimination only occurs at the 17th digit - this sounds good !
............

However I think I have a simpler method.

It might turn out to be wrong, but it might just be valid.

Take a random 27 clue sudoku band like

Code: Select all

+---+---+---+
|123|456|789|
|546|789|213|
|789|231|564|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+

If you keep the given clues within the band - it is impossible to fill in the band with less than 18 clues.

Code: Select all

+---+---+---+
|12.|.56|78.|
|5.6|.89|2.3|
|.89|.31|.64|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+ 18 clues

If you are able to insert clues outside this band - it is possible to fill in the band - and also the whole grid with 17 clues.

I cant fill a single band with any combination of 17 clues. - which doesnt solve the complete grid as well.

Does one exist - possibly ?

Code: Select all

+---+---+---+
|.42|.7.|3.6|
|3..|.9.|1.4|
|..7|1..|8..|
+---+---+---+
|.5.|...|..9|
|...|.36|...|
|...|...|.5.|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+  17 clues defines 25 clues out of 27 in the band

If we can prove that a 16 cant fill a band - does this prove that 16-sudokus dont exist ?. [I think yes]

C

[StrmCkr]

removed

[Papy]

Hi,

Code: Select all

1 given clue does reduces 8 options in the box and 12 others outside the box. - true.

True but incomplet a clue also reduce the digits of the grid
If you obsere the clues of a 17 grid you will see that the number are present a number of time exact.
i/e in the clues you have

Number 1 3 times
Number 2 2 times
Number 3 4 times
...

Adding a clue change this repartition . If you take a sudoku grid (intouchable) with for example a clue in R1C1 with the digit 5
You have a solution. But if you change the 5 in 9 youy will have no solution otr multi solution

That means that the digit it self has importance.
I think that these ârameter is forgat by the conceptot because if changing a digit modifie the solution we don't knoiw why!!!
The day we find all he secrets of the Sudoku will be soved!

About the 17 clues in a band.
My theoryy is out?No
Why? Because all he contrains are not equal:

The different sets colonnes,row, boxex, digits are not equal
all the cell are not equal.

The difference is that the colonne has only 3 elemets, the rows,columns,box, digit have 9 elements

i/a a colum couild take a value between 123 and 987 760 and a row can take 362880 value!
So when you set the a cell if you consider the coluymn or the row the ptoblem is not equal so you cann't applky the band rules to a grid!!!

Papy

[coloin]

Trivially it is 7 numbers

-
7 numbers gives you an unknown pairing of 2 clues.
i.e you need 8 clue numbers.

"I cant fill a single band with any combination of 17 clues. - which doesnt solve the complete grid as well."

which is not

your statement would imply that 17 can't genreate a vaild sudoku as well as it can't complete a band on its own.

I hope some one can find 17 clues which fills a band without solving the grid completly - although I doubt it.

Interesing there is one pair left with the 17 clues.

I think it should be possible to prove a 16 clue puzzle cant fill a band

C

[RW]

I hope some one can find 17 clues which fills a band without solving the grid completly - although I doubt it.

I'm sure those exist, how are you searching? I'd look around the existing 17s and 18s. All you need to find is 17 clues that hit all unavoidables except one of size 4 or 6 (or a bigger, or several unavoidbles that are confined within 2 bands). Should be easy to find by simply removing clues from the 18s or moving some clues in the 17s... At least it souds easy, maybe it's more complicated than that..?

RW

[coloin]

Yes..you are right.
I looked at Gordons 16 clue Pseudopuzzles here - and added a clue
Heres a 17 which solves a band.....but not the puzzle....

Code: Select all

+---+---+---+
|7.3|8..|...|
|...|6..|4..|
|2..|...|...|
+---+---+---+
|...|...|.73|
|.4.|1..|...|
|...|...|...|
+---+---+---+
|61.|...|9..|
|...|.2.|1..|
|..8|.7.|...|
+---+---+---+


Good, so now we need to show that 16 clues cant make a band.
C

[Papy]

Hi,

Do you try he inverse?
Take a 17 clues and remove one.
I thinks that it's possible to solve one or more band
'a band is well r1+r2+r3 or c4+c5+c6?)

Papy

[coloin]

Yes thats how I had tried initially- without success - thats why I was pessimistic.

The 16 clue "pseudopseudopuzzle" I posted has a lowly 8 grid solutions, but needs two clues to complete it. None of the other subgrids posted filled a band [3 boxes] with the 16 clues either.

A quick run through of all of Gordons 17s minus 1 clue would be the logical first step,and I apreciate it would not necessarily be proof.....

C

[StrmCkr]

removed

[coloin]

as 16 clues in the above example can expand and limit all but (2 paired numbers)

I agree !

I agree so much in fact that is why I posted the very same [isomorphic] puzzle and grid completions in the third post of this page.

16 clues, 2 grid solutions, 18 grid completions [9 each of 2 clue numbers].

It has 7 clue numbers and needs one more.

Thats why we called it the SF grid ["thats "Strangly Familiar""]

Use index416.exe program to classify the 6 bands
Use nppcsu.exe to identify some of the small 2-clue unavoidable sets
You will see the two solution grids are isomorphic.

i do have another idea though, is the clue minimal based on the fact numbers move in pairs on the board?

The 2-clue number "template" - or 2-clue unavoidables was extensivly investigated here.

x^(81-N-P-C)
as (x approches 81)

where x = (1:9*9)
where N = # of placed canadiates of that type(1:9)
P = (# of boxes removed + single cells in line of sight, compared to the value of x selected)
C = constraints that generate 0 placemetents of x in any sub set of equations as x must be valid in all 9 subsets. (when looking specifically at x)

Please could you expand on your theory, and why it will always ,at best , leave an unavoidable set ["pair"] at 16 clues ?
C

[m_b_metcalf]

A quick run through of all of Gordons 17s minus 1 clue would be the logical first step,and I appreciate it would not necessarily be proof.....

C

Right, but at 1.6GHz my program needed over 100s for the first 10. Quick?

Regards,

Mike Metcalf

[Papy]

Yes C
the problem is the same that with a 9*9 grids
you need 17 clues

but i give you 1 billion of euros if you do a band of 16*16 with 30 clues
Alxays he size maxi *2 and -2

Papy

[coloin]

Mike, thankyou for responding to this task - I was rather off hand in my post. If you can spare a 100 hours of processor by all means complete it. I would discontinue on finding a band with only 16 clues of course.

Maybe an inkling into how successful it might be is checking how often you can fill a band using a known 17,-1clue +1 clue.

The grids from which I found the 17 which only filled a band were specifically those 16 clues which had the fewest grid solutions

xall16-002
5.2...4.....71...3..............46...7.2......1.......6....2.......3..1.4........
xall16-004
1..6............5........3.....4.72.....2....3.........24...1.....3..6...7.5.....
5.42.........4..3.1.........6..73.........5.1..........3.....7....5..4..6........
5.42.........4..3.1.........6..73.........5.1..........3.....7....5..4..8........
xall16-006
....6.5.28.1................5..2....4......8....9..3.....8.4.9..2..........1.....
...71....4.6......2.............45..6..2...........31..3..5...........42.1.......
.7....3.2...5.6............5..4.........7.2....1......6.....4...2..3.......1...5.
1.42.........4..3.5.........6..73.........5.1..........3.....7....1..4..8........
6...42....3....7............8.73...........42...1.....2.4..5.........3..5........
xall16-007
2.....3.6..1.5.................41.5.67....2...3.........8....4....7........6.....
xall16-008
....57...1...3....6.4......2......6....4...1..7........3....7.5...1...........3..
....9.2.56.8................5..2....4......8....9..3.....8.4.6..2..........1.....
....9.5.26.8................5..2....4......8....9..3.....8.4.6..2..........1.....
....9.5.28.1................5..2....4......8....9..3.....8.4.9..2..........1.....
.3.5.....7......2........1..43...5......1..........3..2.1..7......3..6.4.........
6.1...........24...........42...3.......5..17.........5..16.....4....3.....7.....
6.2...5.....13...4..............57...3.2......1.......7....2.......4..3.5........
7.38........6..4..2...............73.4.1..............61....9......2.1......7.... ***
xall16-009
4..35....61..........7......83..1..........2........4.5.....1..2..4...........8

these dont necessarily have valid 17s by adding one clue [ apart from xall16-002 which is another varient of the SF !]

*** was the one I used

The 15 clue grid with the fewest grid solutions was used earlier. It doesnt have 17s either !

Code: Select all

+---+---+---+
|...|3.1|...|             
|2.4|...|...|   
|...|...|...|       
+---+---+---+   
|8..|52.|...|       
|...|...|9.1|         
|...|...|3..|           
+---+---+---+       
|...|.4.|.5.|           
|91.|...|...|             
|.3.|...|...|             
+---+---+---+ 15 clues     596 grid solutions.   source G Royle

I think RW was correct - we only need to find a grid where 16 clues hits all the unavoidables in a band

Should be easy - if it was possible !

C


Papy - I dont do 16*16