Write a Fortran program to solve Sudoku puzzles :-)

[AN O'Nymous]

The layperson goes through the drudgery of solving Soduku puzzles by
hand. However, us being somewhat more sophisticated, we prefer to let a
computer do it for us. Engineers don't cheat - we just use better tools
:-)

So here's the challenge: can anyone write a Fortran program that can
consistently, and better yet, efficiently solve any Sudoku puzzle of
standard format? A bit of Googling around would show that we would not
be the first to try...

For the purposes of this challenge, we will assume that a "passing
grade" of consistency is being able to solve 95/100 randomly generated
Sudoku challenges (which will be equal for all contenders).

For the uninitiated:
http://en.wikipedia.org/wiki/Sudoku

I've been thinking about it a bit, and being a tad inexperienced, the
immediate one that came to mind was an exhaustive trial-and-error
algorithm. Quite inefficient, but essentially 100% consistent.

I will need to think about this one over the weekend. Does anyone know
if *every* Sudoku puzzle has one unique, correct solution or if there
are usually multiple solutions?

[Richard E Maine]

Post by AN O'Nymous
I will need to think about this one over the weekend. Does anyone know
if *every* Sudoku puzzle has one unique, correct solution or if there
are usually multiple solutions?

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.

[Mr Hrundi V Bakshi]

Post by Richard E Maine

Post by AN O'Nymous
I will need to think about this one over the weekend. Does anyone know
if *every* Sudoku puzzle has one unique, correct solution or if there
are usually multiple solutions?

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.

Baloney. A valid Sudoku is never blank (unlike you, we don't all have open
ended deadlines, some of us actually work for a living) and by design and
as appears in countless newspapers for the masses, it has a unique
solution. Try doing one.

--
Tsk,
Hrundi V.B.

[Michael Metcalf]

Post by Richard E Maine

Post by AN O'Nymous
I will need to think about this one over the weekend. Does anyone know
if *every* Sudoku puzzle has one unique, correct solution or if there
are usually multiple solutions?

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.

I don't think so, it is more a matter of definition. I think most solvers
regard a sudoku as having one solution, otherwise it's simply not a sudoku.
There was an infamous case last summer in the UK. Sky television, with
blasts of trumpets, staged a live sudoku contest in which participants had
to solve the puzzle below. The contest collapsed in chaos when it became
apparent that it has over 1000 (!) solutions.

Regards,

Mike

0 0 0 3 0 5 0 0 0 Sky One v. hard

0 9 0 0 0 0 0 6 0

0 0 0 0 6 0 0 0 0

5 0 0 0 2 0 0 0 8

0 0 8 4 0 7 3 0 0

4 0 0 0 9 0 0 0 7

0 0 0 0 4 0 0 0 0

0 1 0 0 0 0 0 4 0

0 0 0 6 0 8 0 0 0

[Richard E Maine]

Post by Michael Metcalf

Post by Richard E Maine

Post by AN O'Nymous
I will need to think about this one over the weekend. Does anyone know
if *every* Sudoku puzzle has one unique, correct solution or if there
are usually multiple solutions?

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.

I don't think so, it is more a matter of definition. I think most solvers
regard a sudoku as having one solution, otherwise it's simply not a sudoku.

Oh. Ok. I've certainly also seen published "sudokus" where I personally
found multiple solutions (but not thousands :-)). If, as you say, it is
a matter of definition, then I suppose that they weren't really sudokus
in the same sense that one might say that nonstandard Fortran copde
isn't really Fortran.

[Michael Metcalf]

"Richard E Maine" <***@see.signature> wrote in message news:1h6xmh0.1wpudbq1xl2scoN%***@see.signature...
.

Post by Richard E Maine
Oh. Ok. I've certainly also seen published "sudokus" where I personally
found multiple solutions (but not thousands :-)). If, as you say, it is
a matter of definition, then I suppose that they weren't really sudokus
in the same sense that one might say that nonstandard Fortran copde
isn't really Fortran.
--
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

