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}