Re: Sudoku Construction ?


"mathedman" <mathedman@xxxxxxxxxxxxxxx> wrote in message
news:432c311f.87529944@xxxxxxxxxxxxxxxxxxxxxxxxxxx
|
| I read somewhere recently that a puzzle enthusiast has written
| a computer program to produce Sudoku puzzles.
| What type of algorithm/method is used to construct these
| puzzles in order to assure a unique solution?

Exhaustion. Computers are fast, so time doesn't matter.

For a magic square, integers 1 to 9, sum 15 in rows and columms:

Step 1:
Place an integer random number 'a' within the required range at a random
location.

+---+---+---+
| x | x | x |
+---+---+---+
| a | x | x |
+---+---+---+
| x | x | x |
+---+---+---+

Step 2:
Place a second random number b not equal a at some other location.

+---+---+---+
| x | x | x |
+---+---+---+
| a | x | x |
+---+---+---+
| b | x | x |
+---+---+---+

Step 3:
Here c is determined.

+---+---+---+
| c | x | x |
+---+---+---+
| a | x | x |
+---+---+---+
| b | x | x |
+---+---+---+

If c<=0, back up and change b. Goto Step 2.

Step 4:
Place another random number d not equal a,b,c somewhere.
+---+---+---+
| c | x | x |
+---+---+---+
| a | x | d |
+---+---+---+
| b | x | x |
+---+---+---+
Step 5:
Here e is determined.
+---+---+---+
| c | x | x |
+---+---+---+
| a | e | d |
+---+---+---+
| b | x | x |
+---+---+---+

If e = a, b,c,d, or e<=0, goto Step 4.
And so on.

Eventually the computer will place 5 at the centre and solve the square.
+---+---+---+
| 6 | 7 | 2 |
+---+---+---+
| 1 | 5 | 9 |
+---+---+---+
| 8 | 3 | 4 |
+---+---+---+
Other methods are of course possible.

Androcles







.

Relevant Pages

  • Re: Sudoku Construction ?
    ... >| a computer program to produce Sudoku puzzles. ... >| What type of algorithm/method is used to construct these ...
    (sci.math)
  • Sudoku Construction ?
    ... a computer program to produce Sudoku puzzles. ... What type of algorithm/method is used to construct these ...
    (sci.math)
  • Re: Sodoku
    ... figure out how to do sudoku puzzles. ... scribbled notes on what might be where that I can't quite read and ... don't quite trust, I start guessing. ...
    (alt.usage.english)
  • Re: Sodoku
    ... figure out how to do sudoku puzzles. ... remaining possibilities for a cell and erasing them or crossing them ... and don't quite trust, I start guessing. ...
    (alt.usage.english)
  • Re: Sodoku
    ... figure out how to do sudoku puzzles. ... remaining possibilities for a cell and erasing them or crossing them ... If I get sufficiently frustrated with it - especially with hand-scribbled notes on what might be where that I can't quite read and don't quite trust, I start guessing. ...
    (alt.usage.english)