[Michael Metcalf]

Post by Richard E Maine

Post by Michael Metcalf

Post by Richard E Maine
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.

I don't think so, it is more a matter of definition. I think most solvers
regard a sudoku as having one solution, otherwise it's simply not a sudoku.

Oh. Ok. I've certainly also seen published "sudokus" where I personally
found multiple solutions (but not thousands :-)). If, as you say, it is
a matter of definition, then I suppose that they weren't really sudokus
in the same sense that one might say that nonstandard Fortran copde
isn't really Fortran.

Right. I think the "quality of implementation" factor is whether the puzzle
can be solved by the application of pure logic or whether, at some stage, a
guess and possible backtracking (Thread of Ariadne) are required. Solvers
seem to be divided on this issue. My program can create both types, but I
normally reject those requiring guesswork.

Regards,

Mike

[R. Vowels]

Michael Metcalf wrote in message ...

Post by Michael Metcalf
Right. I think the "quality of implementation" factor is whether the puzzle
can be solved by the application of pure logic or whether, at some stage, a
guess and possible backtracking (Thread of Ariadne) are required.

According to statements published with the Sudoku puzzles,
only logic is required. Guesswork is never mentioned.

Post by Michael Metcalf
Solvers
seem to be divided on this issue. My program can create both types, but I
normally reject those requiring guesswork.
Regards,
Mike

[James Parsly]

I'd only encountered the 9x9 ones in the local newspaper, and I assume that
this sort would only have 1 solution, since they always publish the solution
the
next day without any indication that isn't a unique solution.

My solution method depends on this, in fact. It starts out by assuming that
all digits are possible
in the blank spots, and iterates through the squares applying a series of
tests
to eliminate digits. A spot is solved when the possible digits are whittled
down to 1, or
when a digit remains possible in only one of the spots within its row,
column, or 3x3
subsquare.

Essentially all I did was think about how I was solving them by hand, and
then make
the computer do the same thing. If it got stuck, I'd figure out what I'd do
to get going
again, and add that behavior into the program. Stuff like, "If you can
narrow a spot
down to 2 possibilities, and another spot in the same row, or column, or 3x3
subsquare,
can also be narrowed down to the same 2, then these two possibilities can be
eliminated from the remaining spots in the row, column, or 3x3 subsquare."

My next step would probably have been to generalize this rule to work with
n digits in n spots. This is harder than the 2 digit case, cause you'd have
to
detect cases where the possibilities were something like (1 and 3), (2 and
3), (1 and 2).

But, it was solving all the puzzles with the rules I had built into it, so I
lost interest.

Post by Richard E Maine

Post by Michael Metcalf

Post by Richard E Maine

Post by AN O'Nymous
I will need to think about this one over the weekend. Does anyone know
if *every* Sudoku puzzle has one unique, correct solution or if there
are usually multiple solutions?

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.

I don't think so, it is more a matter of definition. I think most solvers
regard a sudoku as having one solution, otherwise it's simply not a sudoku.

Oh. Ok. I've certainly also seen published "sudokus" where I personally
found multiple solutions (but not thousands :-)). If, as you say, it is
a matter of definition, then I suppose that they weren't really sudokus
in the same sense that one might say that nonstandard Fortran copde
isn't really Fortran.
--
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]

Post by James Parsly
I'd only encountered the 9x9 ones in the local newspaper, and I assume that
this sort would only have 1 solution, since they always publish the solution
the next day without any indication that isn't a unique solution.

I once solved one of those newspaper ones, but then found that my
solution did not match the published one. Rechecked and verified that
they were both valid solutions.

Just because they publish what they say is "the" solution, that shows
that they thought it to be unique, but not that they were correct.

[Gordon Sande]

Post by Richard E Maine

Post by James Parsly
I'd only encountered the 9x9 ones in the local newspaper, and I assume that
this sort would only have 1 solution, since they always publish the solution
the next day without any indication that isn't a unique solution.

