Topics sets, maps, efficiency, and boolean zen Reminder of the Rules of Sudoku Sudoku(Links to an external site.)puzzles[play online(Links to an external site.)]begin with a 9x9 board where each...

Topics

sets, maps, efficiency, and boolean zen

Reminder of the Rules of Sudoku

Sudoku(Links to an external site.)puzzles[play online(Links to an external site.)]begin with a 9x9 board where each "cell" is a number (1-9) or an empty space. The goal of the puzzle is to make it so that

• every row contains the values 1-9 only once per row,


• every column contains the values 1-9 only once per column, and


• each of the inside 3x3 squares only contains the values 1-9 once per small square.

The puzzle is solved once all the cells are filled with a number following the rules of the puzzle.

In this assignment, we will be verifying that they rules of Sudoku are followed and identifying when the puzzle is solved.

Instructions

Part 0: Make a copy of your Sudoku #1 Solution

We will be building off your Sudoku #1 solution. I recommend beginning this assignment by making a new folder with a copy of your Sudoku #1 solution just so that you are working in a new space and can easily start over if needed.

• 
  If you did not complete Part 1, you can usethis solution to Part 1 of Sudokuas starter code for this assignment.Note that I have intentionally provided a solution to Part 1 that is not stylistically beautiful according to my standards; however it does work. The reason for this is that I don't want to see my solution turned in during future quarters - so I'm giving you a working - but non-optimal - solution as your starting code if you need to use it. This way I can easily identify it should it accidentally make it's way to Chegg (not that any of you would do that).

Part 1: isValid

You should add a method to your board class that will return true if all of the following constraints are followed according to the board's current data; false otherwise:

• there is no data in the board that is not a 1-9 or a space (or your representation of a space - could be a '.' or a 0, etc)


• no row contains any duplicate values of 1-9


• no column contains any duplicate values of 1-9


• no mini-square contains any duplicate values of 1-9

Use private helper methods

I recommend creating private helper methods for each of these four constraints and then checking if all the constraints are true in your isValid method. Make sure to use Boolean zen! (This is similar to how our TicTacToe game had an isSolved method that utilized helper methods isFull and checkWinner.)

Checking for valid data

Go through the entire 2D structure and check that none of the cells contain data that is not allowed. You can solve this using any way you want - I recommend putting the valid data values in an ArrayList or a Set and then using contains() on that structure to make sure every cell's data is valid. Return true if all data is valid; false if any one piece of data is invalid.

Note that in terms of efficiency:

• if you choose to use an ArrayList for this solution, your efficiency for this method will be O(n * m) at best because for every value in your 2D array you will need to check every value in the ArrayList (in the worst case).


• if you choose to use a TreeSet for this solution, your efficiency for this method will be O(n log m) at best because for every value in your 2D array you will need to check every value in the TreeSet (in the worst case) which is an O(log n) operation.


• if you choose to use a HashSet for this solution, your efficiency for this method will be O(n) at best - which is the best of these three options - because for every value in the 2D array you will need to check every value in the HashSet (in the worst case) which is an O(1) operation.


• if your internal structure is an int[][] rather than a char[][], you can write a solution that does not require auxiliary storage (you can do this with the char[][] as well, but it reads less cleanly, I think) - this solution will be O(n) because you will still need to visit every element in the 2D array to make sure only the values 0-9 occur.

Checking the rows

Make sure that no row contains a duplicate value.This should be checked using a Set (either Set or Set depending on your board implementation choice).If you put all the values for the row into the set, then you will be able to check if the set contains the value as you go to see if there are duplicates.

Checking the columns

This will be similar to check rows, except you'll be looking for duplicates vertically in the board instead of horizontally.

Checking the mini-squares

In Sudoku, the board is actually not just a 9x9 grid, it's really a 3x3 grid of 3x3 mini-squares. One of the constraints of Sudoku is that each mini-square only contains the values 1-9 once (similar to a row or a column). I anticipate that this check will be the hardest for you to complete so I am going to give you a little helper method here that you can use:

private int[][] miniSquare(int spot) {       int[][] mini = new int[3][3];       for(int r = 0; r

Note that if you used a char[][], you should change all my int[][] to char[][]; also change `board` to be the name of your 2D internal structure

Example: If we had an internal Sudoku board that looks like:

530070000 600195000 098000060 800060003 400803001 700020006 060000280 000419005 000080079

Then, miniSquare(1) would return

530 600 098

and, miniSquare(5) would return

060 803 020

If you call this method with the mini-square location that you want to access (looking at it like our tic-tac-toe board configuration for the mini-squares), then you will be returned a 2D array of the mini-square. You can then solve the problem similar to the rows and columns.

Part 2: isSolved

You should add a method to your board class that will return true if there are nine occurrences of every number 1-9 in the grid AND all the constraints of isValid are followed.

There are several ways that you could check to see if the board is solved such as just checking that there are no spaces (or dots or 0s left in the grid - depending on your implementation); however,I expect you to use a Map for this check. You should create a single map, iterate over the entire 2D structure counting the occurrences of each value 1-9. If all values nine times AND the board isValid, then the puzzle is solved.

Part 3: Test your Sudoku functionality

To test that everything works, run mySudokuCheckerEngineV2.java


using these providedboard data files. If all tests pass, you are good to go.

• Assertions allow us to verify that a certain condition is true in the code at a given point.


• 
  In JGrasp, you must enable assertions in order to use them.To do this go to the Build menu --> Enable Assertions, then run your file like normal. If an assertion fails, the program will end and the assertion error message will tell you what's wrong.

What to Submit

• Your modified board class


• The SudokuCheckerEngine with output showing the results of your test cases.

Submission Requirements

You should do the following for _all_ assignments submitted for this course.

ProgramComment

Include a comment at the beginning of your program with the followinginformation and a description of the program in your own words:

// Your name here // CS 143 // HW Core Topics: ... // // This program will ...

Program Output

Include the output from a single run of your program as a block comment at the end ofthe program. This comment should come one blank line after the last closing curly brace in your code.

}
/* Paste the output from JGrasp here. Altering output will earn you an automatic zero for the assignment. */

Rubric