22C:21: Computer Science II: Data Structures

## Problem Set 3. Posted 2/2

Notes: Of the three problems given below, one will be solved by the TAs in next week's discussion section, you will have to solve one in class, and the remaining problem is due in the lecture on Friday, 2/10.

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.

1. Compute A(i, j) for all empty slots (i, j).
2. 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).
3. 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.

1. 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.
I want you to implement the Set ADT as a boolean array of size 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.

2. 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:
1. All the sets are empty, implying that the game has been completed.
2. All the sets have size more than one, implying that our algorithm is stuck and can make no further progress.
3. 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.

3. 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. 1 + 2 + 3 + ... + sqrt(n) = Theta(n).

2. 8 log_2(n) + 12 log_5(n) = O(log n).

3. 8 log_2(n) + 12 log_5(n) = O(n^2).

4. n^2 + 2^n = Theta(2^n).