pearlygate
November 9th, 2009, 08:58 AM
Has anyone ever made a sudoku solver before? I made one by constructing a search tree and search using DFS using recursion. something like
//call solve(initialTable)
boolean solve( List<Integer>[][] table) {
//if table is solved return true
//else let solutions = all possible solutions for unfinished cells in the state ordered by cells with the least number of possible solutions
//for each possible solutions set the cell = some number
//if this solve some other cells, do them and update the table.
// call solve(modifiedTable)
// if solve(modifiedTable) return true, then return true
// else undo the changes made to the table
//if for loop doesn't find solution return false
}
Of course there are other optimizations, etc but I am curious if there is a way to do this iteratively? I'm kinda stuck thinking about it.
Thanks
//call solve(initialTable)
boolean solve( List<Integer>[][] table) {
//if table is solved return true
//else let solutions = all possible solutions for unfinished cells in the state ordered by cells with the least number of possible solutions
//for each possible solutions set the cell = some number
//if this solve some other cells, do them and update the table.
// call solve(modifiedTable)
// if solve(modifiedTable) return true, then return true
// else undo the changes made to the table
//if for loop doesn't find solution return false
}
Of course there are other optimizations, etc but I am curious if there is a way to do this iteratively? I'm kinda stuck thinking about it.
Thanks