I once solved one of those newspaper ones, but then found that my
solution did not match the published one. Rechecked and verified that
they were both valid solutions.
Just because they publish what they say is "the" solution, that shows
that they thought it to be unique, but not that they were correct.

I thought they just published a solution to show that one existed.
Mostly it was for folks who had not found a solution. If you find
a solution it is easy to verify that you have a valid one. At that
point most folks loose interest in seeing if their solution is the
same as the one published.

The fact that you checked only shows that you wasted too many
years taking advanced mathematics where issues like uniqeness
of solution get discussed. <<Many smilies!>> It is surprising
how often folks who have taken one or two courses in calculus
seem to be surprised when discrete mathematics problems have
multiple solutions.

[Michael Metcalf]

Post by James Parsly
But, it was solving all the puzzles with the rules I had built into it, so
I lost interest.

Try the one I posted earlier today!

Regards,

Mike Metcalf

[Kay Diederichs]

Post by Michael Metcalf

Post by James Parsly
But, it was solving all the puzzles with the rules I had built into it, so
I lost interest.

Try the one I posted earlier today!
Regards,
Mike Metcalf

I believe you mean
3 5
9 6
6
5 2 8
84 73
4 9 7
4
1 4
6 8
?


My little Fortran program tells me that

146375829
395281764
782964531
567123498
928457316
431896257
673549182
819732645
254618973

solves that puzzle, but e.g.

146375289
395281764
872964153
567123498
928457316
431896527
283549671
619732845
754618932

is also a solution (my program found all 10868 solutions in 0.3 seconds).

However, wikipedia says that ...
=============
Construction

It is possible to set starting grids with more than one solution and to set
grids with no solution, but such are not considered proper Sudoku puzzles; like
most other pure-logic puzzles, a unique solution is expected.
=============

... which the above puzzle does not meet.

Does anybody know what the (uniquely solvable) sudoku with the smallest number
of preset numbers is?

Kay
------------ And now a word from our sponsor ---------------------
For a secure high performance FTP using SSL/TLS encryption
upgrade to SurgeFTP
---- See http://netwinsite.com/sponsor/sponsor_surgeftp.htm ----

[Michael Metcalf]

Post by Kay Diederichs
However, wikipedia says that ...
=============
Construction
It is possible to set starting grids with more than one solution and to
set grids with no solution, but such are not considered proper Sudoku
puzzles; like most other pure-logic puzzles, a unique solution is
expected.
=============
... which the above puzzle does not meet.

Quite so. That's why the Sky TV show collapsed into chaos, reports say.

Post by Kay Diederichs
Does anybody know what the (uniquely solvable) sudoku with the smallest
number of preset numbers is?

No, but I believe I once saw some with only 19, constructed using AI
techniques. I can manage only mid- to upper-20s. Here's one I made with 26
("circle and 2 dots"):

. . 1 7 9 4 6 . .

. 2 . . . . . 1 .

6 . . . . . . . 7

9 . . . . . . . 6

8 . . 4 . 3 . . 5

2 . . . . . . . 3

5 . . . . . . . 1

. 7 . . . . . 8

. . 3 5 8 1 2 . .

Try it by hand, though; comments welcome. Solving sudokus by program is
boring, although writing the programs can be fun.

Regards,

Mike Metcalf

[Jan Vorbrüggen]

Post by Michael Metcalf
Try it by hand, though; comments welcome. Solving sudokus by program is
boring, although writing the programs can be fun.

Agreed. However, it would be nice to have a little program that supports
one in filling it out; pencil and eraser can be a bit tedious.

I was surprised that one I found in an airline magazine with 23 entries was
actually solveable without guesswork and backtracking...but it did require
some time to get over several stumbling blocks at which I needed to invent
a new rule in order to make forward progress 8-).

Jan

[Michael Metcalf]

Post by Jan Vorbrüggen

