What makes a unique sudoku?

Post Reply New Topic

In a sudoku puzzle, what conditions must be satisfied by the given numbers, to ensure that a unique solution exists? Is there a minimum number of given numbers necessary to ensure a unique solution?

I tried tackling this question a while ago, before forgetting about it. I recently came across a message board where a maths professor admitted to being stumped by the same question, which kind of makes me think I shouldn't waste my time.

Still, I wonder if anyone has any ideas.

A (trivial) 1x1 sudoku grid doesn't need any entries to ensure a unique solution, because there is only one solution (the number one).

A 2x2 sudoku grid only needs one entry to ensure a unique soluton, e.g., the following puzzle (if you can call it a puzzle).



A 3x3 sudoku grid only needs two entries to ensure a unique solution, e.g.,



Unless I am mistaken, a 4x4 sudoku grid seems to need only five entries to ensure a unique solution, e.g.,



Is there a general formula here?

omg... im so good at sudoku

If the two numbers specified in the 3x3 grid are in the same row or column, the solution is not unique:

123
231
312

123
312
231

both start with 12 in the first row.

Are you interested in the minimum number of entries that specify a unique solution, or the number such that if that number of entries is specified, the solution must be unique no matter how the locations are chosen?

The former, although the latter is also an interesting question, which I hadn't thought of asking. I see that the wording I used made it seem like I was actually asking the latter question.

Anyway, looks like I made a mistake with the 4x4 grid. Four entries will suffice to specify a unique solution, e.g.,



As for a 5x5 grid, I think seven entries will suffice, e.g.,



A 6x6 grid could be made up of 6x1 grids or 3x2 grids. Maybe the answer is different for each.
I haven't worked them out yet.

1324
2413
3142
4231

1432
4123
2341
3214

I didn't explain fully, but the 4x4 grid I have illustrated is divided into four 2x2 grids (see how the central vertical and central horizontal lines are darker) so the second solution you've given above is not valid, because, for example,

14
41

is not a valid 2x2 grid.

Of course, I could have divided the 4x4 grids into four 4x1 grids instead, in which case it seems the answer (the minimum number of entries sufficient to guarantee a unique solution) would be different.

It would seem to be simpler to analyze the behaviour without subgrids first, although this is admittedly a different problem.

Have you seen this: http://www.csse.uwa.edu.au/~gordon/sudokumin.php

I hadn't come across that site before. It looks interesting.
I gather they haven't managed to find an answer yet either. It struck me as I was opening it up that I didn't want to read too much, because I want to try to make some progress on my own!

I agree that analyzing matrices without subgrids would be a good place to start. The answer for each undivided n x n matrix would probably give an "upper bound" to the answer for the corresponding "divided" n x n matrix.

There is another (related?) problem I've come up with that is simpler still, yet I haven't managed to find an answer to it either. Take an n x n matrix and fill some of the squares with objects (say, beads, or whatever). Then proceed as follows:

If there is any unfilled square such that the number of objects in the same column plus the number of objects in the same row is greater than or equal to n-1, then fill that square with another object. Eventually, if you have started with enough objects, and if they have been put in the correct locations, you should be able to fill the entire matrix.

What is the minimum number of starting objects sufficient for an n x n matrix?

For a 6 x 6 matrix, ten objects is sufficient, although it might work with a lower number and I just haven't worked out how.

E.g., with a 6 x 6 matrix, we could start with the configuration shown (with red objects) and proceed by adding blue objects as illustrated.



Etc.

Lucky you - I'm not!

Btw, the National Autistic Society in the UK is using Sudoku to raise funds. Check this site out -->

http://www.sudokuthon.org.uk/play/index.cfm

There is a 6x6 arrangement with only 9 that is very similar to your pattern:



OOOOOO
XXOOOO
OXXOOO
OOXOOO
OOXXOO
OOOXXO

For your second problem, I believe the number required to force an nXn block to be filled is

n = (n^2 - 1) / 4 for n odd

n = n^2 / 4 for n even

Nice one. That seems to work.

Any idea why?

There is a simple pattern that works for all n, although it is slightly different for the even and odd cases. It looks like:

OOOOOOOOOOO
OOOOXOOOOOO
OOOXXOOOOOO
OOXXXOOOOOO
OXXXXOOOOOO
XXXXXOOOOOO
OOOOOXXXXXO
OOOOOXXXXOO
OOOOOXXXOOO
OOOOOXXOOOO
OOOOOXOOOOO

The step like pattern allows the addition of an X to permit the addition of an additional X. This could probably be formalized into a mathematical proof, but I'm happy with a simple hand waving arguement for now.

Along these lines, I have wondered before how the programs work that create the sudoku in the newspaper, puzzle books, etc. I have heard that they are all generated by a computer program.

I haven't thought about it much, but I wonder if someone has invented an algorithm that's sure to generate uniquely solvable puzzles, or if the program just has a whole bunch of "templates" in its memory that have shown to work and that it can modify. It is clear that, from a single uniquely solvable puzzle, a large number of others can be generated simply by scrambling the order of the rows and columns within sets of adjacent sub-grids, permuting rows and/or columns of sub-grids, exchanging the horizontal and vertical axes, and replacing one number with another (for example the 2s become 4s and the 4s become 2s). These would all be "equivalent" puzzles in logical terms, though I don't know if expert sudoku solvers could recognize that they are in fact essentially the same, if a lot of these scrambling operations are carried out one after the other.

I suppose the program could also add numbers one by one and try solving the puzzle after each one, using artificial intelligence, though that would be computationally really expensive.

Also, I wonder how difficulty is determined. It can't be just based on how many more hints are given than are required, because I've seen sudoku with relatively few hints that had one or two stars.

I've wondered this too. If I remember rightly, the last time I looked at a Sudoku puzzle in the paper, the paper gave the name of the sudoku compiler above. I wondered how much the guy was being paid if it's just a matter of running a computer program.

I've been trying to figure out how many different n x n "grids without subgrids" are possible, and I came across something that seemed quite counter-intuitive to me.

I'd assumed that to find, for instance, the number of possible 6x6 grids, you'd start with the number of possible permutations for the first row ( 6! = 720 ). Then you'd choose an arbitrary permutation for the first row, and work out how many possibilities that left for the second row (it seems to be 265). Then you'd arbitrarily choose on of those permutations for the second row and then move on to the third row, and so on. Finally, to find the number of possible 6x6 grids, you'd multiply together the numbers for each row ( 720 x 265 x ... etc).

But it seems that the results can be different depending on which choices you make. For example, if you have the following arrangement for the first four rows:

1 2 3 4 5 6
2 3 4 5 6 1
3 4 5 6 1 2
4 5 6 1 2 3

This leaves only two possibilities for the fifth row, namely:

5 6 1 2 3 4 ... or ...
6 1 2 3 4 5

But if you instead have the following arrangement for the first four rows:

1 2 3 4 5 6
2 1 4 3 6 5
3 4 5 6 1 2
4 3 6 5 2 1

You now have eight possibilities for the fifth row:

5 6 1 2 3 4 ... or ...
5 6 1 2 4 3 ... or ...
5 6 2 1 3 4 ... or ...
5 6 2 1 4 3 ... or ...
6 5 1 2 3 4 ... or ...
6 5 1 2 4 3 ... or ...
6 5 2 1 3 4 ... or ...
6 5 2 1 4 3

Maybe it's just me, but this was kind of unexpected, although it makes some sort of sense when I compare the two arrangements.

So does anyone know how many 6x6 grids of this type are actually possible?
(And I used a computer program to help me with this!)