## Re: Solving puzzles mechanically

Programs which generate, solve, and analyze Sudoku puzzles

### Re: Fuss about solving Sudoku

Dominic wrote:...You may come up with a sufficient number to solve some problems, but this is intrinsically arbitrary since you will never know when you have the complete set of rules to solve every problem. i.e. there is no mathematical rigour to this process whatsoever...

Hi:

I don't believe your statement is correct.

Today was the first I had ever heard of this Sudoku puzzle. I was able to work through an example puzzle and arrive at the solution. It is challenging, but fairly straight-forward to solve.

That solution process showed me that I can solve Soduku using a technique that is almost identical to how I solve logic problems. It is inherently a mathematical solution process!

My point is this: it is very easy to create a program that will methodically solve a given Soduku and arrive at the one-and-only answer. There is absolutely no need for any sort of inelegant, brute-force trial-and-error solution method. And THAT means that you can be certain that your solver has arrived at the correct solution.

I will work up a Visual Basic .NET program that can solve these puzzles, but it will take a few days to complete. I'll post back then.

...in the mean time, accept it as your challenge to take another look at these puzzles and try to discover my solution methodology.

Good Luck,
KEITH
Guest

Posts: 312
Joined: 25 November 2005

### Re: Fuss about solving Sudoku

Keith wrote:it is very easy to create a program that will methodically solve a given Soduku and arrive at the one-and-only answer. There is absolutely no need for any sort of inelegant, brute-force trial-and-error solution method. And THAT means that you can be certain that your solver has arrived at the correct solution.

I don't believe your statement is correct.

Not every puzzle has a unique solution - it depends on how well the clues are selected. You may arrive at an answer, but not necessarily the answer.

Many puzzles, perhaps the majority (and certainly all of Pappocom's) can be solved without resorting to T&E, but there are still some that are not solveable without it. There is sometimes a need for that "inelegant, brute-force trial-and-error solution method."

Simes
http://www.simes.clara.co.uk/programs/sudoku.htm
simes

Posts: 324
Joined: 11 March 2005
Location: UK

I do agree with Simes. Brute-force (comp. term for "guessing") is necessary in problems (like sudoku) where deduction is not enough.

It is inherently a mathematical solution process!
You don't need to put ! here, we all know that for a long time
Guest

### the Mathematics describing Sudoku

From Wikipedia:

The problem of solving Sudoku puzzles is known to be NP-complete

Mathematicians would say that solving Sudoku puzzles can be expressed as a graph coloring problem. The aim of the puzzle in its standard form is to construct a proper 9-coloring of a particular graph, given a partial 9-coloring. The graph in question has 81 vertices, one vertex for each square of the grid. The vertices can be labelled with the ordered pairs (x,\, y), where x and y are integers between 1 and 9. In this case, the vertices labelled by (x,\, y) and (x',\, y') are joined by an edge if and only if:

* x = x'\, or,
* y = y'\, or,
* x \equiv x' \pmod{3} \, and y \equiv y' \pmod{3} \,.

The puzzle is then completed by assigning an integer between 1 and 9 to each vertex, in such a way that vertices that are joined by an edge do not have the same integer assigned to them.
Guest

It's the first time I heard about this Sudoku game when I reading TorontoStar during a trip several days ago. I came up the solution before I back home. Then I wrote a VB program to do what I did automatically, less than one second. If somebody what to try, give me a email: weberluo2004@yahoo.ca, I don't have FTP site.

Cheers
Weber
Guest

Previous