MySudokuBoard.java :

import java.util.*; import java.io.*;

public class MySudokuBoard { public final int SIZE = 9; protected char[][] myBoard; public MySudokuBoard(String theFile) { myBoard = new char[SIZE][SIZE]; try { Scanner file = new Scanner(new File(theFile)); for(int row = 0; row map = new HashMap(); for(char[] row : myBoard) { for(char cell : row) { if(map.containsKey(cell)) map.put(cell, map.get(cell) + 1); else map.put(cell, 1); } } // info on Collections: https://docs.oracle.com/javase/8/docs/api/?java/util/Collections.html return map.keySet().size() == 9 && Collections.frequency(map.values(),9) == 9; } public boolean isValid() { // checks for bad data for(char[] row : myBoard) for(char cell : row) if(cell != '.' && (cell '9')) return false; // checks for row/col violations for(int r = 0; r trackingRow = new HashSet(); Set trackingCol = new HashSet(); for(int c = 0; c trackingMini = new HashSet(); for(int r = 0; r

}

SudokuCheckerEngine.java :

public class SudokuCheckerEngineV2 {

public static void main(String[] args) { // Note that here I am calling the board object MySudokuBoard // if you named your class something different, you should // find and replace all `MySudokuBoard` with your class name boolean allTests = true; // an empty board is valid, but not solved System.out.print("Checking empty board..."); MySudokuBoard board1 = new MySudokuBoard("boards/empty.sdk"); assert board1.isValid() : "isValid: should be true"; assert !board1.isSolved() : "isSolved: should be false"; if(board1.isValid() && !board1.isSolved()) System.out.println("passed."); else { System.out.println("failed."); allTests = false; } // an incomplete, valid board is valid, but not solved System.out.print("Checking incomplete, valid board..."); MySudokuBoard board2 = new MySudokuBoard("boards/valid-incomplete.sdk"); assert board2.isValid() : "isValid: should be true"; assert !board2.isSolved() : "isSolved: should be false"; if(board2.isValid() && !board2.isSolved()) System.out.println("passed."); else { System.out.println("failed."); allTests = false; } // a complete, valid board is valid and solved System.out.print("Checking complete, valid board..."); MySudokuBoard board3 = new MySudokuBoard("boards/valid-complete.sdk"); assert board3.isValid() : "isValid: should be true"; assert board3.isSolved() : "isSolved: should be true"; if(board3.isValid() && board3.isSolved()) System.out.println("passed."); else { System.out.println("failed."); allTests = false; } // a board with dirty data is not valid and not solved System.out.print("Checking dirty data board..."); MySudokuBoard board4 = new MySudokuBoard("boards/dirty-data.sdk"); assert !board4.isValid() : "isValid: should be false"; assert !board4.isSolved() : "isSolved: should be false"; if(!board4.isValid() && !board4.isSolved()) System.out.println("passed."); else { System.out.println("failed."); allTests = false; } // a board with a row violation is not valid and not solved System.out.print("Checking row violating board..."); MySudokuBoard board5 = new MySudokuBoard("boards/row-violation.sdk"); assert !board5.isValid() : "isValid: should be false"; assert !board5.isSolved() : "isSolved: should be false"; if(!board5.isValid() && !board5.isSolved()) System.out.println("passed."); else { System.out.println("failed."); allTests = false; } // a board with a column violation is not valid and not solved System.out.print("Checking col violating board..."); MySudokuBoard board6 = new MySudokuBoard("boards/col-violation.sdk"); assert !board6.isValid() : "isValid: should be false"; assert !board6.isSolved() : "isSolved: should be false"; if(!board6.isValid() && !board6.isSolved()) System.out.println("passed."); else { System.out.println("failed."); allTests = false; } // a board with both a row and a column violation is not valid and not solved System.out.print("Checking row&col violating board..."); MySudokuBoard board7 = new MySudokuBoard("boards/row-and-col-violation.sdk"); assert !board7.isValid() : "isValid: should be false"; assert !board7.isSolved() : "isSolved: should be false"; if(!board7.isValid() && !board7.isSolved()) System.out.println("passed."); else { System.out.println("failed."); allTests = false; } // a board with a mini-square violation is not valid and not solved System.out.print("Checking mini-square violating board..."); MySudokuBoard board8 = new MySudokuBoard("boards/grid-violation.sdk"); assert !board8.isValid() : "isValid: should be false"; assert !board8.isSolved() : "isSolved: should be false"; if(!board8.isValid() && !board8.isSolved()) System.out.println("passed."); else { System.out.println("failed."); allTests = false; } if(allTests) System.out.println("**** HORRAY: ALL TESTS PASSED ****"); } }

SudokuSolverEngine.java :

public class SudokuSolverEngine {

public static void main(String[] args) { // Here I have called my class `MySudokuBoard` if you named your class // differently, modify the line below to use your own class name MySudokuBoard board = new MySudokuBoard("boards/very-fast-solve.sdk"); System.out.println("Initial board"); System.out.println(board); System.out.println();

System.out.print("Solving board..."); long start = System.currentTimeMillis(); board.solve(); long stop = System.currentTimeMillis(); System.out.printf("SOLVED in %.3f seconds. ", ((stop-start)/1000.0)); System.out.println(); System.out.println(board); } }

Part 1: solve() method header and initial checks Add a method to your board class that will allow the puzzle to be solved. This method is going to take no parameters, as it will operate on the 2D array that is already stored in the Board. This method will return true or false, depending on whether or not the puzzle can be solved. - If your board state is invalid - you already have a method that can check this - then you should immediately return false because the board cannot be solved. - If your board is already solved - you also already have a method that can check this - then you should return true because the board is already solved. - In all other cases you have an incomplete, but valid, board so you will use recursive backtracking to attempt to solve the puzzle. - If in your exhaustive searching you find a solution, you'll end up returning true; but - if you never find a solution, you'll end up returning false. Part 2: solve() with recursive backtracking Tackling the recursive backtracking of this solution is not going to require a lot of code. For reference, my solution is around 20 lines of code in total. Yours does not need to be the same length, but I will be surprised if it is much longer. The hard part with recursive backtracking is *thinking* in the appropriate way. I highly recommend reviewing 8 Queens problem from chapter 12 of our text book a the solution is similar to this problem. The general idea is that you need to try the values 1-9 in each of the empty spaces on your board in an intentional and brute force / exhaustive way. Every time you try a number you check if this creates a valid state on the board and then recurse hoping this leads you to a solution. If it does, you end up returning true up and up out of the recursive calls. However before that is likely to happen, you will hit several dead end solutions where you need to recurse out once and undo whatever change you tried on your board. Again, recursive backtracking is essentially made up of three parts: 1) try something 2) recurse and see if this leads to a solution 3) undo what you tried if the recursive try didn't work out. Part 3: Test your Sudoku Solver functionality To test that everything works, run my SudokuSolverEngine.java using these provided board states: very-fastsolve.sdk and fast-solve.sdk I am giving you these test boards because it turns out that recursive backtracking is both memory in-efficient and slow. This means that if you try to solve() some of the boards from Sudoku \#2, the solve() method might run for a very long time. You need to add two things to the SolverEngine. 1. Before trying to solve the board, check if the board is in an invalid state. If it is, print a message to the screen that says that the board cannot be solved. - You can test with the any of the rules violating boards from Sudoku \#2 2. Before trying to solve the board, check if the board is already solved. If it is, print a message to the screen that says that the board is already solved. - You can test with the valid-complete.sdk board from Sudoku \#2 What to Submit - Your modified board class - The SudokuSolverEngine with your modifications Submission Requirements You should do the following for_all_assignments submitted for this course