17? 16? 15? 14?

Everything about Sudoku that doesn't fit in one of the other sections

Postby coloin » Thu Jan 04, 2007 1:29 pm

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
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby StrmCkr » Thu Jan 04, 2007 6:38 pm

removed
Last edited by StrmCkr on Sat Dec 13, 2014 6:31 am, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 679
Joined: 05 September 2006

Postby coloin » Sun Jan 07, 2007 12:29 am

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

Strmckr wrote: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
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby StrmCkr » Sun Jan 07, 2007 7:29 am

removed
Last edited by StrmCkr on Sat Dec 13, 2014 6:31 am, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 679
Joined: 05 September 2006

Postby Papy » Sun Jan 07, 2007 9:42 am

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
Papy
 
Posts: 131
Joined: 15 August 2006

Postby coloin » Sun Jan 07, 2007 11:05 am

coloin wrote:Trivially it is 7 numbers
-
7 numbers gives you an unknown pairing of 2 clues.
i.e you need 8 clue numbers.

coloin wrote:"I cant fill a single band with any combination of 17 clues. - which doesnt solve the complete grid as well."
which is not
StrmChkr wrote: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
Last edited by coloin on Sun Jan 07, 2007 9:51 am, edited 2 times in total.
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby RW » Sun Jan 07, 2007 11:13 am

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
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby coloin » Sun Jan 07, 2007 1:44 pm

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
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby Papy » Sun Jan 07, 2007 3:06 pm

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
Papy
 
Posts: 131
Joined: 15 August 2006

Postby coloin » Mon Jan 08, 2007 12:50 am

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
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby StrmCkr » Mon Jan 08, 2007 7:35 am

removed
Last edited by StrmCkr on Sat Dec 13, 2014 6:31 am, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 679
Joined: 05 September 2006

Postby coloin » Mon Jan 08, 2007 12:35 pm

StrmChkr wrote: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.



StrmChkr wrote: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.

StrmChkr wrote: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
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby m_b_metcalf » Mon Jan 08, 2007 2:27 pm

coloin wrote: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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8428
Joined: 15 May 2006
Location: Berlin

Postby Papy » Mon Jan 08, 2007 6:00 pm

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:D:D:D:D:D

Papy
Papy
 
Posts: 131
Joined: 15 August 2006

Postby coloin » Tue Jan 09, 2007 2:46 am

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

gfroyle wrote: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
coloin
 
Posts: 1638
Joined: 05 May 2005

PreviousNext

Return to General