The New Sudoku Players' Forum

[jamesb2951]

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]

...using the word "solve" loosely. I mean could the grid be impossible to complete by any means, even "brute force"?

[evert]

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

[udosuk]

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!

[jamesb2951]

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.

[evert]

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?

[udosuk]

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

[gfroyle]

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

[sonovapreechaman]

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

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

[gfroyle]

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

[udosuk]

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

[evert]

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?

[gfroyle]

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.