Home > Archive > Fortran > December 2005 > Re: Mathematical proof on existence: Write a Fortran program to solve Sudoku puzzles
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Re: Mathematical proof on existence: Write a Fortran program to solve Sudoku puzzles
|
|
|
| Many have proposed brilliant ideas to solve the puzzle. But, relevant
to what Richard Maine wrote, I wonder if there is a mathematical proof
that can prove that, given an initial set of numbers in the squares,
there is/are such combination(s) of numbers that fulfill the
requirement of the puzzle. If there are tens, hundreds, or infinite
(rather than unique) of such combinations, this puzzle is not
interesting at all.
In my humble opinion, before we can even think of a way to solve a
problem, we have to scrutinize the problem first.
>
> It is imediately "obvious" that multiple solutions exist in general.
> Consider, for example, the degenerate case where all of the starting
> squares are blank. Every Sudoku solution is also a solution to that
> case. A "good" Sudoku puzzle should have a unique solution, but that is
> what us standards folk might call a "quality of implementation" issue.
>
> --
> Richard Maine | Good judgment comes from experience;
> email: my first.last at org.domain| experience comes from bad judgment.
> org: nasa, domain: gov | -- Mark Twain
| |
| Richard E Maine 2005-12-08, 7:15 pm |
| kis <kisitanggang@gmail.com> wrote:
[about the number of solutions for a given Sudoku puzzle]
> If there are tens, hundreds, or infinite
> (rather than unique) of such combinations, this puzzle is not
> interesting at all.
It certainly isn't infinite, even without appealing to uniqueness as
part of the definition of a "proper" Sudoku puzzle. It is immediately
"obvious" that the number of solutions or a 9x9 Sudoku is no more than
9**81. It doesn't take much work to cut down that figure by mant orders
of magnitude, but in any case, it trivially gives an upper bound.
Admitedly, that is large enough to count as "infinite" even for mutants
with quite a few extra fingers. :-)
--
Richard Maine | Good judgment comes from experience;
email: my first.last at org.domain| experience comes from bad judgment.
org: nasa, domain: gov | -- Mark Twain
|
|
|
|
|