Win a copy of Re-engineering Legacy Software this week in the Refactoring forum
or Docker in Action in the Cloud/Virtualization forum!

# Sudoku puzzle

Arjunkumar Shastry
Ranch Hand
Posts: 986
This Japanse puzzle is becoming popular day by day everywhere.Solving this is not very difficult but surely challenging.First step is very important.

www.sudoku.com
For those who are unaware of Sudoku,its simple.
" Fill in the grid so that every row,
every column, and every 3x3 box
contains the digits 1 through 9. with no digit repeated "
1)Is it possible to write a program which can solve Sudoku puzzle?

[ June 26, 2005: Message edited by: Arjunkumar Shastry ]

Tim West
Ranch Hand
Posts: 539
While I don't want to dive into the details, you could write a backtracking solution along the lines of "8 queens", I reckon.

....but I have a thesis to work on, so I'll leave the fun up to someone else

-Tim

Srinivasa Raghavan
Ranch Hand
Posts: 1228
It's very interesting. I'm seeing this puzzle daily in, NewYork Post & www.thehindu.com , news papers.

Is it possible to write a program which can solve Sudoku puzzle
In our college days we have writtern program for this,
Magic Square program was so popular in those days..
[ June 26, 2005: Message edited by: Srinivasa Raghavan ]

David O'Meara
Rancher
Posts: 13459
Originally posted by Arjunkumar Shastry:
1)Is it possible to write a program which can solve Sudoku puzzle?

Yes, although this may be a question for the Programming Diversions forum
Theoretically (if they have provided a correct problem) there is a single solution so a brute-force approach will work. This depends on the efficiency of creating all possible solutions and filtering to find the only one left.

There is no reason you can't use the usual solution method to provide an intelligent algorithm, it all depends on what you know

The page here suggests that it is also the unique solution to a linear equation, which is probably the most efficient approach. ( the 'parent page' is here )
[ June 26, 2005: Message edited by: David O'Meara ]

John Smith
Ranch Hand
Posts: 2937
The straightforward way would probably take a very long time to calculate, so I implemented it using backtracing, as Tim suggested. It ttok only a quarter of a second for the answer to come out:

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 1 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 9 7 2 1 4 3 6 5
5 3 1 6 4 2 9 7 8
6 4 2 9 7 8 5 3 1
9 7 8 5 3 1 6 4 2

Unfortunately, MD doesn't accept code, but if you post it in Programming Diversions, I'll be happy to post it in there.