OK so far

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

OK so far

Postby Smythe Dakota » Tue Jun 06, 2006 5:22 am

Define a partially filled-in grid as OK so far if there is at most one of each digit in each row, column, and box.

Note that a grid can be OK so far and still have no solution. The following is a simple example:

Code: Select all
+-------+-------+-------+
| 1 2 3 | 4 5 6 | 7 8 . |
| . . . | . . . | . . 9 |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+

Question 1. For which values of N (N=0 through N=81) do there exist grids with N cells filled in, which are OK so far and yet have no solutions?

Question 2. For which values of N (N=0 through N=81) do there exist grids with N cells filled in, which are OK so far and have multiple solutions?

I am guessing that, for question 1, the minimum N is 9, and the maximum is 77 or fewer.

For question 2, the minimum N is obviously 0, and the maximum is probably 77.

Bill Smythe
Smythe Dakota
 
Posts: 534
Joined: 11 February 2006

Re: OK so far

Postby ravel » Tue Jun 06, 2006 7:23 am

Smythe Dakota wrote:Question 1. For which values of N (N=0 through N=81) do there exist grids with N cells filled in, which are OK so far and yet have no solutions?
...
I am guessing that, for question 1, the minimum N is 9, and the maximum is 77 or fewer.

See here for tso's sample with 5 numbers.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Pi » Tue Jun 06, 2006 8:43 pm

Code: Select all
N=1 - No solution available
N=2 - No Solution available
N=3 - Unknown
N=4 - Unknown
N=5:
+---+---+---+
|1--|---|---|
|2--|---|---|
|3--|---|---|
+---+---+---+
|-4-|---|---|
|---|---|---|
|---|---|---|
+---+---+---+
|---|---|---|
|--4|---|---|
|---|---|---|
+---+---+---+

N = 6:
+---+---+---+
|1--|---|---|
|25-|---|---|
|3--|---|---|
+---+---+---+
|-4-|---|---|
|---|---|---|
|---|---|---|
+---+---+---+
|---|---|---|
|--4|---|---|
|---|---|---|
+---+---+---+

N=7:
+---+---+---+
|1--|---|---|
|256|---|---|
|3--|---|---|
+---+---+---+
|-4-|---|---|
|---|---|---|
|---|---|---|
+---+---+---+
|---|---|---|
|--4|---|---|
|---|---|---|
+---+---+---+

N=8
+---+---+---+
|17-|---|---|
|256|---|---|
|3--|---|---|
+---+---+---+
|-4-|---|---|
|---|---|---|
|---|---|---|
+---+---+---+
|---|---|---|
|--4|---|---|
|---|---|---|
+---+---+---+

N=9
+---+---+---+
|17-|---|---|
|256|---|---|
|38-|---|---|
+---+---+---+
|-4-|---|---|
|---|---|---|
|---|---|---|
+---+---+---+
|---|---|---|
|--4|---|---|
|---|---|---|
+---+---+---+

N=10
+---+---+---+
|179|---|---|
|256|---|---|
|38-|---|---|
+---+---+---+
|-4-|---|---|
|---|---|---|
|---|---|---|
+---+---+---+
|---|---|---|
|--4|---|---|
|---|---|---|
+---+---+---+

10<N<28: - Fill in parts of boxes 2 & 3 in adition to N=10 grid
28<N<46: - Fill in parts of boxes 6 & 9  in adition to N=10 grid and boxes 2&3

46<N<64:
This grid minus any numbers in boxes 5 & 8 which can each be removed
+---+---+---+
|179|823|456|
|256|147|938|
|38-|965|127|
+---+---+---+
|-4-|356|289|
|---|278|341|
|---|419|675|
+---+---+---+
|---|791|564|
|--4|582|713|
|---|634|892|
+---+---+---+

N=65
+---+---+---+
|179|823|456|
|256|147|938|
|38-|965|127|
+---+---+---+
|74-|356|289|
|---|278|341|
|---|419|675|
+---+---+---+
|---|791|564|
|--4|582|713|
|---|634|892|
+---+---+---+

N=66
+---+---+---+
|179|823|456|
|256|147|938|
|38-|965|127|
+---+---+---+
|741|356|289|
|---|278|341|
|---|419|675|
+---+---+---+
|---|791|564|
|--4|582|713|
|---|634|892|
+---+---+---+

N=67
+---+---+---+
|179|823|456|
|256|147|938|
|38-|965|127|
+---+---+---+
|741|356|289|
|--5|278|341|
|---|419|675|
+---+---+---+
|---|791|564|
|--4|582|713|
|---|634|892|
+---+---+---+

N=68
+---+---+---+
|179|823|456|
|256|147|938|
|38-|965|127|
+---+---+---+
|741|356|289|
|-65|278|341|
|---|419|675|
+---+---+---+
|---|791|564|
|--4|582|713|
|---|634|892|
+---+---+---+