Post by Michael Metcalf
Try it by hand, though; comments welcome. Solving sudokus by program is
boring, although writing the programs can be fun.

Agreed. However, it would be nice to have a little program that supports
one in filling it out; pencil and eraser can be a bit tedious.

Use Excel. You can even add colour to distinguish the givens from your own
entries and to mark guesses, and then use the undo button to backtrack.

Regards,

Mike Metcalf

[Michael Metcalf]

Post by Michael Metcalf
Use Excel. You can even add colour to distinguish the givens from your own
entries and to mark guesses, and then use the undo button to backtrack.

In particular, go to the bottom right corner of
http://www.simetric.co.uk/sudoku/index.htm.

Regards,

Mike Metcalf

[Mark B Stucky]

Post by Jan Vorbrüggen

Post by Michael Metcalf
Try it by hand, though; comments welcome. Solving sudokus by program is
boring, although writing the programs can be fun.

Agreed. However, it would be nice to have a little program that supports
one in filling it out; pencil and eraser can be a bit tedious.
I was surprised that one I found in an airline magazine with 23 entries was
actually solveable without guesswork and backtracking...but it did require
some time to get over several stumbling blocks at which I needed to invent
a new rule in order to make forward progress 8-).
Jan

You might want to try the program at

http://web.tiscali.it/irrational/tcl/sudoku-0.7.1/index.html

--Mark

[Joost]

Post by Michael Metcalf

Post by Kay Diederichs
Does anybody know what the (uniquely solvable) sudoku with the smallest
number of preset numbers is?

No, but I believe I once saw some with only 19, constructed using AI
techniques. I can manage only mid- to upper-20s. Here's one I made with 26

17 givens seems to be enough to yield unique sudokus. The following
link might be of interest:

http://en.wikipedia.org/wiki/Mathematics_of_Sudoku

Joost

[Herman D. Knoble]

Joost: Thanks.

Another TCL (command line) implementation (one file) is at:
http://sourceforge.net/projects/sudokut

This comes with extensive documentation (sudokut.html) and has been
tested on more difficult puzzles (E.g. all of Top95 and impossible_520).
It is fast and also solves puzzles with multiple solutions outputing
(and numbering) all possible solutions.

