+/EE422C
software design
git clone https://git.julia.blue/+/EE422C
7e47727
master
1import java .io .File ; 2import java .io .FileNotFoundException ; 3import java .util .Arrays ; 4import java .util .Scanner ; 5 6/** 7* This is a Sudoku Solver that solves a partial Sudoku Board using 8* recursion. The Sudoku solver fills a N×N (N=9 by default) grid 9* with digits so that each column, each row, and each of the Size 10* ×Size (N=Size × Size while Size =3 by default) subgrids contains 11* all of the digits from 1 to 9. 12* <p> 13* You need to implement the solve(SudokuBoard b, int current) method 14* using recursion. Everything else is given to you. 15* </p> 16* <p> 17* Don't change other given methods/fields. You can add some private 18* helper methods but you may not add new public methods or fields. 19* </p> 20*/ 21public class Sudoku { 22 23public static int noSolves =0 ; 24public static int size ; 25 26@ SuppressWarnings ("resource" ) 27public static void main (String []args ) 28throws FileNotFoundException { 29// Initialize board 30Scanner sc =new Scanner (new File ("sudoku.in" )); 31 32boolean more =true ; 33while (more ) { 34int n =sc .nextInt (); 35size =n *n ; 36int [][]initial =new int [size ][size ]; 37 38for (int cell =0 ;cell <size *size ;cell ++) { 39initial [cell /size ][cell %size ] =sc .nextInt (); 40 } 41System .out .println (initial .length ); 42solve (initial ); 43more =sc .hasNextInt (); 44if (more ) { 45System .out .println ();// Print blank line between test cases 46 } 47 } 48 } 49 50public static void solve (int [][]initial ) { 51if (size ==1 ) { 52System .out .println (1 ); 53return ; 54 } 55SudokuBoardSoln brd =new SudokuBoardSoln (size ,initial ); 56if (solve (brd ,brd .nextEmpty (-1 ))) { 57brd .else { 59System .out .println ("NO SOLUTION" ); 60 } 61 } 62 63public static boolean solve (SudokuBoardSoln b ,int current ) { 64noSolves ++;// For debug 65// current increases from 0 to size^2 - 1 -- first along a 66// row, then downwards. 67 68// IF the current placement is at square size^2, we are done. 69// ELSE 70// LOOP try out all 'size' numbers in the current square. 71// IF any number is safe to place there 72// Place it. 73// Call solve with the next square without an initial value. 74// IF above returns TRUE 75// RETURN TRUE. 76// ELSE 77// Remove the placement, (and try the next possible digit) 78// END LOOP 79// RETURN false (if we fall out of the LOOP without returning true, we have exhausted 1 - size) 80if (current ==size *size ) { 81return true ; 82 } 83for (int i =1 ;i <size +1 ; ++i ) { 84// System.out.println("Checking: " + i + " at " + current%size + " " + current/size); 85if (b .isSafe (i ,current )){ 86b .set (i ,current ); 87if (solve (b ,b .nextEmpty (current ))) { 88return true ; 89 } 90b .remove (i ,current ); 91 } 92 } 93return false ; 94 } 95} 96 97class SudokuBoardSoln { 98 99int [][]board ; 100boolean [][]initial ; 101int size ; 102int N ; 103 104public SudokuBoardSoln (int size ) { 105this .size =size ; 106N = (int ) (Math .sqrt (size ) +1e-3 ); 107board =new int [size ][size ]; 108 } 109 110public SudokuBoardSoln (int size ,int [][]starting ) { 111this (size ); 112initial =new boolean [size ][size ];// Is a square is 113// initialized? Iff not, 114// program may change its 115// value. 116for (int r =0 ;r <size ;r ++) { 117for (int c =0 ;c <size ;c ++) { 118if (starting [r ][c ] !=0 ) { 119initial [r ][c ] =true ; 120 } 121 } 122 } 123 124for (int r =0 ;r <size ;r ++) { 125board [r ] =Arrays .copyOf (starting [r ],size ); 126 } 127 } 128 129public void set (int a ,int n ) { 130board [n /size ][n %size ] =a ; 131 } 132 133public void remove (int a ,int n ) { 134set (0 ,n ); 135 } 136 137/* 138* Given a square, find the next one that was not initialized. 139*/ 140public int nextEmpty (int n ) { 141n ++; 142if (n ==size *size ) { 143return n ; 144 } 145int row =n /size ; 146int col =n %size ; 147while (initial [row ][col ]) { 148n ++; 149if (n ==size *size ) { 150return n ; 151 } 152row =n /size ; 153col =n %size ; 154 } 155return n ; 156 } 157 158/* 159* Whether safe to place number 'a' in space 'n'. 160*/ 161public boolean isSafe (int a ,int n ) { 162int row =n /size ; 163int col =n %size ; 164// If putting 'a' at location 'n' causes duplicate 165// number at its row, return false 166for (int i =0 ;i <size ; ++i ) { 167if (board [row ][i ] ==a ) { 168return false ; 169 } 170 } 171 172// If putting 'a' at location 'n' causes duplicate 173// number at its column, return false 174for (int i =0 ;i <size ; ++i ) { 175if (board [i ][col ] ==a ) { 176return false ; 177 } 178 } 179 180// If putting 'a' at location 'n' causes duplicate 181// number at its inner 3*3 (any N by N) square, return false 182int r =row /N ; 183int c =col /N ; 184for (int i =0 ;i <N ; ++i ) { 185for (int j =0 ;j <N ; ++j ) { 186if (board [r *N +i ][c *N +j ] ==a ) { 187return false ; 188 } 189 } 190 } 191 192// Hint: If there is a duplicate number, it means that one 193// number is missing (e.g. If we have two 1s in range of 194// [1..9], it means one of the other numbers is missing as we 195// can have at most 9 empty cells). 196return true ; 197 } 198 199public void for (int r =0 ;r <size ;r ++) { 201String blank ="" ; 202for (int c =0 ;c <size ;c ++) { 203if (board [r ][c ] ==0 ) { 204System .out .blank +"*" ); 205 }else { 206System .out .blank +board [r ][c ]); 207 } 208blank =" " ; 209 } 210System .out .println (); 211 } 212 } 213}