N=69
+---+---+---+
|179|823|456|
|256|147|938|
|38-|965|127|
+---+---+---+
|741|356|289|
|965|278|341|
|---|419|675|
+---+---+---+
|---|791|564|
|--4|582|713|
|---|634|892|
+---+---+---+

N=70
+---+---+---+
|179|823|456|
|256|147|938|
|38-|965|127|
+---+---+---+
|741|356|289|
|965|278|341|
|8--|419|675|
+---+---+---+
|---|791|564|
|--4|582|713|
|---|634|892|
+---+---+---+

N=71
+---+---+---+
|179|823|456|
|256|147|938|
|38-|965|127|
+---+---+---+
|741|356|289|
|965|278|341|
|8-3|419|675|
+---+---+---+
|---|791|564|
|--4|582|713|
|---|634|892|
+---+---+---+

N=72
+---+---+---+
|179|823|456|
|256|147|938|
|38-|965|127|
+---+---+---+
|741|356|289|
|965|278|341|
|823|419|675|
+---+---+---+
|---|791|564|
|--4|582|713|
|---|634|892|
+---+---+---+

N=73
+---+---+---+
|179|823|456|
|256|147|938|
|38-|965|127|
+---+---+---+
|741|356|289|
|965|278|341|
|823|419|675|
+---+---+---+
|---|791|564|
|6-4|582|713|
|---|634|892|
+---+---+---+

N=74
+---+---+---+
|179|823|456|
|256|147|938|
|38-|965|127|
+---+---+---+
|741|356|289|
|965|278|341|
|823|419|675|
+---+---+---+
|---|791|564|
|694|582|713|
|---|634|892|
+---+---+---+

N=75
+---+---+---+
|179|823|456|
|256|147|938|
|38-|965|127|
+---+---+---+
|741|356|289|
|965|278|341|
|823|419|675|
+---+---+---+
|---|791|564|
|694|582|713|
|--7|634|892|
+---+---+---+

N=76
+---+---+---+
|179|823|456|
|256|147|938|
|38-|965|127|
+---+---+---+
|741|356|289|
|965|278|341|
|823|419|675|
+---+---+---+
|---|791|564|
|694|582|713|
|5-7|634|892|
+---+---+---+

N=77
+---+---+---+
|179|823|456|
|256|147|938|
|38-|965|127|
+---+---+---+
|741|356|289|
|965|278|341|
|823|419|675|
+---+---+---+
|---|791|564|
|694|582|713|
|517|634|892|
+---+---+---+





i believe that an N=80 would be impossible. I think that my 77 can be advanced on and am interested to see if there is a 3 or a 4 out there
Pi
 
Posts: 389
Joined: 27 May 2005

Postby JPF » Tue Jun 06, 2006 9:06 pm

Pi wrote:i believe that an N=80 would be impossible. I think that my 77 can be advanced on

Code: Select all
N=78
+---+---+---+
|179|823|456|
|256|147|938|
|38-|965|127|
+---+---+---+
|741|356|289|
|965|278|341|
|823|419|675|
+---+---+---+
|--2|791|564|
|694|582|713|
|517|634|892|
+---+---+---+

N=79
+---+---+---+
|179|823|456|
|256|147|938|
|38-|965|127|
+---+---+---+
|741|356|289|
|965|278|341|
|823|419|675|
+---+---+---+
|-32|791|564|
|694|582|713|
|517|634|892|
+---+---+---+




JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby Smythe Dakota » Wed Jun 07, 2006 12:42 am

Hmm, interesting.

But I see nobody has tackled question 2 yet.

Maybe we can generalize: For which N (N=0 through N=81) and which M (M=0 through M=gazillions) do there exist grids with N filled-in cells which are OK so far and which have exactly M solutions?

Bill Smythe
Smythe Dakota
 
Posts: 534
Joined: 11 February 2006

Postby Pi » Wed Jun 07, 2006 8:27 pm

as for question 2 i am running a query on my database, i will get you a 77 in a minute
Pi
 
Posts: 389
Joined: 27 May 2005

Postby JPF » Wed Jun 07, 2006 9:46 pm

Pi,

what you are looking for is here, from Ocean

Ocean wrote:Here is one with 77 clues (and I am too lazy to make it minimal by hand):

Code: Select all
Pseudo-puzzle (two solutions):
 *-----------*
 |159|286|473|
 |237|154|896|
 |486|397|521|
 |---+---+---|
 |912|843|765|
 |345|..9|182|
 |678|521|349|
 |---+---+---|
 |861|432|957|
 |593|..8|214|
 |724|915|638|
 *-----------*



JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France


Return to General