The TCL code distributed works for me under Windows or Linux (provided
TCL is properly installed. Input is flexible and the command line
options (implemented in TCL of course) allow -f inputfileid
as well as an 81 character notation directly as part of the command line.

Example: tclsh sudokut -f test.inp > solution.out

where test.inp can be one of many forms as given in the
documentation file.

Skip


On 8 Dec 2005 09:48:48 -0800, "Joost" <***@cam.ac.uk> wrote:

-|> > Does anybody know what the (uniquely solvable) sudoku with the smallest
-|> > number of preset numbers is?
-|> >
-|>
-|> No, but I believe I once saw some with only 19, constructed using AI
-|> techniques. I can manage only mid- to upper-20s. Here's one I made with 26
-|
-|17 givens seems to be enough to yield unique sudokus. The following
-|link might be of interest:
-|
-|http://en.wikipedia.org/wiki/Mathematics_of_Sudoku
-|
-|Joost

[Michael Metcalf]

Here's one I produced to keep you out of mischief over the weekend. I'll
post the solution on Monday.

Regards,

Mike Metcalf


2 0 0 0 0 0 0 5 0

0 0 0 8 9 1 0 0 3

0 0 7 0 0 0 0 0 0

0 0 0 0 0 0 0 0 7

0 0 0 3 0 2 8 9 0

0 7 5 0 0 0 4 0 0

0 0 0 0 8 5 0 0 0

0 0 2 0 1 0 0 0 0

0 0 0 7 0 3 1 0 0

[Herman D. Knoble]

Mike: I posted a reference to a TCL Sudoku solver today.
Running your puzzle with it produces:

Sudoku 1
Current sudoku:
200000050000891003007000000000000007000302890075000400000085000002010000000703100
-----------------------
| 2 0 0 | 0 0 0 | 0 5 0 |
| 0 0 0 | 8 9 1 | 0 0 3 |
| 0 0 7 | 0 0 0 | 0 0 0 |
|-------|-------|-------|
| 0 0 0 | 0 0 0 | 0 0 7 |
| 0 0 0 | 3 0 2 | 8 9 0 |
| 0 7 5 | 0 0 0 | 4 0 0 |
|-------|-------|-------|
| 0 0 0 | 0 8 5 | 0 0 0 |
| 0 0 2 | 0 1 0 | 0 0 0 |
| 0 0 0 | 7 0 3 | 1 0 0 |
-----------------------
Solving...
Found 1 solution
Solution 1:
-----------------------
| 2 9 8 | 4 3 7 | 6 5 1 |
| 6 5 4 | 8 9 1 | 2 7 3 |
| 1 3 7 | 5 2 6 | 9 8 4 |
|-------|-------|-------|
| 8 2 9 | 1 5 4 | 3 6 7 |
| 4 6 1 | 3 7 2 | 8 9 5 |
| 3 7 5 | 9 6 8 | 4 1 2 |
|-------|-------|-------|
| 9 1 3 | 2 8 5 | 7 4 6 |
| 7 4 2 | 6 1 9 | 5 3 8 |
| 5 8 6 | 7 4 3 | 1 2 9 |
-----------------------
Solved in 1.428 seconds

Skip

On Fri, 09 Dec 2005 17:06:39 GMT, "Michael Metcalf" <***@compuserve.com> wrote:

-|Here's one I produced to keep you out of mischief over the weekend. I'll
-|post the solution on Monday.
-|
-|Regards,
-|
-|Mike Metcalf
-|
-|
-|2 0 0 0 0 0 0 5 0
-|
-|0 0 0 8 9 1 0 0 3
-|
-|0 0 7 0 0 0 0 0 0
-|
-|0 0 0 0 0 0 0 0 7
-|
-|0 0 0 3 0 2 8 9 0
-|
-|0 7 5 0 0 0 4 0 0
-|
-|0 0 0 0 8 5 0 0 0
-|
-|0 0 2 0 1 0 0 0 0
-|
-|0 0 0 7 0 3 1 0 0
-|
-|

[Michael Metcalf]

Post by Herman D. Knoble
Mike: I posted a reference to a TCL Sudoku solver today.

[snip]

Thanks, pal. I hope people interested in doing it the hard way don't see
your post!!!! Like I've said before, using programs is boring.

Mike

[Herman D. Knoble]

Mike: I'm sorry that I messed this up. I canceled the posting.
Skip

On Fri, 09 Dec 2005 17:37:15 GMT, "Michael Metcalf" <***@compuserve.com> wrote:

-|
-|"Herman D. Knoble" <***@SPAMpsu.DOT.edu> wrote in message
-|news:***@4ax.com...
-|> Mike: I posted a reference to a TCL Sudoku solver today.
-|> Running your puzzle with it produces:
-|[snip]
-|
-|Thanks, pal. I hope people interested in doing it the hard way don't see
-|your post!!!! Like I've said before, using programs is boring.
-|
-|Mike
-|

[Michael Metcalf]

Post by Herman D. Knoble
Mike: I'm sorry that I messed this up. I canceled the posting.
Skip

Skip,
Thanks, no sweat. By way of upping the ante, here is a supersudoku
(16x16). Masochists can ask me by e-mail for a megasudoku (25x25, perhaps
too big to fit in here). I'll post the solution next Friday. It takes my
program 330msecs to solve this.

Regards,

Mike

2 0 0 0 0 0 9 0 0 0 0 0 14 1 0 15

0 0 0 1 0 0 0 0 0 0 0 8 6 9 0 0

0 0 0 0 0 0 0 0 0 10 0 1 0 0 13 7

0 11 0 0 6 10 0 0 0 0 7 12 0 0 0 0

0 0 0 0 0 6 1 14 10 12 0 3 0 0 0 0

6 0 0 4 0 0 0 13 16 0 0 0 7 0 0 0

0 0 10 0 0 11 0 0 0 0 8 0 0 14 16 0

9 0 0 13 16 0 0 2 0 0 0 4 5 0 0 11

16 0 0 15 5 0 0 0 7 0 0 14 9 0 0 0

0 13 11 0 0 7 0 0 0 0 3 0 0 12 4 0

12 0 0 2 0 0 0 4 6 0 0 0 3 0 0 14

0 0 0 0 15 0 13 6 8 0 1 11 0 2 0 0

0 7 0 0 8 13 0 0 0 0 4 16 0 0 0 0

10 1 0 0 3 0 12 0 0 6 0 0 0 0 14 5

0 0 15 3 1 0 0 0 0 0 0 2 4 13 9 0

5 0 16 0 0 0 0 0 0 3 0 0 10 7 0 6

[Jan Vorbrüggen]

By way of upping the ante, here is a supersudoku (16x16).

Of course, such a puzzle should be using 0-9, A-F instead of 1-16 for
its digits...

Jan

[Michael Metcalf]

Post by Jan Vorbrüggen

By way of upping the ante, here is a supersudoku (16x16).

Of course, such a puzzle should be using 0-9, A-F instead of 1-16 for
its digits...

In fact, 1-9, A-G is sometimes used.

Regards,

Mike

[Michael Metcalf]

Post by Herman D. Knoble
Mike: I posted a reference to a TCL Sudoku solver today.
-----------------------
Solved in 1.428 seconds

P.S. It took my program 23 secs to produce this (hard) puzzle and 20msecs to
solve it.

Regards,

Mike Metcalf

[Mr Hrundi V Bakshi]

Post by Richard E Maine

Post by Michael Metcalf

Post by Richard E Maine

Post by AN O'Nymous
I will need to think about this one over the weekend. Does anyone know
if *every* Sudoku puzzle has one unique, correct solution or if there
are usually multiple solutions?

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.

I don't think so, it is more a matter of definition. I think most solvers
regard a sudoku as having one solution, otherwise it's simply not a sudoku.

Oh. Ok. I've certainly also seen published "sudokus" where I personally
found multiple solutions (but not thousands :-)).

