Project 03: Sudoku Solver

The goal of this assignment is to ensure students have an understanding of:

• Multidimensional arrays
• Recursive methods
• Redirecting a file stdin.
• Problem Description
• Sudoku is a type of puzzle, played with a 9x9 grid containing the numbers 1 through 9 and some blanks. The player tries to fill in the grid while ensuring that each row, column, and 3x3 sub-grid (indicated with the heavier border) contains exactly one of each of the numbers 1 through 9. An example starting grid is seen below on the left as well as the completed version to its right.

326

9 3 5 1 18 64

81 29

7 8 67 82

26 95

8 2 3 9 513

483921657 967345821 251876493 548132976 729564138 136798245 372689514 814253769 695417382

Your goal for this project is to implement a program that solves Sudoku puzzles.

There are several files attached to this assignment on Blackboard. The SudokuSolver.java file is askeleton you'll fill outto complete program. After you download it, you should rename it to FirstnameLastnameProject03.java and rename the main class it contains likewise. The other files are example Sudoku grids you can use to test your program. How to use a file as input to your program instead of typing out the grid each time is explained in a section at the end of this document.

It's recommended you complete program inthree steps, described below.

Step 1: Implement thereadGridandprintGrid

The first two functions you should implement arereadGridandprintGrid.

readGridreads a Sudoku grid the keyboard using theScannerclass. The Sudoku grid is provided with 9 numbers per line, separated by spaces, in 9 lines. Empty spaces, if any are present, are represented as 0. The grid is returned as a 2d array. The array is already created for you in the skeleton file. You can initialize the inner arrays withgrid[i] = new int[9];

printGridprints a Sudoku grid in the same format described above. Printing extra spaces at the end of a line are acceptable.

Step 2: ImplementisValid

Before trying to implement the solver itself, you should start by implementing theisValidfunction to gain a better intuition for how Sudoku works. This function returns true if the Sudoku grid is completed and valid. A grid is complete if it contains no 0s. A grid is valid if each row, column, and 3x3 sub-grid contains exactly one of each of the numbers 1 through 9. You will likely implement this using 3 sets of nested for-loops.

There are a few different approaches you can take to checking the validity of a row/column/sub-grid. Some examples:

• Verify that no two cells in the area you'rechecking contain the same value-duplicates indicate that some value is missing
• Use an array of 9 boolean values to keep track of which values you see in the area. At each step through the iteration, setfound[n - 1] = true, where n is the value containedin the cell you're examining.If one of the values is false after iterating over the area, then you know one is missing
• You may use whichever approach you find easiest/most natural.
• Step 3: implement solve
• The algorithm You will be employing to solve Sudoku grids is a brute force approach. It is analogous to a human trying every single possibility. You start by placing into the first empty cell the first available number at that location and then moving onto the next empty cell. A value is available if it is not used in the column, row, or 3x3 sub-grid the cell is contained in. If at some point you find there are no available numbers at some empty cell, you have to"backtrack" by returning to the previousformerly empty cell and replacing the number there with the next available number. If there are no more available numbers at that location, you have to backtrack even further. Some pseudocode for this approach:
• solve() {
• x, y = next empty cell coordinates if no empty cell exists {
• return true }

 for each available number n at (x, y) { set cell at (x, y) to n // Recurse to move to the next cell if solve() returns true { 

• return true }

 } // Couldn't place any numbers in this cell, so backtrack set cell at (x, y) to 0 return false 

}

It is recommended you start by implementing the two helper functions described below.

Step 3a: ImplementfindNextCell

As should be clear from the pseudocode above, an essential step in solving a Sudoku grid is locating empty cells. ThefindNextCellfunction factors out that step into a separate function to simplify thesolvemethod.

The method outlined in the provided java file takes an x and y coordinates as parameters. This is an optimization to help reduce the amount of searching necessary. Since you know where the previous empty cell was, you can save time by starting our search from that location rather than always starting from 0, 0.

Because functions can only have one return value, this function returns an array. If an empty cell exists, the function should return the x and y coordinates in an array with a length of 2. If no empty cells are left in the grid, then the function should return an array with length 0.

To help you implement this function, a function that tests it (by running the function with known inputs and checking the correctness of the return value) is provided in the skeleton. You can uncomment the first line of themainmethod to enable the tests.

Step 3b: implementvaluesUsedAt

To implement the"for each" loop in the pseudocode,you need a way to determine which numbers are available at a set of coordinates (x, y). ThevaluesUsedAtfunction implements this by computing the opposite-which values are used/not available.valuesUsedAtcommunicates it's result by returning an array of 9booleanvalues. Thebooleanat indexnwill be true ifn + 1is contained in row x, column y, or the sub-grid containing (x, y). Thus, the"for each" loop in the pseudocode can be implemented by iterating over the return value ofvaluesUsedAt. That is, if thebooleanvalue atiis false, theni + 1is an available number.

Remember that when abooleanarray is created, all of its values default to false. As a result,you don't need to do initialization after creating the array.

Like withisValid, you'll likely implementvaluesUsedAtusing 3 sets of nested for loops. As withfindNextCellabove, a test function forvaluesUsedAtis provided in the skeleton.

You can uncomment the second line of the main method to enable the tests.

Redirecting a file to stdin

