| Author |
Topic:
Mathematicians Solve Minimum Sudoku Problem
[Locked] |
Scarne
Title: Capo di Scientifico
Posts: 1,087
Registered: 2001-7-23 15:24:34
|
Date Posted:
1/1/00 12:00am
Subject:
Mathematicians Solve Minimum Sudoku Problem
|
http://www.technologyreview.com/blog/arxiv/27469/
They used brute force to prove that all the puzzles with 16 clues (or fewer by simple inductive proof) have at least 2 solutions. 
-----signature-----
E Pluribus Unum
|
|
|
Date Posted:
1/1/00 12:00am
Subject:
Mathematicians Solve Minimum Sudoku Problem
|
Why would anyone want to know this?
-----signature-----
We have not inherited the Earth from our parents, we have borrowed it from our children.
|
Ptilk
Title: Creepy old pirate
Posts: 2,359
Registered: 2002-2-13 14:52:58
|
Date Posted:
1/1/00 12:00am
Subject:
Mathematicians Solve Minimum Sudoku Problem
|
Why would anyone want to know the batting averages for every player on the 1952 Cubs? People do though.
This actually has some use...unlike the Cubs. 
|
paulg_68
Posts: 2,469
Registered: 2009-7-27 18:45:54
|
Date Posted:
1/1/00 12:00am
Subject:
Mathematicians Solve Minimum Sudoku Problem
|
Eternal_Midnight posted:
Why would anyone want to know this?
Didn't read the article but I bet it was someone trying for their PHD in math.
It's tough to come up with an original thesis after a million other people got to choose theirs first.
-----signature-----
If you wish to make an apple pie from scratch...
http://www.youtube.com/watch?v=zSgiXGELjbc
"Everyone has a chance to become rich." - Groucho48
"Most of the human wealth on earth exists between the ears of live human beings." - theredkay1
|
eodoll
Posts: 1,028
Registered: 2002-2-14 12:35:42
|
Date Posted:
1/1/00 12:00am
Subject:
Mathematicians Solve Minimum Sudoku Problem
|
|
Im interested to know whats the minimum number required to guarantee that there is only one unique solution? I guess its 18 or 19.
|
paulg_68
Posts: 2,469
Registered: 2009-7-27 18:45:54
|
Date Posted:
1/1/00 12:00am
Subject:
Mathematicians Solve Minimum Sudoku Problem
|
Nah, it would be a lot more than that. Imagine if you just filled in all 27 on the three top sections. There would still be tons of possible solutions for the lower 54.
-----signature-----
If you wish to make an apple pie from scratch...
http://www.youtube.com/watch?v=zSgiXGELjbc
"Everyone has a chance to become rich." - Groucho48
"Most of the human wealth on earth exists between the ears of live human beings." - theredkay1
|
ZigmundZag
Title: Grammar Nazi
Posts: 1,211
Registered: 2002-3-25 23:03:00
|
Date Posted:
1/1/00 12:00am
Subject:
Mathematicians Solve Minimum Sudoku Problem
|
eodoll posted:
Im interested to know whats the minimum number required to guarantee that there is only one unique solution? I guess its 18 or 19.
If all puzzles of 16 or fewer clues have two or more solutions, then I'm assuming the inverse is true - that a puzzle with at least 17 clues could have as few as 1 solution.
EDIT: Oh, I see what you're getting at now. Paul already answered it. Placement of the clues is key. You could make a poor Sudoku with probably half the clues and multiple solutions still available.
-----signature-----
"Take the cheese to sickbay!"
|
eodoll
Posts: 1,028
Registered: 2002-2-14 12:35:42
|
Date Posted:
1/1/00 12:00am
Subject:
Mathematicians Solve Minimum Sudoku Problem
|
|
Interesting, so what would be the minimum number to guarantee that there is a unique solution? 70?
|
ZigmundZag
Title: Grammar Nazi
Posts: 1,211
Registered: 2002-3-25 23:03:00
|
Date Posted:
1/1/00 12:00am
Subject:
Mathematicians Solve Minimum Sudoku Problem
|
Well, you could still have multiple solutions if all but two lines were complete and the two lines were blank...so that would be 63. If the cubes used their numbers in such a way that the undiscovered numbers used values that were already in the clues for the subset of 3 grids I think you could probably stretch it even further, maybe to 70. There's probably a mathematical way to get it all the way to 77 but I can't think of it.
-----signature-----
"Take the cheese to sickbay!"
|
|
|
Date Posted:
1/1/00 12:00am
Subject:
Mathematicians Solve Minimum Sudoku Problem
|
did i ever mention that i hate numbers?
-----signature-----
Jesus? No, but there is indeed a god shaped hole in the heart of man, why is yours so empty? -- snarf igraine
the original monotheism: http://en.wikipedia.org/wiki/Phallus
|
