IMpossible sudokus

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

IMpossible sudokus

Postby jamesb2951 » Thu Sep 22, 2005 2:57 am

Can a grid with only 8 clues, all different, no two in the same row, column or box, be impossible to solve? How about only seven clues?
jamesb2951
 
Posts: 3
Joined: 21 September 2005

IMpossible sudokus

Postby jamesb2951 » Thu Sep 22, 2005 3:00 am

...using the word "solve" loosely. I mean could the grid be impossible to complete by any means, even "brute force"?
jamesb2951
 
Posts: 3
Joined: 21 September 2005

Postby evert » Thu Sep 22, 2005 6:30 am

This 1 has no solution at all:
Code: Select all
1; ; ; ; ; ; ; ; ;
 ; ; ; ; ; ; ; ; ;
 ; ; ; ; ; ; ; ; ;
 ; ;1; ; ; ; ; ; ;
 ; ; ; ; ; ; ; ; ;
 ; ; ; ; ; ; ; ; ;
 ; ; ; ; ; ; ; ; ;
 ; ; ; ;1; ; ; ; ;
 ;5; ; ; ; ;2;3;4;

see also http://forum.enjoysudoku.com/viewtopic.php?t=1380
evert
 
Posts: 186
Joined: 26 August 2005

Postby udosuk » Thu Sep 22, 2005 5:13 pm

evert, jamesb2951 said the clues must be all different. So your example is no good...

And I think no, you can't force a contradiction with 8 different digits in 8 different rows/columns/boxes. It seems you are implying that you can force one with 9. Please show us an example!
udosuk
 
Posts: 2698
Joined: 17 July 2005

good catch

Postby jamesb2951 » Thu Sep 22, 2005 10:40 pm

Sorry for the misimplication! I don't have an example of an impossible 1-9 layout with only one digit in each row, column and box. I believe there is such a layout, since there are impossible such layouts in smaller boards.
jamesb2951
 
Posts: 3
Joined: 21 September 2005

Postby evert » Fri Sep 23, 2005 3:44 pm

Udosuk,
I agree

jamesb2951,,
please explain your impossible examples on smaller boards

BTW
Do you mean the grid has one unique solution?
Or do you mean a grid with more solutions and all of them very very hard to find?
evert
 
Posts: 186
Joined: 26 August 2005

Postby udosuk » Fri Sep 23, 2005 4:39 pm

What James wants is a grid that has no solution, like the one you posted earlier where you can't put a 1 anywhere in the bottom row, but all the given clues (a maximum of 9) must be of different digits, all in different rows/columns/boxes.

I think this could be a programming drill for guys like dukuso to help...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby gfroyle » Sun Sep 25, 2005 11:34 am

Can't be done.. not much programming needed.

There is only one way, up to equivalence, of choosing 9 spots that are all in different rows, columns and boxes.

Then if we want the entries to be all different, then there is only one way, up to equivalence, of assigning the numbers.

This gives just one grid to check

Code: Select all
1 . .  . . .  . . .
. . .  2 . .  . . .
. . .  . . .  3 . .

. 4 .  . . .  . . .
. . .  . 5 .  . . .
. . .  . . .  . 6 .

. . 7  . . .  . . .
. . .  . . 8  . . .
. . .  . . .  . . 9


This has more than one solution, and so we are finished..

Cheers

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby sonovapreechaman » Sun Sep 25, 2005 12:15 pm

...so how does this one fit in to that equation?

1 _ _ | _ _ _ | _ _ _
_ _ _ | _ _ _ | _ _ 9
_ 7 _ | _ _ _ | _ _ _
_________________
_ _ _ | _ _ _ | _ 6 _
_ _ 8 | _ _ _ | _ _ _
_ _ _ | _ _ 2 | _ _ _
_________________
_ _ _ | 4 _ _ | _ _ _
_ _ _ | _ 3 _ | _ _ _
_ _ _ | _ _ _ | 5 _ _
sonovapreechaman
 
Posts: 3
Joined: 24 September 2005

Postby gfroyle » Sun Sep 25, 2005 12:40 pm

sonovapreechaman wrote:...so how does this one fit in to that equation?

1 _ _ | _ _ _ | _ _ _
_ _ _ | _ _ _ | _ _ 9
_ 7 _ | _ _ _ | _ _ _
_________________
_ _ _ | _ _ _ | _ 6 _
_ _ 8 | _ _ _ | _ _ _
_ _ _ | _ _ 2 | _ _ _
_________________
_ _ _ | 4 _ _ | _ _ _
_ _ _ | _ 3 _ | _ _ _
_ _ _ | _ _ _ | 5 _ _


Two entries in one box... he wanted all entries in different boxes..
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby udosuk » Sun Sep 25, 2005 5:41 pm

Very smart proof, Gordon!

And I think the same result holds even if we lax the rule about the boxes. In that case at most 3 clues could be in a box and the other 6 clues must not be in the same band/stack of that box.

Couldn't prove it elegantly like you did though...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby evert » Tue Sep 27, 2005 9:52 pm

gfroyle wrote:There is only one way, up to equivalence, of choosing 9 spots that are all in different rows, columns and boxes.
Does this need any proof by itself?
evert
 
Posts: 186
Joined: 26 August 2005

Postby gfroyle » Wed Sep 28, 2005 1:49 am

evert wrote:
gfroyle wrote:There is only one way, up to equivalence, of choosing 9 spots that are all in different rows, columns and boxes.
Does this need any proof by itself?


You need to convince yourself that it is true, but it is not difficult.

Remember that we can permute the rows within any horizontal band of 3, and the columns within any vertical stack of 3 to get an equivalent puzzle.

We need to show that any grid with 9 cells one in each row/col/box can be permuted to the one that I gave in my first message. So assume that someone gives you such a grid not already in the standard form.

Start with the top horizontal band and permute the rows so that row 1 contains the entry from box 1, row 2 the entry from box 2 and row 3 the entry from box 3. Then do the middle horizontal band, and again permute the rows so that rows 4,5,6 contain the entries from boxes 4,5 and 6 respectively. Then do the same in the bottom horizontal band.

Then do the same for the vertical stacks, one at a time, but now permuting columns...

The result of this is a grid with 9 filled cells that IS in standard form.
gfroyle
 
Posts: 214
Joined: 21 June 2005


Return to General