Because the Sudoku grids are large and complex, you'll want to avoid typing themrepeatedly. Ifyou're working from the command line, then you canuse the < character to use a file as stdin. For example:

java FirstnameLastnameProject03 < incompleteSudoku0.txt

You can find a brief description of how to do the program in Eclipsehere.

In IntelliJ, to select a file to use as input, begin byselecting "Edit Configurations..." from the

drop down at the right of the main editor window.

Then, click the checkbox next to "Redirect input from:" and click the folder icon at the right toselect the file you want to use as input.

import java.util.Arrays; import java.util.Scanner; public class SudokuSolver { static int[][] readGrid() { Scanner scanner = new Scanner(System.in); int[][] grid = new int[9][]; scanner.close(); return grid; } static void printGrid(int[][] grid) { } // Returns true if the sudoku grid passed in is complete and valid. That // is, it contains no 0s, and every row, column, and 3x3 block contains // exactly one of 1-9. static boolean isValid(int[][] grid) { return false; } // Attempts to solve the sudoku grid. If it succeeds, returns true and // updates the grid with the solution. If it cannot find a solution, // returns false. static boolean solve(int[][] grid) { int[] nextEmpty = findNextEmptyCell(grid, 0, 0); if (nextEmpty.length == 0) { return true; } return solve(grid, nextEmpty[0], nextEmpty[1]); } // Attempts to find a solution to the passed in grid. grid[x][u] must the // location of the first empty cell in the grid. If this fails to find a // solution, it returns false and leaves the grid unmodified (ie resets the // cell at (x, y) back to 0). static boolean solve(int[][] grid, int x, int y) { return false; } // Returns the location of the next empty cell in the grid starting from // (x, y) in a 2-value array, where the 0th item is the next coordinate and // the 1st item is the y coordinate. If no empty cells remain in the grid, // it should return an empty (0-length) array. static int[] findNextEmptyCell(int[][] grid, int x, int y) { return new int[] { x, y }; } // Returns a boolean array containing 9-values. The 0th value in the array // is true if a 1 is present in any of the row, column, or 3x3 block // containing (x, y). Likewise, the 1st value is true if a 2 is present, // and so on. static boolean[] usedValuesAt(int[][] grid, int x, int y) { boolean[] usedValues = new boolean[9] return usedValues; } public static void main(String[] args) { // testFindNextEmptyCell(); // testUsedValuesAt(); int[][] grid = readGrid(); printGrid(grid); if (isValid(grid)) { System.out.println("Valid"); } else { boolean solved = solve(grid); if (!solved) { System.out.println("Grid isn't solvabled"); } else { System.out.println("Solved:"); printGrid(grid); } } } // Testing data and methods follow static final int[][] INCOMPLETE_TEST_GRID = new int[][] { new int[] { 0, 0, 0, 0, 0, 0, 9, 0, 7, }, new int[] { 0, 0, 0, 4, 2, 0, 1, 8, 0, }, new int[] { 0, 0, 0, 7, 0, 5, 0, 2, 6, }, new int[] { 1, 0, 0, 9, 0, 4, 0, 0, 0, }, new int[] { 0, 5, 0, 0, 0, 0, 0, 4, 0, }, new int[] { 0, 0, 0, 5, 0, 7, 0, 0, 9, }, new int[] { 9, 2, 0, 1, 0, 8, 0, 0, 0, }, new int[] { 0, 3, 4, 0, 5, 9, 0, 0, 0, }, new int[] { 5, 0, 7, 0, 0, 0, 0, 0, 0, }, }; static void testFindNextEmptyCell() { int[] next = findNextEmptyCell(INCOMPLETE_TEST_GRID, 0, 0); if (!Arrays.equals(next, new int[] { 0, 0 })) { throw new RuntimeException("Expected 0, 0 but got " + next[0] + ", " + next[1]); } next = findNextEmptyCell(INCOMPLETE_TEST_GRID, 1, 3); if (!Arrays.equals(next, new int[] { 4, 3 })) { throw new RuntimeException("Expected 4, 3 but got " + next[0] + ", " + next[1]); } next = findNextEmptyCell(INCOMPLETE_TEST_GRID, 8, 2); if (!Arrays.equals(next, new int[] { 0, 3 })) { throw new RuntimeException("Expected 0, 3 but got " + next[0] + ", " + next[1]); } } static void testUsedValuesAt() { boolean[] used = usedValuesAt(INCOMPLETE_TEST_GRID, 0, 0); boolean[] expected = new boolean[] { true, false, false, false, true, false, true, false, true, }; if (!Arrays.equals(used, expected)) { throw new RuntimeException("Expected " + formatUsedValuesArray(expected) + " got " + formatUsedValuesArray(used)); } used = usedValuesAt(INCOMPLETE_TEST_GRID, 1, 4); expected = new boolean[] { true, true, false, true, true, false, true, true, false, }; if (!Arrays.equals(used, expected)) { throw new RuntimeException("Expected " + formatUsedValuesArray(expected) + " got " + formatUsedValuesArray(used)); } } static String formatUsedValuesArray(boolean[] used) { String s = ""; for (int i = 0; i < used.length; i++) { if (used[i]) { if (s.equals("")) { s += (i + 1); } else { s += ", " + (i + 1); } } } return s; } }