Counting Sudoku Solutions in Java
Articles —> Counting Sudoku Solutions in Java
How many possible sudoku solutions are there? Sometimes thoughts such as this end up squeezing the rest of my free time out of me. The easy answer would be to just look it up, but why not have some fun and try to calculate it? Of course a little math and logic beforehand would have suggested I turn tail and run from the problem, live and learn.
I've written a Sudoku game in the past, so I decided to expand upon that code to write an algorithm that counts how many possible solutions there are. The code below demonstrates a solution. Basically, for each square it arrives at, the algorithm iterates through each of the 1-9 entries. For each value that is a valid entry based upon all the previous values, the algorithm proceeds to the next sudoku grid square to perform the same calculation. The algorithm will continue like so until a solved puzzle is completed. The key here is, given the recursive algorithm (namely the fill method), it can then backtrack through the sudoku grid to the last position that still needs an increment, increments the value and continue where it left off. Long story short, this will track and backtrack through the puzzle finding and counting possible solutions. For efficiency I used pre-made look-up tables to enforce the basic Sudoku rules.
The java source code:
/* * A class used to count solutions to sudoku puzzles. Copyright 2010 Greg Cope * * @author Greg Cope * @copyright Greg Cope */ public class SudokuCounter { /**Lookup table for horizontal values of the grid*/ public static final int horizontal[][] = {{0,1,2,3,4,5,6,7,8}, {9,10,11,12,13,14,15,16,17}, {18,19,20,21,22,23,24,25,26}, {27,28,29,30,31,32,33,34,35}, {36,37,38,39,40,41,42,43,44}, {45,46,47,48,49,50,51,52,53}, {54,55,56,57,58,59,60,61,62}, {63,64,65,66,67,68,69,70,71}, {72,73,74,75,76,77,78,79,80} }; /**Lookup table for vertical values of the grid*/ public static final int vertical[][] = {{0,9,18,27,36,45, 54, 63, 72}, {1,10,19,28,37,46,55,64,73}, {2,11,20,29,38,47,56,65,74}, {3,12,21,30,39,48,57,66,75}, {4,13,22,31,40,49,58,67,76}, {5,14,23,32,41,50,59,68,77}, {6,15,24,33,42,51,60,69,78}, {7,16,25,34,43,52,61,70,79}, {8,17,26,35,44,53,62,71,80} }; /**Lookup table for 3x3 grid values*/ public static final int box[][] = { {0,1,2,9,10,11,18,19,20}, {3,4,5,12,13,14,21,22,23}, {6,7,8,15,16,17,24,25,26}, {27,28,29,36,37,38,45,46,47}, {30,31,32,39,40,41,48,49,50}, {33,34,35,42,43,44,51,52,53}, {54,55,56,63,64,65,72,73,74}, {57,58,59,66,67,68,75,76,77}, {60,61,62,69,70,71,78,79,80}}; /**Lookup values for a particular cell. Corresponds to horizontal, vertical, grid, h-pair (other horizontal pairs in grid), v-pair (other vertical pairs in grid)*/ public static final int cell[][] = { {0,0,0,1,2,1,2}, {0,1,0,0,2,1,2}, {0,2,0,0,1,1,2}, {0,3,1,4,5,1,2}, {0,4,1,3,5,1,2}, {0,5,1,3,4,1,2}, {0,6,2,7,8,1,2}, {0,7,2,6,8,1,2}, {0,8,2,6,7,1,2}, {1,0,0,1,2,0,2}, {1,1,0,0,2,0,2}, {1,2,0,0,1,0,2}, {1,3,1,4,5,0,2}, {1,4,1,3,5,0,2}, {1,5,1,3,4,0,2}, {1,6,2,7,8,0,2}, {1,7,2,6,8,0,2}, {1,8,2,6,7,0,2}, {2,0,0,1,2,0,1}, {2,1,0,0,2,0,1}, {2,2,0,0,1,0,1}, {2,3,1,4,5,0,1}, {2,4,1,3,5,0,1}, {2,5,1,3,4,0,1}, {2,6,2,7,8,0,1}, {2,7,2,6,8,0,1}, {2,8,2,6,7,0,1}, {3,0,3,1,2,4,5}, {3,1,3,0,2,4,5}, {3,2,3,0,1,4,5}, {3,3,4,4,5,4,5}, {3,4,4,3,5,4,5}, {3,5,4,3,4,4,5}, {3,6,5,7,8,4,5}, {3,7,5,6,8,4,5}, {3,8,5,6,7,4,5}, {4,0,3,1,2,3,5}, {4,1,3,0,2,3,5}, {4,2,3,0,1,3,5}, {4,3,4,4,5,3,5}, {4,4,4,3,5,3,5}, {4,5,4,3,4,3,5}, {4,6,5,7,8,3,5}, {4,7,5,6,8,3,5}, {4,8,5,6,7,3,5}, {5,0,3,1,2,3,4}, {5,1,3,0,2,3,4}, {5,2,3,0,1,3,4}, {5,3,4,4,5,3,4}, {5,4,4,3,5,3,4}, {5,5,4,3,4,3,4}, {5,6,5,7,8,3,4}, {5,7,5,6,8,3,4}, {5,8,5,6,7,3,4}, {6,0,6,1,2,7,8}, {6,1,6,0,2,7,8}, {6,2,6,0,1,7,8}, {6,3,7,4,5,7,8}, {6,4,7,3,5,7,8}, {6,5,7,3,4,7,8}, {6,6,8,7,8,7,8}, {6,7,8,6,8,7,8}, {6,8,8,6,7,7,8}, {7,0,6,1,2,6,8}, {7,1,6,0,2,6,8}, {7,2,6,0,1,6,8}, {7,3,7,4,5,6,8}, {7,4,7,3,5,6,8}, {7,5,7,3,4,6,8}, {7,6,8,7,8,6,8}, {7,7,8,6,8,6,8}, {7,8,8,6,7,6,8}, {8,0,6,1,2,6,7}, {8,1,6,0,2,6,7}, {8,2,6,0,1,6,7}, {8,3,7,4,5,6,7}, {8,4,7,3,5,6,7}, {8,5,7,3,4,6,7}, {8,6,8,7,8,6,7}, {8,7,8,6,8,6,7}, {8,8,8,6,7,6,7}}; private static int size = 81; public static void main(String[] args){ int[] sudoku = new int[size]; for ( int i = 0; i < size; i++ ){ sudoku[i] = 0; } EditableLong count = new EditableLong(0); fill(sudoku, 0, count); System.out.println(count.getValue()); } /** *Recursively fill a sudoku grid and counts possible solutions */ private static void fill(int[] sudoku, int index, EditableLong count){ for ( int i = 0; i < 9; i++ ){ sudoku[index] = i+1; if ( index == size-1 ){ if ( validateCellEntry(index, sudoku) ){ count.increment(); } }else{ if ( validateCellEntry(index, sudoku) ){ fill(sudoku, index+1, count); } } } sudoku[index] = 0; } /** * Checks if the entry at the position in the sudoku array is valid based upon * the rest of the array and sudoku rules. * @param pos * @param sudoku * @return */ private static boolean validateCellEntry( int pos, int[] sudoku){ int val = sudoku[pos]; for ( int i = 0; i < 9; i++ ){ if ( horizontal[cell[pos][0]][i] != pos && sudoku[horizontal[cell[pos][0]][i]] == val ){ return false; } if ( vertical[cell[pos][1]][i] != pos && sudoku[vertical[cell[pos][1]][i]] == val ){ return false; } if ( box[cell[pos][2]][i] != pos && sudoku[box[cell[pos][2]][i]] == val ){ return false; } } return true; } /** * Inner wrapper class for a long * */ private static class EditableLong{ private long value; public EditableLong(long value){ this.value = value; } public long getValue(){ return value; } public void increment(){ value++; if ( value == Long.MAX_VALUE ){ throw new IllegalStateException("Long reached its max value."); } } } }
Just before running this for a reasonable period of time, I thought I'd cheat and do a little investigation. This is when I realized how tough the above could be when I read the actual number of possible Sudoku puzzles:
6,670,903,752,021,072,936,960 solutions1
So maybe not something that I can readily calculate...a little modification of my code above to print out its efficiency, followed by some math conversions, I determined it would take a very long time to complete: approximately 2.6e9 years? Maybe it was late at night and my math skills were weak, but perhaps this not a listing of code that's worth trying to run to completion.
0 results
Comments
- Mats N - January, 19, 2018
How it is ment use this program?
I tried to execute it but nothing happens.
Hope for answer :-)