What is the minimun number of digits/symbols required to give a unique answer
in a SODOKU problem?

Regards
Mongolia

---

Request for Question Clarification by pafalafa-ga on 13 Feb 2006 18:11 PST

I assume you're asking about the puzzle I know as Sudoku, but also
sometimes called Sodoku.

I'm not sure I get your question, though.  There's a fixed number of
boxes in a given puzzle (though the number can vary from puzzle to
puzzle).

So if a puzzle has, say, 81 boxes, wouldn't it very simply take 81
digits to provide a unique answer?

If you're asking if a puzzle can be answered by using less that all
the digits 1 through 9, the rules generally require an answer that
uses each and every digit (1-9) once, in each 3x3 box.

What am I missing?

pafalafa-ga

---

Clarification of Question by mongolia-ga on 13 Feb 2006 18:21 PST

pafalafa

First apologies for the spelling. I am indeed indeed talking about Sudoku
and i am refering to the standard 9 by 9 variety (i.e. 81 squares)Now a typical
 Sudoku game may have say 3 to 5 digits in each 3 by 3 square. (that
is to begin with) Lets say there were exactly 4 digits per each 3 by 3
square. That would make a total of 36 digits to start.

My question is what is the MATHEMATICAL minimum number of digits
required to give a solution which is unique?

Hope this helps

Mongolia

Interesting question.  He is asking what is the minimum number of
numbers that need to be given at the start of the puzzle to ensure a
unique solution to the puzzle.

But there are a few versions of the 9 by 9 Sudoku puzzle.

1.  All puzzles require each number 1 thru 9 to appear once in each
row, column, and 3 by 3 box.  But what about the two main diagonals? 
Do you also require both of the two main diagonals to contain each
number 1 thru 9?

2.  For the numbers given at the start of the puzzle, are they
required to be symmetrical about the center square (i.e. if there is a
number given at the start of the puzzle in the upper right corner of
the puzzle, there is also a number in the lower left corner)? 
Symmetry makes the puzzle prettier.

Two examples:

1.  The daily Sudoku puzzle in the Los Angeles Times requires each
number 1 thru 9 to appear once in each row, column, and box, but there
is no special requirement for the diagonals.  The numbers given at the
start of the puzzle are always symmetrical about the center square.

2.  The puzzle that appeared recently in the Readers Digest required
each number 1 thru 9 to appear once in each row, column, box, and
diagonal (the two mian diagonals).  The numbers given at the start of
the puzzle were not required to be symmetrical about the center
square.

You could ask here:
http://www.sudoku.org.uk/

I was intrigued to find that the example under "solving sudoku
document" labeled "gentle" had 29 numbers, as did a couple given has
ultra-difficult under "unsolvable sudoku"  (half way down the page). 
28 numbers is the lowest I found in my very brief search, which
suggests to me that there may be a formula to prove that this is the
minimal number required  (?   3^3 + 1  Relates nicely to 3x3 blocks of
3x3 with an added number required to make solution possible.).

The puzzles on the site all follow the symmetrical rule, something I
just hadn't noticed before.

The issue is not just the number of numbers but the combination of
them (providing  all 9 instances of "3" is of different value to one
instance each of "1" to "9") and their positioning (intersection of
datasets provides the basis of the elimination process).  It comes
down to how many Trits of information are required and provided by
each number given.

To prove a minimum mathematically is an interesting challenge...and
not straightforward.

poet

I have seen some puzzles that follow the symmetrical rule that give
only 26 numbers at the beginning.  So the minimum number of numbers
required at the beginning is at least that low.

From http://www.csse.uwa.edu.au/~gordon/sudokumin.php

"This page is concerned with the question of what is the smallest
number of entries in a Sudoku puzzle that has a unique completion.

At the moment, there are examples of 17-hint uniquely completable
Sudoku puzzles, but no known 16-hint examples. Hence I am collecting
as many 17-hint examples as possible, in the hope that their analysis
will yield some insight.

Currently I have a collection of 36628 distinct Sudoku configurations
with 17 entries"

Search strategy: sudoku minimum

Having looked at Brx24-ga's link I believe he has come close to
answering my question  (i.e. the minimum is 17)

So I would like to set a litte challenge If anyone knows of a puzzle
with only 16 entries Please send it to me.

And failing that has anyone attempted a mathematical proof that the minimum is 17?

Regards
Mongolia

BTW I am of course refering to the "bog standard" version of Sudoku.
The entries do not have to be in any way symmetrical and there is no
restiction suggesting that the two diagonals contain digits 1 to 9.

Mongolia,

There's a lengthy thread here that may be of interest to you:

http://www.sudoku.com/forums/viewtopic.php?t=605&start=0

There's a recent claim of a proof that the minimum is equal to or greater than 17:

http://www.sudoku.com/forums/viewtopic.php?t=2984&postdays=0&postorder=asc&start=0

There seem to be questions that some have about the proof but the
originator hasn't returned to the thread yet.

He is listed as VP, Engineering in his profile.

It would be inteeresting to try to look at sudoku as a system of
equations (27 equations, actually...9 across, 9 down, 9 boxes). 
Rather than using 1-9 use the 1st 9 primes.  Make sure that all 27
equations equal 223092870=2*3*5*7*11*13*17*19*23.
Since the sudoku problem could be mapped to a system of equations it
could be proven using mathematical techniques, what are the minimum
number of variables required for the system to have one unique
solution.  I'm a bit rusty on linear algebra, but I would assume there
are some tools out there to optimize a system like that.

Odds are someone has already tried this approach...but I thought I'd
put the idea out there anyway.

It depends on the game difficulty....it can range from 27 (difficult) to 36(easy)