*Sudoku* is a cool game of logic that has been popular around the world for
some years and is now becoming well known in the US.
To play the game go here.
In the first two problems in this homework, you will implement a simple Sudoku
solver.
A Sudoku game can be represented by a 2-dimensional 9 by 9, integer array.
Each slot in the game is identified by a pair (`i`, `j`),
0 <= `i` < 9, and 0 <= `j` < 9.
Some of the slots are already filled in with integers (in the range 1 through 9)
whereas some of the slots are empty.
The goal is to fill these empty slots according to the rules of the game.
For each empty slot, (`i`, `j`), let
*A*(`i`, `j`) denote the subset of {1, 2, ..., 9}
consisting of numbers that can legally be filled in slot (`i`, `j`).
I propose that you implement the following simple algorithm to solve
a given Sudoku game.

- Compute
*A*(`i`,`j`) for all empty slots (`i`,`j`). - If the size of
*A*(`i`,`j`) is 1 for any empty slot (`i`,`j`), then fill slot (`i`,`j`) with the number in*A*(`i`,`j`). - If there are no empty slots, quit the program. Otherwise, go to Step 1.

My guess is that there are many Sudoku puzzles this program will be unable to solve. Below, I describe some experiments you can perform to test how well this program is doing.

To implement the above program, we will first implement the *Set* ADT.
Once the set ADT is implemented, we can define a 9 by 9, 2-dimensional array of sets
and use this to keep track of which slot (if any) to fill next.

- A
*Set*ADT represents some subset of {1, 2, ...,`n`} for some natural number`n`. It supports the operations*insert*,*delete*,*isMember*,*isEmpty*,*union*, and*intersection*, which are described below.- S.insert(x) takes a number x in {1, 2, ..., n} and inserts x it into S.
- S.delete(x) takes a number x in {1, 2, ..., n} and deletes it from S.
- S.isMember(x) takes a number x in {1, 2, ..., n} and returns true if x is in S and returns false, otherwise.
- S.isEmpty() returns true if S is empty and returns false otherwise.
- S.union(A) takes a subset A of {1, 2, ..., n} and changes S to S union A.
- S.intersection(A) takes a subset A of {1, 2, ..., n} and changes S to S intersection A.

`n`. If an element*x*in {1, 2, ..., n} belongs to the set, then slot x-1 in the boolean array should be true; otherwise it should be false. Partial implementation of the Set ADT is given here. Complete it.**Solution:**Here is the implementation of the Set ADT. - Here are more details for implementing the Sodoku solving algorithm, described
above.
First, define a 9 by 9 2-dimensional array, called
`Soduko`. This will keep track of the current status of the game and will contain integers between 0 and 9. The entry 0 will correspond to an empty slot. Then, define a 9 by 9 2-dimensional array of sets, called`allowedSets`. For each slot (`i`,`j`), 0 <=`i`< 9, and 0 <=`j`< 9, if this slot is filled, then`allowedSets`[`i`][`j`] should be an empty set. Otherwise,`allowedSets`[`i`][`j`] should contain the subset of {1, 2, ..., 9} containing all entries that are legal for slot (`i`,`j`). In each iteration of your algorithm, you will scan`allowedSets`[`i`][`j`], for various values of`i`and`j`. There are three possibilities:- All the sets are empty, implying that the game has been completed.
- All the sets have size more than one, implying that our algorithm is stuck and can make no further progress.
- There is a set of size one.

If the third possibility holds, then the algorithm finds the slot (

`i`,`j`) for which the size of`allowedSets`[`i`][`j`] is one and fills slot (`i`,`j`) with the number in`allowedSets`[`i`][`j`]. Then the algorithm should delete this number from all`allowedSets`[`k`][`l`] which are in the same row or the same column or the same 3 by 3 block as slot (`i`,`j`). Then the algorithm goes to the next iteration.Write a java program that implements the above algorithm. Equip the program with the ability to read a Sudoko game typed at the keyboard and also equip the program with the ability to output a Sudoku game (either completed or partially completed).

Run your program on a few of the Sudoku games here. Can you find a Sudoku game that your program cannot solve? If so, print it out and also output the allowed set for each empty slot.

**Solution:**Here is the implementation of the Sudoku program. -
For each of the claims below, say whether the claim is true or false.
Provide a 1-2 sentence justification for your answer.
A formal proof is not necessary.
If it helps you think, for part (1) below, you can assume that sqrt(n) is an
integer.
- 1 + 2 + 3 + ... + sqrt(n) = Theta(n).
**True.**Substituting sqrt(n) for n in the formula for the sum of the first n natural numbers, we get sqrt(n)(sqrt(n) + 1)/2. This simplifies to n/2 + sqrt(n)/2. This is Theta(n). - 8 log_2(n) + 12 log_5(n) = O(log n).
**True.**Since one can replace one fixed base by any other fixed base of a logarithm and that changes the term just by a constant factor. - 8 log_2(n) + 12 log_5(n) = O(n^2).
**True.**Since n^2 grows much faster than both terms on the left. - n^2 + 2^n = Theta(2^n).
**True.**Since 2^n grows much faster than n^2 and is the dominant term on the left.

- 1 + 2 + 3 + ... + sqrt(n) = Theta(n).