001package algs13.xbacktrack.xsudoku; 002 003import algs13.xbacktrack.xframework.MyBacktrackDriver; 004import algs13.xbacktrack.xframework.XBacktrackProblem; 005import algs13.xbacktrack.xframework.XBacktrackResult; 006import stdlib.StdOut; 007import stdlib.Stopwatch; 008 009import java.util.HashMap; 010import java.util.HashSet; 011import java.util.Set; 012 013/** 014 * A Sudoker solver, implemented as a BacktrackProblem where each 015 * choice is represented by a MutableCell (a cell we can assign a 016 * digit as part of a possible solution to Sudoku). 017 * 018 * This project represents a more substantial Java program than 019 * what we have been working with so far in the course. Search in this 020 * file and in algs13.xbacktrack.xframework.MyBacktrackDriver 021 * (MyBacktrackDriver.java)for some TODOs that will direct you to what you 022 * need to do for this assignment. 023 */ 024public final class MySudoku implements XBacktrackProblem<XMutableCell> { 025 026 public static final int SUBGRID_DIMENSION = 3; 027 public static final int GRID_SIZE = SUBGRID_DIMENSION * SUBGRID_DIMENSION; 028 private final XSudokuCell[][] grid; 029 030 // This is a mapping of subgrid id to the set of all cells in the subgrid. 031 // When the solver tries assigning a digit to a cell, that digit must 032 // not exist in another cell in the subgrid. This provides a quick way 033 // to find all the cells in a given subgrid so this property can be checked. 034 private final HashMap<Integer, Set<XSudokuCell>> subgrids; 035 036 final XMutableCell firstCell; 037 final XMutableCell lastCell; 038 039 private MyBacktrackDriver<XMutableCell> driver; 040 041 /** 042 * The constructor takes GRID_SIZE array of strings, each of which must be GRID_SIZE in 043 * length. Each character must be a digit. The index of the string corresponds to the row in the 044 * grid and the index of the digit in the string corresponds to the column in the grid. 045 * 046 * If a digit is 0, that signifies that the cell in the grid is mutable and the digit in that 047 * cell will be assigned by the solver. 048 */ 049 MySudoku(final String[] input) { 050 if(input.length != GRID_SIZE) { 051 throw new IllegalArgumentException(String.format("Input must have %d rows, found %d rows", GRID_SIZE, input.length)); 052 } 053 054 grid = new XSudokuCell[GRID_SIZE][]; 055 subgrids = new HashMap<>(); 056 for(int i = 0; i < GRID_SIZE; i++) { 057 subgrids.put(i, new HashSet<>()); 058 } 059 060 XMutableCell next = null; 061 XMutableCell last = null; 062 for(int x = GRID_SIZE - 1; x >= 0; x--) { 063 if(input[x].length() != GRID_SIZE) { 064 throw new IllegalArgumentException( 065 String.format("Input must have %d columns, found %d columns", GRID_SIZE, input[x].length()) 066 ); 067 } 068 grid[x] = new XSudokuCell[GRID_SIZE]; 069 for(int y = GRID_SIZE - 1; y >= 0; y--) { 070 char c = input[x].charAt(y); 071 final int digit = c - 48; 072 if(digit < 0 || digit > GRID_SIZE) { 073 throw new IllegalArgumentException(String.format("Invalid digit %d at location (%d, %d)", digit, x, y)); 074 } 075 if(digit == 0) { 076 XMutableCell cell = new XMutableCell(x, y, next); 077 grid[x][y] = cell; 078 next = cell; 079 if(last == null) last = next; 080 } 081 else { 082 grid[x][y] = new XImmutableCell(x, y, digit); 083 } 084 Set<XSudokuCell> subgrid = subgrids.get(grid[x][y].subgridId); 085 subgrid.add(grid[x][y]); 086 } 087 } 088 // Start out at a dummy cell - the first choice is what to do with the first 089 // cell in the grid, but if we backtrack from that choice, the framework 090 // we need this to be in the stack to prevent stack underflow. 091 firstCell = new XMutableCell(-1, -1, next); 092 if(last == null) { 093 throw new IllegalStateException("No last cell!"); 094 } 095 this.lastCell = last; 096 } 097 098 @Override 099 public void initialize(final MyBacktrackDriver<XMutableCell> driver) { 100 this.driver = driver; 101 driver.track(firstCell); // ... which happens to be the dummy cell! 102 } 103 104 private XMutableCell findNextMove(final XMutableCell current) { 105 if(current != null) { 106 int nextDigit = current.nextDigit(); 107 // When nextDigit wraps around to 0, we have tried all digits that 108 // are valid for the current cell. 109 while(nextDigit != 0) { 110 if(isValid(current)) { 111 return current; 112 } 113 nextDigit = current.nextDigit(); 114 } 115 } 116 // There is no next move we can make in the current cell. 117 return null; 118 } 119 120 // Verify the puzzle solution is correct. 121 private boolean verify() { 122 for(int x = 0; x < GRID_SIZE; x++) 123 for(int y = 0; y < GRID_SIZE; y++) 124 if(!isValid(grid[x][y])) return false; 125 return true; 126 } 127 128 // Method to determine whether the cell, with the digit updated 129 // prior to this call, is valid given the current state of the puzzle. 130 private boolean isValid(final XSudokuCell cell) { 131 final int subgrid = cell.subgridId; 132 final int digit = cell.getDigit(); 133 final int row = cell.x; 134 final int col = cell.y; 135 // Count how many times the digit for this cell occurs in its 136 // row, column, and subgrid. If the row, column, or subgrid has 137 // more than one occurrence of this digit, the cell is not valid. 138 int rowCount = 0; 139 int colCount = 0; 140 int subgridCount = 0; 141 for(int i = 0; i < GRID_SIZE; i++) { 142 if(grid[row][i].getDigit() == digit) rowCount++; 143 if(grid[i][col].getDigit() == digit) colCount++; 144 } 145 for(final XSudokuCell c : subgrids.get(subgrid)) { 146 if(c.getDigit() == digit) subgridCount++; 147 } 148 return rowCount <= 1 && colCount <= 1 && subgridCount <= 1; 149 } 150 151 // Given the previous choice of a digit on a mutable cell, 152 // determine whether we can advance from this choice. 153 @Override 154 public boolean advance(final XMutableCell previous) { 155 if(previous == lastCell) { 156 // The puzzle is solved! 157 driver.setDone(); 158 return true; 159 } 160 // Find the next valid move for the next cell for which we need to make a choice. 161 // If there is none, we can't proceed with the previous choice we made. 162 final XMutableCell nextMove = findNextMove(previous.nextCell); 163 if(nextMove == null) { 164 return false; 165 } 166 167 // We found a move we can try. 168 // Track it. 169 driver.track(nextMove); 170 171 // The the framework to keep building on the choice we just tracked. 172 return true; 173 } 174 175 @Override 176 public String toString() { 177 StringBuilder builder = new StringBuilder(); 178 for(int i = 0; i < grid.length; i++) { 179 for(int j = 0; j < grid[i].length; j++) { 180 builder.append(grid[i][j].getDigit()); 181 builder.append(" "); 182 } 183 builder.append("\n"); 184 } 185 return builder.toString(); 186 } 187 188 // TODO: Start here. Read over the code and comments here first. Don't worry about all the 189 // code you see in this assignment. Focus on the TODOs I have provided. You may wish to 190 // explore the code in detail at some point, but you don't need to understand all of it 191 // in order to succeed on this assignment. 192 // 193 // This is the main program you will run to test out your solution. 194 public static void main(final String[] args) { 195 196 // A Sudoku grid consists of 9 rows and 9 columns, and has 9 3x3 subgrids. Each 197 // cell is in exactly one subgrid. The subgrids, assigned letters A-I here for 198 // illustration, are as follows: 199 // 200 // A A A | B B B | C C C 201 // A A A | B B B | C C C 202 // A A A | B B B | C C C 203 // ------+-------+------ 204 // D D D | E E E | F F F 205 // D D D | E E E | F F F 206 // D D D | E E E | F F F 207 // ------+-------+------ 208 // G G G | H H H | I I I 209 // G G G | H H H | I I I 210 // G G G | H H H | I I I 211 // 212 // Each location in the grid is a cell, which may have an immutable digit as part 213 // of the puzzle definition, or a mutable digit which the Sudoku solver will assign. 214 // Sudoku puzzles of some number of pre-filled cells that serve as clues. 215 // 216 // No digit may appear more than once in any row, column, or subgrid. 217 // 218 // The Sudoku puzzle below has 17 clues. 219 // 220 // If we were to use brute force to solve a 9x9 Sudoku puzzle with 17 clues, 221 // we would need to check all possible combinations of digits for the empty cells 222 // until we find a combination that satisfies all the constraints of Sudoku. 223 // Since there are 64 empty cells in a 9x9 Sudoku puzzle with 17 clues, each of 224 // which can be filled with 9 possible digits, the total number of possible 225 // combinations is 9^64. 226 // 227 // This is an astronomically large number, and it would take an incredibly long 228 // time to check all possible combinations, even with the most powerful computers 229 // available today. In fact, it's estimated that it would take billions of years 230 // to solve a single 9x9 Sudoku puzzle using brute force. 231 // 232 // Fortunately, there are much more efficient algorithms and strategies that can 233 // be used to solve Sudoku puzzles without having to resort to brute force. One 234 // such technique is called backtracking. With backtracking, we repeatedly try 235 // choices we can make to solve a problem, continually building on previous choices. 236 // When we determine that a particular choice will not work, we backtrack to an earlier 237 // decision point and try out a different choice. When we employ this strategy, 238 // we don't have to check every possible solution to a problem independently. When we 239 // backtrack, we eliminate a very, very large number of possible solutions and reduce 240 // the search space significantly. 241 // 242 // On my machine, the backtracking framework solves the puzzle below in about 1 minute. 243 // If you do everything correctly, you should see a message stating that the program 244 // backtracked 58,192,225 times. 245 // 246 // In this implementation of a Sudoku solver, we start at the upper left cell in the 247 // grid, working left to right, trying out possible digits from 1 to 9. When we cannot 248 // place a digit in a cell based on information we already have, we do not bother to 249 // try it. When we can place a digit in a cell, we need to investigate whether that choice 250 // can be fruitful in determining a solution. If we determine that the previous choice 251 // we made cannot be fruitful, all possible solutions with that digit in that cell are 252 // abandoned, and the next digit in that cell is tried. This process continues until all 253 // empty cells are filled with valid digits, and we arrive at a solution to the puzzle. 254 // If there is no solution, the puzzle is defective: the grid with the clues originally 255 // provided would not form a valid puzzle. 256 // 257 // See https://en.wikipedia.org/wiki/Backtracking for more information about backtracking. 258 // TODO: Scroll down to Examples in the Wikipedia article to see an animation of a Sudoku 259 // puzzle being solved using backtracking. That is essentially what this program is doing. 260 // 261 // TODO: Your task: Find the TODOs in algs13.xframework.MyBacktrackDriver. 262 // You will implement the methods that power the xframework that solves backtracking 263 // problems. You will know you have succeeded if the program prints a valid solution to the 264 // problem. This exercise should serve as a powerful example of what you can do with a stack, 265 // and illustrate why we study data structures, and in particular stacks. 266 // 267 // TODO: Additional question for you: Find the linked list in this class. Note that we are 268 // NOT using a class called Node, although there is something analogous to it. Your answer 269 // should indicate the name of the class that is analogous to the Node, and the name of the 270 // variable holding the first pointer. NOTE that the linked list I am looking for is part of 271 // this implementation of the specific problem (and not in the MyBacktrackDriver) and does not 272 // involve the stack used by the driver although the stack does happen to use a linked list. 273 // HINT: Look in the advance method for a "pointer" (pun intended!). If you look at the 274 // constructor for this class, named MySudoku, you will see the list being constructed in 275 // reverse, from the lower right-hand side of the grid to the upper left-hand side. 276 // 277 // TODO: The linked list "Node" class name is: 278 // 279 // TODO: The linked list first pointer is the variable in this class named: 280 // 281 String[] input = { 282 "000060100", 283 "300070000", 284 "000000000", 285 "000300620", 286 "400000500", 287 "700000000", 288 "000207003", 289 "006000080", 290 "010400000" 291 }; 292 293 final MySudoku puzzle = new MySudoku(input); 294 295 final MyBacktrackDriver<XMutableCell> driver = new MyBacktrackDriver<>(puzzle); 296 final Stopwatch s = new Stopwatch(); 297 final XBacktrackResult result = driver.solve(); 298 final double time = s.elapsedTime(); 299 300 StdOut.println(); 301 if(result.isSuccess()) { 302 StdOut.format("Got successful result: in %f seconds\n%s", time, puzzle); 303 StdOut.format("Solution is verified? %s", puzzle.verify()); 304 } 305 else { 306 StdOut.println(result); 307 } 308 } 309}