Show one, and cite your pubished source, you phoney bullshitter.

[Gib Bogle]

This post might be inappropriate. Click to display it.

[kis]

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.

Post by Richard E Maine
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]

kis <***@gmail.com> wrote:

[about the number of solutions for a given Sudoku puzzle]

Post by kis
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. :-)

[Michael Metcalf]

Post by AN O'Nymous
So here's the challenge: can anyone write a Fortran program that can
consistently, and better yet, efficiently solve any Sudoku puzzle of
standard format? A bit of Googling around would show that we would not
be the first to try...

I have written a program in Fortran 95 that, for all square sudokus from 2 x
2 to 36 x 36:

1) solves any puzzle, and reports whether there is a unique or multiple
solutions (but not how many if multiple);

2) can generate puzzles that are either asymmetric, symmetric, have unique
solutions, or have several solutions (this option is normally disabled), and
assesses their degree of difficulty (but for 36 x 36 only a special class is
possible);

3) can generate completed grids (potential solutions) from scratch -- this
is a special case of 1) above;

4) can generate a puzzle of a fixed shape - an early attempt is attached as
my Season's Greetings to the group (and Long Live the where statement!)

Mike Metcalf

[Michael Metcalf]

Post by Michael Metcalf
I have written a program in Fortran 95 that, for all square sudokus from 2 x

For '2 x 2' read '4 x 4'

Post by Michael Metcalf
2) can generate puzzles that are either asymmetric, symmetric, have unique
solutions, or have several solutions (this option is normally disabled), and

should read

