13 posts
• Page **1** of **1**

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

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

see also http://forum.enjoysudoku.com/viewtopic.php?t=1380

- 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

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!

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

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

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

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

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

Cheers

Gordon

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

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

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

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

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

13 posts
• Page **1** of **1**