I'd like to write a computer program to solve sudoku puzzles for me ;-)
Because I'm too lazy to solve them myself! LOL
Seriously, though, how would you approach writing a program that finds the solution for a 9X9 sudoku puzzle?
Data Structure to use?
Algorithm?
I suppose I could use an array for the data structure. Any better ideas?
As far as the algorithm is concerned, I believe I would need some backtracking code, but that's my only idea so far.
Thinking about implementing this in Python, since I've heard so many good things about it, and would like to learn.
All input is appreciated ;-)
Think about how you solve them manually, then try to convert it to code. Sudoku is a very logical puzzle and can be solved both through trying every combination and logic.
If you search sudoku solver here on DIC there are many hints and solutions for you.
http://www.dreamincode.net/?cx=000872085005376217422%3Azamd_7elal4&p=google&cof=FORID%3A11&q=sudoku+solver&sa=Go#1357
Read up on constraint propagation. Many of the "easy" Sudoku puzzle can be solved with straight propagation but harder ones will require back tracking.
i would probably do it in Prolog...it can be done in a few lines.
Well I had to do this in Assembly for school ( and yes i would rather put my head through a pitchfork before attempting that again). The experience has taught me a few ways to go about this.
1st Way) http://en.wikipedia.org/wiki/Depth-first_search (Depth First Search) is the algorithm that you would implement. this takes picks a state and chooses a value. based of that it picks the next neighbor and follows that to the end of the puzzle. If it finds a dead end, it will back up and try a different path. This algorithm is a fairly standard searching algorithm paired with BFS (searches differently). Assembly doesn't make it easy to implement this algorithm, but its a snap in higher level languages
2nd way) Taking the concept of the first you can start at pos(0,0) and give it a value of one. now move across row and increment its value by 1 at each step At this step check the column Was the input valid? if not keep incrementing until you try them all move back (explain below what that entails). do this to the end of the row. check the row for legitimacy, and if it isnt move back. What i mean by moving back, is to clear the pos you were at (back to 1) and then increment by 1 the pos you move to. This pattern will eventually fill up the table.
Special Conditions:
fixed num: you will have to create a hopping method to jump over that going forward and back
move back at pos(0,0) this means that there were no solutions, and will have to report such when you encounter said event
move forward at pos(maxRow, maxCol): this means puzzle is solved.
Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)