2) can generate puzzles that are either asymmetric or symmetric, have unique
solutions, and do not or do require guesses (this option is normally
disabled), and

[AN O'Nymous]

Interesting, Michael. What technique (e.g. Tabu, simulated annealing,
partial enumerative, ...?) does your algorithm use to solve it, and
what decision rules do you use to get the algorithm to give up looking
for multiple solutions?

[Michael Metcalf]

Post by AN O'Nymous
Interesting, Michael. What technique (e.g. Tabu, simulated annealing,
partial enumerative, ...?) does your algorithm use to solve it, and
what decision rules do you use to get the algorithm to give up looking
for multiple solutions?

I apply various logic solving algorithms, for instance 'pairs', and resort
to brute force if the logic rules prove insufficient. Brute force stops as
soon as it finds a second solution (hardly counts as a decision rule - going
on is simply uninteresting). For a human solver, brute force is equivalent
to having to guess (Thread of Ariadne). The line between the two is fuzzy,
depending on how many algorithms you're willing to code and apply (X-wing,
swordfish, jellyfish etc.), just as a human solver may guess rather than
apply such techniques.

I'm planning to write an article for Fortran Forum on this.

Regards,

Mike Metcalf

[Brooks Moses]

Post by AN O'Nymous
http://en.wikipedia.org/wiki/Sudoku
I've been thinking about it a bit, and being a tad inexperienced, the
immediate one that came to mind was an exhaustive trial-and-error
algorithm. Quite inefficient, but essentially 100% consistent.
I will need to think about this one over the weekend. Does anyone know
if *every* Sudoku puzzle has one unique, correct solution or if there
are usually multiple solutions?

Amusingly, I just heard of Sudoku puzzles yesterday due to a contest
announced in the Practical-TeX online magazine for TeX and LaTeX. The
contest announcement there had a few links to sources for solution
algorithms and the like:
http://tug.org/pracjourn/2005-4/distract/

In particular, they recommend this site as a starting point:
http://www.sudokusolver.co.uk/

- Brooks

[R. Vowels]

Post by AN O'Nymous
So here's the challenge: can anyone write a Fortran program that can
consistently, and better yet, efficiently solve any Sudoku puzzle of
standard format? A bit of Googling around would show that we would not
be the first to try...

I wondered how long it would be before a challenge
was issued.
Several months ago I wrote a solver,
following the hand method.

[Rich Townsend]

Post by R. Vowels

Post by AN O'Nymous
So here's the challenge: can anyone write a Fortran program that can
consistently, and better yet, efficiently solve any Sudoku puzzle of
standard format? A bit of Googling around would show that we would not
be the first to try...

I wondered how long it would be before a challenge
was issued.
Several months ago I wrote a solver,
following the hand method.

But you being Vowells, and this being c.l.f, will we ever see a working program?

[AN O'Nymous]

Post by Rich Townsend
and this being c.l.f, will we ever see a working program?

Oh, ye of little faith :-)

In the spirit of open sourcing, I'll start the ball rolling with the
"validity checker" below, which checks if the row/column/region
requirements are met once you give it the element's co-ordinates to
check for.

It assumes that all relevant entries are known - either given or
guessed.

! This section assigns the regions for the entry
x_region = int(real(x)/3.)+1
y_region = int(real(y)/3.)+1

! This section checks the validity of the region
count = 0
x_offset1 = 3*x_region-1
x_offset2 = 3*x_region
y_offset1 = 3*y_region-1
y_offset2 = 3*y_region

do i = 1,9
count(i) = i
enddo

do i = x_offset1, x_offset2
do j = y_offset1, y_offset2
do k = 1, 9

if (count(k) == sudoku_array(i,j)) then
count(k) = 0
endif

enddo
enddo
enddo

test_integer = 0
do i = 1,9
test_integer = test_integer + count(i)
enddo

if (test_integer == 0) then
Print *,'Valid region'
endif
if (test_integer > 0) then
Print *,'Invalid region'
endif


