Hi Don, How is your method better than backtracking?
i hope you are implementing a sudoku solver.. Let me know. Regds. On Tue, Oct 4, 2011 at 10:42 PM, Don <dondod...@gmail.com> wrote: > When you say "Simulate" Sudoku, do you mean solve a given Sudoku > problem? > > Here is an overview of how I did that: > > I used an array of 81 integers to represent the board. > Then I built a 27x9 table of all the groups: 9 rows, 9 columns, and 9 > squares. > Then I built a 81x3 map which relates each location on the board to > the 3 groups it belongs to. > I maintain an array of 27 integers called "avail" whose bits indicate > which values are still needed in that group. > > Read in the given values and update avail accordingly. > > Then repeatedly do the following until the problem is solved > For each empty cell > Compute the bitwise AND of the avail values for the 3 groups it > belongs to. > If the AND is zero, no value can go there. Return failure. > If exactly one value can go there, put it there and update the > avail values for the 3 groups > If the loop above did not fill in any cells, then do the following > Loop at each of the 27 groups > For each value missing in that group, count the locations > where it could go > If it could go in exactly one location, put it there > If it cannot go in any location, return failure. > If the neither method above filled in any cells, then do the > following: > Pick the empty cell with the fewest possible values > Try the possible values in that cell until you find one which > allows the puzzle to be completed > > If the puzzle is solvable, this will solve it in a fraction of a > second. > > Don > > On Oct 4, 9:21 am, himanshu kansal <himanshukansal...@gmail.com> > wrote: > > can anybody give me the steps you need to check while writing a > > program to simulate sudoku.... > > > > i don't want the exact code....just algorithm would me more than > > sufficient..... > > > > suggest also the suitable languages for implementing that......VB or > > java or any other???? > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Nice Day Abhishek Sharma Bachelor of Technology IIT Kanpur (2009) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
