IMpossible sudokus

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

IMpossible sudokus

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

...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

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

evert

Posts: 186
Joined: 26 August 2005

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

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

Udosuk,
I agree

jamesb2951,,

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

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

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

...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

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

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

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

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