- Forum
- General C++ Programming
- sudoku solver
sudoku solver
please suggest some algorithm to make a sudoku solver which workouts on some pre-filled values to make out the solution
Well, I don't think anyone will make this whole algorithm for you, but here's a general idea to help you start.
I'dd represent the sudoku solver with a 9x9 array of char and a few public methods to read and set the starting numbers. Any cell with a space is empty.
The first methods you need are those which will search for a number within a column, a row or a block and return true if the number is found. That's 3 different functions.
You could make a method which tries to place a number in a cell and returns true if this number "could" go there. If the cell is empty, this function would call the 3 search functions made previously. If the number was not found in the current row, column or block, then it could go in the current cell.
You can also make a method which calls the previous one 9 times. If there is only one number which can be placed in the current cell, then place it.
This method would need to be in a set of loops which tries it for all cells of the sudoku. This operation would also need to be repeated until the sudoku is solved, or until nothing has changed after a scan of the whole grid.
But then again, this algorithm doesn't to trial and error. Only the easiest of sudokus can be done that easily.
You can do trial-and-error solving by placing a number which "could" be in a cell even if you aren't certain that it belongs there. Then you call the solving algorithm recursively from there. If the algorithm returns false, it means no solution was found using the current guessed number, so you have to erase it and try another one.
I think this wikipedia page explains this brute-force method better than me:
http://en.wikipedia.org/wiki/Sudoku_solving_algorithms#Brute-force_algorithm
Edit: Mats was quicker... wait, did I really spend 20 minutes thinking about solving sudokus? Haha...
I'dd represent the sudoku solver with a 9x9 array of char and a few public methods to read and set the starting numbers. Any cell with a space is empty.
The first methods you need are those which will search for a number within a column, a row or a block and return true if the number is found. That's 3 different functions.
You could make a method which tries to place a number in a cell and returns true if this number "could" go there. If the cell is empty, this function would call the 3 search functions made previously. If the number was not found in the current row, column or block, then it could go in the current cell.
You can also make a method which calls the previous one 9 times. If there is only one number which can be placed in the current cell, then place it.
This method would need to be in a set of loops which tries it for all cells of the sudoku. This operation would also need to be repeated until the sudoku is solved, or until nothing has changed after a scan of the whole grid.
But then again, this algorithm doesn't to trial and error. Only the easiest of sudokus can be done that easily.
You can do trial-and-error solving by placing a number which "could" be in a cell even if you aren't certain that it belongs there. Then you call the solving algorithm recursively from there. If the algorithm returns false, it means no solution was found using the current guessed number, so you have to erase it and try another one.
I think this wikipedia page explains this brute-force method better than me:
http://en.wikipedia.org/wiki/Sudoku_solving_algorithms#Brute-force_algorithm
Edit: Mats was quicker... wait, did I really spend 20 minutes thinking about solving sudokus? Haha...
Last edited on
Topic archived. No new replies allowed.