aspose file tools*
The moose likes Meaningless Drivel and the fly likes Sudoku puzzle Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Meaningless Drivel
Bookmark "Sudoku puzzle" Watch "Sudoku puzzle" New topic
Author

Sudoku puzzle

Arjunkumar Shastry
Ranch Hand

Joined: Feb 28, 2005
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 ]

Namma Suvarna Karnataka
Tim West
Ranch Hand

Joined: Mar 15, 2004
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

Joined: Sep 28, 2004
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 ]

Thanks & regards, Srini
MCP, SCJP-1.4, NCFM (Financial Markets), Oracle 9i - SQL ( 1Z0-007 ), ITIL Certified
David O'Meara
Rancher

Joined: Mar 06, 2001
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

Joined: Oct 08, 2001
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.
 
permaculture playing cards
 
subject: Sudoku puzzle