Combinations and stuff...

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

Combinations and stuff...

Postby Guest » Tue Dec 06, 2005 6:21 pm

Hello,

I have found that neat game of 'Sudoku' too late (well, I'm 15-year-old, so it wasn't possible much earlier anyway:) ), about two weeks ago and so I haven't been able to (and I will never be able to) read all topics on this forum. So I don't know whether my question has already been posted and replied. I will, however, be very glad if anybody here knows the answer(s) and posts them, even though it isn't about solving sudoku and the game itself.

For sure there are two types of sudoku: These, which have just one possible result and these, which can have two or more solvings (for example blank grid:) ). Well, there are these which don't have any solving, but I don't count them, because I think it's sort of 'breaking the rule'.

1) Which is the SMALLEST possible amount of numbers in the grid in Sudoku's which have just one solving?
2) Which is the BIGGEST possible amount of numbers in the grid in Sudoku's which have more than one solving?
3) How many possible combinations are there in blank grid? I don't think it's 3^36 (81^9). It should be less, but I cannot count how many.
4) In those breaking-the-rule Sudoku's, which don't break the rule in the way that they would have more same digits in row, column or box, but they are simply unsolveable because of duality of one digit in one place, like is:
Code: Select all
+-------+-------+-------+
| . . 8 | . . . | . . . |
| . . . | . 8 . | . . . |
| . . . | . . . | 2 . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . 8 . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . 8 |
| . . . | . . . | . . . |
+-------+-------+-------+

is there any possibility with less than five digits? I really have doubts, but maybe I am just blind and dumb, who knows...
Guest
 
Posts: 312
Joined: 25 November 2005

Re: Combinations and stuff...

Postby tso » Tue Dec 06, 2005 9:05 pm

Harkonnen wrote:Hello,

I have found that neat game of 'Sudoku' too late (well, I'm 15-year-old, so it wasn't possible much earlier anyway:) )



Actually, Sudoku in its present form is several years older than you.

Harkonnen wrote:... so I haven't been able to (and I will never be able to) read all topics on this forum.


I've found that the SEARCH feature in this forum isn't nearly as effective as going to GOOGLE.COM, click on ADVANCED SEARCH, select ONLY DOMAIN, enter SUDOKU.COM as the domain.

Harkonnen wrote:1) Which is the SMALLEST possible amount of numbers in the grid in Sudoku's which have just one solving?


It hasn't been proven but it is strongly believed that 17 is the minimum.

Harkonnen wrote:2) Which is the BIGGEST possible amount of numbers in the grid in Sudoku's which have more than one solving?


That's easy -- 77. If the last four undecided cells form a rectangle in two boxes, two columns and two rows, each with the same two possibilites, there will be two equally valid solutions.

Code: Select all
. . . |12 .12 | . . .
. . . | . . . | . . .
. . . | . . . | . . .
------+-------+------
. . . |12 .12 | . . .
. . . | . . . | . . .
. . . | . . . | . . .
------+-------+------
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .




Harkonnen wrote:3) How many possible combinations are there in blank grid? I don't think it's 3^36 (81^9). It should be less, but I cannot count how many.



I'm not sure I understand the question -- I'll defer to others and refer you to the Su-Doku's maths thread.

Your answer to the last question seems correct to me.
tso
 
Posts: 798
Joined: 22 June 2005

Postby Shazbot » Tue Dec 06, 2005 9:34 pm

the grid provided for your last question is an invalid grid. You would never come across a puzzle that leads to this situation, unless it were very poorly written.

I agree with all the comments from TSO on your previous questions.
Shazbot
 
Posts: 220
Joined: 24 September 2005

Re: Combinations and stuff...

Postby Crazy Girl » Wed Dec 07, 2005 1:36 am

Harkonnen wrote:3) How many possible combinations are there in blank grid? I don't think it's 3^36 (81^9). It should be less, but I cannot count how many.


Do you mean a noughts and crosses grid where 0 represents a blank cell in a grid and x represents a clue/number in a grid,

eg
Code: Select all
x x x | x 0 0 | 0 0 x
0 0 x | 0 x x | x 0 0
0 0 0 | x 0 0 | 0 0 x 
 
x 0 0 | x 0 0 | x 0 0
x 0 0 | 0 0 0 | 0 0 x
0 0 x | 0 0 x | 0 0 x

x 0 0 | 0 0 x | 0 0 0
0 0 x | x x 0 | x 0 0
x 0 0 | 0 0 x | x x x


So how many non-equivelent grids are there?
Crazy Girl
 
Posts: 189
Joined: 08 November 2005

Postby tso » Wed Dec 07, 2005 3:45 am

Shazbot wrote:the grid provided for your last question is an invalid grid. You would never come across a puzzle that leads to this situation, unless it were very poorly written.



Actually, that was his point. Using only 5 clues, he has set a Sudoku that has no solution. The question is, is it possible to set a Sudoku with less than 5 clues that has no solutions?
tso
 
Posts: 798
Joined: 22 June 2005

Postby PaulIQ164 » Wed Dec 07, 2005 3:11 pm

I don't think it's possible to construct a grid that doesn't contain any number twice in a row/colum/box, yet has no correct solution, with fewer than five numbers. Though there is another way of doing it with five:

Code: Select all
+-------+-------+-------+
| . . 8 | . . . | . . . |
| . . . | . . . | 1 2 3 |
| . . . | 8 . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+


(In fact, there's another way, 'halfway' between the two given, where you use three 8s to restict box 3 to only two places the 8 can be, then put a 1 and a 2 there. My guess is that these are the only significantly different ways to do this, though.)
PaulIQ164
 
Posts: 533
Joined: 16 July 2005

Re: Combinations and stuff...

Postby tso » Wed Dec 07, 2005 7:15 pm

Anonymous wrote:1) Which is the SMALLEST possible amount of numbers in the grid in Sudoku's which have just one solving?


I should have mentioned that though the unproven but likely minimum for a 9x9 Sudoku with 3x3 sub-boxes is 17 -- the minimum for a 9x9 with irregularly shaped sub-boxes is just EIGHT.

Over 30,000 Sudokus with 17 clues can be found here. They cover the entire range of difficulty from trivial to I-wish-I-never-met-you.
tso
 
Posts: 798
Joined: 22 June 2005

Postby Paulie1990 » Thu Dec 08, 2005 7:15 am

Hello

This is me, who wrote those questions, however, I washaving some troubles while logging in with this account, so I have posted it as another account I had done just for that thing

Anyway, thanks you all for your answers, they are really nice.

However, I am afraid, that my question about blank grid hasn't been understood, nevertheless maybe it's because I had asked uncomprehensibly, so I will try in another words.

My question was actually asking of how many Sudoku's there are. That is the same amount as is amount of combinations in blank grid. For example when we have just one digit to fill in, we have ONLY one solution. But how many solutions does blank grid have?
Paulie1990
 
Posts: 4
Joined: 05 December 2005

Postby Paulie1990 » Thu Dec 08, 2005 7:19 am

Paulie1990 wrote:But how many solutions does blank grid have?


Just one more thing: I don't know whether I use good terminology, but for me, blank grid is that grid which has no digits in itself, just those lines marking boxes, in the other words: sudoku with 81 free places...
Paulie1990
 
Posts: 4
Joined: 05 December 2005


Return to General