! This section checks the validity of the rows/columns
do i = 1,9
count(i) = i
enddo

do i = 1, 9
do k = 1, 9
if (count(k) == sudoku_array(i,y)) then
count(k) = 0
endif
enddo
enddo

test_integer = 0
do i = 1,9
test_integer = test_integer + count(i)
enddo

if (test_integer == 0) then
Print *,'Rows OK'
endif
if (test_integer > 0) then
Print *,'Rows not OK'
endif



do i = 1,9
count(i) = i
enddo

do j = 1, 9
do k = 1, 9
if (count(k) == sudoku_array(x,j)) then
count(k) = 0
endif
enddo
enddo

test_integer = 0
do i = 1,9
test_integer = test_integer + count(i)
enddo

if (test_integer == 0) then
Print *,'Columns OK'
endif
if (test_integer > 0) then
Print *,'Columns not OK'
endif

[Richard Maine]

Post by AN O'Nymous

Post by Rich Townsend
and this being c.l.f, will we ever see a working program?

Oh, ye of little faith :-)

I think you missed the important part before the "and" in Rich's post.
:-) Or perhaps you intentionally choose to do so,which would be fine.

[Michael Metcalf]

Post by AN O'Nymous
! This section checks the validity of the rows/columns
do i = 1,9
count(i) = i
enddo
do i = 1, 9
do k = 1, 9
if (count(k) == sudoku_array(i,y)) then
count(k) = 0
endif
enddo
enddo

Might I suggest that once count(k) has been set 0 you can exit the 2 loops.
But the whole section is, I think, equivalent to (untested):

kount = ( (/ i, i = 1, 9 /) ) ! count is an intrinsic, so a name to be
avoided
do k = 1, 9
if(any(kount(k) == sudoku_array(:,y) ) ) kount(k) = 0 ! is y correct? do
you mean j?
end do

or even

where (kount == sudoku_array(:,y)) kount = 0

In my own code, I have found count, any and where invaluable.

Regards,

Mike Metcalf

[AN O'Nymous]

Post by Michael Metcalf
Might I suggest that once count(k) has been set 0 you can exit the 2 loops.

Do you mean that there is no point testing the legality of an element
if it fails one test? In general, unless an element fails, you'd have
to test region + row + column to be certain if it is correct.

Post by Michael Metcalf
kount = ( (/ i, i = 1, 9 /) ) ! count is an intrinsic, so a name to be
avoided
do k = 1, 9
if(any(kount(k) == sudoku_array(:,y) ) ) kount(k) = 0 ! is y correct? do
you mean j?
end do

Yes, "y" is correct. We were scrolling across column-y with that do
loop.

[Michael Metcalf]

Post by AN O'Nymous

Post by Michael Metcalf
Might I suggest that once count(k) has been set 0 you can exit the 2 loops.

Do you mean that there is no point testing the legality of an element
if it fails one test? In general, unless an element fails, you'd have
to test region + row + column to be certain if it is correct.

Yes. Once count(k) is set to 0 it cannot get changed to any other value
(only to 0 again), so there's no point in continuing the double loop.

Regards,

Mike Metcalf

[Thomas Koenig]

Post by AN O'Nymous
I've been thinking about it a bit, and being a tad inexperienced, the
immediate one that came to mind was an exhaustive trial-and-error
algorithm. Quite inefficient, but essentially 100% consistent.

As it happens, I encountered my first Sudoku on a train last Friday,
and as I happened to have my laptop with me, I wrote a program to
solve sudokus, and yes, in Fortran. Most of the time was spent
getting the code to handle the dependencies between the different
fields correct.

The program is only for the 9*9 types. As efficiency goes, it
took me about an hour to write, and execution time is neglible.
That's efficient according to my definition.

It uses straightforward backtracking (if there is such a thing),
and a bit less than 2000 invocations of the central subroutine
for the one puzzle that I tested it on.