Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.
Trending News
I'm creating a sudoku solver in Java, and I need help! Can Anyone here?
I'm going about it in this way:
So far what I've done:
The program creates a list (1-9), then check my array (int[][]); for every number in the column, it checks through the numbers, and if one is there that's in my list of 1-9, it changes that number to 0. Does the same for columns. If there are 8 0's, the remaining number (int > 0) will be put into that array location.
What I have yet to do:
numbers in each THIRD need to be included in that as well. Is there an algorithm or maybe some new way of determining what a third of the array is? or do I have to resort to if/then/switch statements? or maybe I'm going about this completely wrong?
I'm an amateur programmer, this is really the first full fledged solo program I'm attempting, so you're comments are greatly appreciated! thanks.
1 Answer
- Mark FLv 61 decade agoFavorite Answer
I've started a little sudoku solver as a mental exercise, although I haven't gotten around to finishing it. I created a regular 9x9 2D array of cells, and each cell contains the current number that's set there (if any) and a bitmask showing all the numbers that can be at this location (i.e. 9 bits per cell, one for each possible number). I then create multiple arrays of indices ("sets") into this grid, i.e. one set of 9 indices for each row, one for each column, and one for each 3x3 sub-grid.
The first rule is that if a cell is set to a number then no other number in that cells row, column or sub-grid can be set to that number. So when I set a cell to a given number initially I find all the sets that contain that cell, then I loop through all the other cells in those sets and remove that number from their mask.
Rule two is that if the mask for any cell at any time contains only 1 bit that's set (i.e. only one number can go here) then I set the cell to that number and apply rule # 1 to all cells that share a set with this cell.
Rule 3 is that if a bit for a given number is set in only 1 cell in any given set then that cell must contain that number. This is analogous to finding a column where you've excluded the number 3 (say) from all cell except one...that cell must be a 3.
After this, the rules get a bit more complex. Rule 2 can be extended to a more generic form involving X cells i.e. if there are X cells in any given set and they only have X numbers that can reside in them then no other cells in that set can have those numbers so you can wipe them from the other cell's bitmasks.
There are plenty of web pages dedicated to sudoku containing more advanced algorithms that are also easy to apply to bitmasks, you just repeatedly apply those rules and these until you arrive at a solution. If at any point you hit a dead end then you'll have to resort to a brute force approach and do a depth-first search until you reach the solution .
