Computer Science 3300
Spring 2015
Section 001
Programming Assignment 3

Table of contents

1. Background
2. Functional requirements
3. Nonfunctional requirements
4. Template
5. Sets
6. Puzzles
7. Getting a section of a puzzle
8. Building and running your program
9. Reading and writing puzzles
10. The puzzle solver
11. Tactic 1
12. Tactic 2
13. Trace prints
14. Submitting your work

Background

A Sudoku puzzle is a 9x9 grid. Some of the cells have digits in them and some are empty. The grid naturally breaks into rows and columns, but it is also broken into nine 3x3 squares. For example, see here for sample puzzles. The goal is to fill in a digit into each of the empty cells, with the following requirements.

1. Each digit must be from 1 to 9.
2. Each row, column and square has all of the digits from 1 to 9 in it, each exactly once.

Functional Requirements

Write a C++ program that reads a Sudoku puzzle and prints a solution to that puzzle.

Input format

The input format is described in detail below. Your program is required to support that input format. Approximately, the puzzle is presented as 9 lines, with 9 nonblank characters per line. A digit represents an initially occupied cell and a dash represents an empty cell. There can be empty lines, which are skipped, and there can be spaces in a line, which are also skipped. The input might be as follows.

1-- 489 --6
73- --- -4-
--- --1 295

--7 12- 6--
5-- 7-3 --8
--6 -95 7--

914 6-- ---
-2- --- -37
8-- 512 --4

Output format

The output should consist of the original puzzle followed by the the solved puzzle, in a similar style. The output must clearly identify to puzzle as the input and the solution as the solution. Write the output with spaces and line breaks the way it was shown in the input example above, regardless of the original form of the input. For example, the output might be as follows.

The original puzzle:

1-- 489 --6
73- --- -4-
--- --1 295

--7 12- 6--
5-- 7-3 --8
--6 -95 7--

914 6-- ---
-2- --- -37
8-- 512 --4

Solution:

152 489 376         
739 256 841
468 371 295

387 124 659
591 763 428
246 895 713

914 637 582
625 948 137
873 512 964    

The puzzle was solved.

Tracing

The program requires you to provide tracing capabilities in your program. See tracing, below.

Nonfunctional Requirements

The program is required to be written in accordance with the design issues and algorithmic issues discussed below.

The program is required to follow the coding standards for this course, which include the following.

• The program must use the correct file format and file name. See the template below.
• Every function is required to have a clear, concise and precise contract telling what the function accomplishes and returns and how each of its parameters influences what it accomplishes and what it returns. The contract must not be concerned with how the function works.
• Each function can have at most one loop in its body.
• A function body must not change the value of a call-by-value parameter.
• Do not write functions that do not perform their whole jobs.
• Use margin comments sparingly.
• Avoid code duplication.
• End the last line.
• Do not use global or static variables.
• Every body of an if-statement, loop, etc. must be a compound statement.
• Do not use redundant tests in if-statements.
• If code is only performed at the end of the last iteration of a loop, then it should be written after the loop.

Template

Get the template for this assignment. It has the things discussed below already installed in it.

Sets

You will want to store a set of possible values for each cell. You can use the following implementation of sets. Get both files, intset.h and intset.cpp.

• intset.h
• intset.cpp

You can use the features listed below. Only use the features of the intset module mentioned here. If you use undocumented features, your program will not compile when I compile it, even if it compiles when you compile it.

Important note. None of the functions provided for type SetOfSmallInts changes a set. They all take const parameters. Even functions whose names might suggest that they make a change do not make a change. They produce new sets.

SetOfSmallInts

SetOfSmallInts is a type. Use it like any other type. A value of type SetOfSmallInts is a subset of {1,2,3,4,5,6,7,8,9}. (It does not need to be a proper subset, so it can be set {1,2,3,4,5,6,7,8,9}.) When you create a variable of type SetOfSmallInts, it is automatically initialized to hold an empty set.

emptySet

emptySet is an empty set. For example,

  SetOfSmallInts s;
  s = emptySet;

creates a variable s, and explicitly initializes it to hold an empty set. (The initialization is redundant, since s is initialized to an empty set automatically when it is created.)

isEmpty(s)

isEmpty(s) returns true if s is an empty set, and false otherwise.

size(s)

size(s) returns the number of members that set s has. For example, size(rangeSet(2,5)) = 4.

rangeSet(x, y)

rangeSet(x, y) is a set {x, x+1, ..., y} holding all integers that are greater than or equal to x and less than or equal to y. For example, rangeSet(2,6) is set {2,3,4,5,6}. Notice that rangeSet(3,2) is {}, since there are no integers that are greater than or equal to 3 and less than or equal to 2. For example,

  SetOfSmallInts s;
  s = rangeSet(1, 9);

makes set s = {1,2,3,4,5,6,7,8,9}.

singletonSet(x)

singletonSet(x) returns a set that contains only x. For example,

  SetOfSmallInts t;
  t = singletonSet(1);

makes t hold set {1}.

isSingleton(s)

isSingleton(s) returns true if set s holds exactly one number, and false otherwise.

member(x, s)

member(x, s) returns true if x is a member of set s, and false otherwise. For example, if s is set {2,4}, then member(2, s) is true, but member(5, s) is false.

smallest(s)

smallest(s) returns the smallest member of s, or 0 if s is an empty set. For example,

  SetOfSmallInts s = rangeSet(3,6);
  int n = smallest(s);

makes n = 3.

setUnion(s, t)

setUnion(s,t) returns the union of sets s and t. For example,

  SetOfSmallInts s, t, u;
  s = singletonSet(2);
  t = singletonSet(6);
  u = setUnion(s,t);

makes u hold set {2,6}.

setIntersection(s, t)

setIntersection(s, t) returns the intersection of sets s and t (the set of all numbers that are in both s and t). For example,

  SetOfSmallInts s,t,u;
  s = rangeSet(1,5);
  t = rangeSet(3,7);
  u = setIntersection(s,t);

makes u = {3,4,5}.

setDifference(s, t)

setDifference(s,t) returns the set of all numbers that are in s but not in t. For example,

  SetOfSmallInts s,t,u;
  s = rangeSet(1,5);
  t = rangeSet(3,7);
  u = setDifference(s,t);

makes u = {1,2}.

insert(x, s)

insert(x, s) returns the set that you get by adding x to set s. It does not change s. If x is already in s, insert(x, s) returns s. For example,

  SetOfSmallInts u,v;
  u = singletonSet(3);
  v = insert(5, u);

makes u = {3} and v = {3,5}. Notice that creating v does not change u.

remove(x, s)

remove(x, s) returns the set that you get by removing x from set s. It does not change s. If x is not in s then remove(x, s) returns s.

Puzzles

Logically, a puzzle is a 9x9 array of sets. You will represent a puzzle as an array of pointers, where each pointer points to an array of sets. Type definition typdef SetOfSmallInts** Puzzle; defines type Puzzle to be the same as SetOfSmallInts**. If p has type Puzzle, then p[i][j] is the set stored at row i, column j of p. The rows and columns are numbered from 0 to 8, not from 1 to 9. So the upper left corner of puzzle p is p[0][0] and the lower right corner is p[8][8].

The template file contains a function, copyPuzzle, that makes a copy of a puzzle. Look at it to see how to use a Puzzle.

Getting a Section of a Puzzle

You will find it useful to be able to extract a row, column or square of a puzzle as an array of 9 sets. But you need to be able to change those sets in the original puzzle, not just to look at them. So what you really want is a pointer back into the original puzzle, so that any changes you make affect the original puzzle. The template file contains type definition

  typedef SetOfSmallInts** PuzzleSection;

getRow(s, p, i)

Store row i of puzzle p into section s.

getColumn(s, p, i)

Store column i of puzzle p into section s.

getSquare(s, p, i)

Store square i of puzzle p into section s.

Suppose that p has type Puzzle. Then

  PuzzleSection Sec = newPuzzleSection();
  getSquare(Sec, p, 0);

  *(Sec[4]) = setDifference(*(Sec[4]), s);

  p[1][1] = setDifference(p[1][1], s);

Allocating and Deallocating Memory

Functions are provided for you to allocate and deallocate puzzles and puzzle sections. Be sure to use them. To allocate a new puzzle, use newPuzzle(). For example,

  Puzzle p = newPuzzle();

  deletePuzzle(p);

Building and Running Your Program

To build your program, copy file Makefile to the directory containing your program. It contains a few targets to make. For example, command

make sudoku

make run1

make test

1. Reading and Writing Puzzles

This section starts a development plan. Start by writing three functions, one to read a puzzle and two to write a puzzle, plus a main program to test them.

Puzzle readPuzzle()

Read a puzzle from the standard input in the form shown above. Allocate memory for it and return the puzzle.

You cannot assume that there are spaces or empty lines in the input puzzle, and you cannot assume that there is only one space between separate nonblank characters. The input might be as follows

1--489--6
73-----4-
-----1295
--712-6--
5--7-3--8
--6-957--
9146-----
-2-----37
8--512--4

or as follows.

   1  -  -   4  8  9   -  -  6
   7  3  -   -  -  -   -  4  -
   -  -  -   -  -  1   2  9  5

   -  -  7   1  2  -   6  -  -
   5  -  -   7  -  3   -  -  8
   -  -  6   -  9  5   7  -  -

   9  1  4   6  -  -   -  -  -
   -  2  -   -  -  -   -  3  7
   8  -  -   5  1  2   -  -  4

(Don't overcomplicate this. Just skip white space when getting a character. It does not matter what the white space consists of.)

void printPuzzle(Puzzle p)

Print puzzle p on the standard output in a form suitable for the final output.

• If a set is a singleton set, write the only member of that set (a single digit).
• If it is an empty set, write *
• Otherwise, write '-'.

The puzzle must be broken into squares in the form of the sample input above. Use this function to show both the original puzzle and the solved puzzle.

void showPuzzle(Puzzle p)

Print puzzle p on the standard output, but in a form suitable for debugging. For each set, print all of the members of the set. Make the output look nice. Keep the columns aligned. For example, a puzzle might look as follows when printed using showPuzzle.

1         5         25        4         8         9         3         7         6                    
7         3         259       2         5         6         18        4         1                    
46        46        8         3         7         1         2         9         5                    
34        489       7         1         2         4         6         5         39                   
5         49        129       7         46        3         149       12        8                    
234       48        6         8         9         5         7         12        123                  
9         1         4         6         37        78        58        258       2                    
6         2         5         89        4         48        158       3         7                    
8         7         3         5         1         2         9         6         4                    

You can see that the first square contains

 {1}   {5}   {2,5}
 {7}   {3}   {2,5,9}
 {4,6} {4,6} {8}

Design showPuzzle so that, if it encounters an empty set, it shows an asterisk rather than showing nothing at all.

int main(int argc, char** argv)

Read a puzzle and show it using printPuzzle and showPuzzle.

Make sure that all of those functions appear to be working before moving on. Resist the temptation to move on to the rest before you are ready. Here are some puzzles for testing your program.

• puzzle1.txt
• puzzle2.txt
• puzzle3.txt

Intermediate version

Once the readPuzzle, printPuzzle and showPuzzle functions are working, submit them as assignment 3i. Include a main function that tests them.

The Puzzle Solver

You will need a function, the solve(p), that solves puzzle p. It will employ tactics described below.

The solver should a value of type SolutionStatus, defined as follows.

  enum SolutionStatus {solved, unsolvable, working};

• Result solved indicates that a solution has been found and stored into p. In this case, each set in p must be a singleton set.
• Result unsolvable indicates that the puzzle has no solution. The sets in p are meaningless in this case.
• Result working indicates that the solver has run out of idea, but has neither succeeded in solving the puzzle nor concluded that it is unsolvable.

You will need functions to test the status. Write a function that takes a puzzle and returns true if all of the sets are singleton. Write another function that takes a puzzle and returns true if there is an empty set in the puzzle.

Tactic 1

There are a few tactics that people (and computers) use to solve Sudoku puzzles. A simple and obvious tactic (tactic 1) is to locate singleton sets, which are cells whose values are known. If K occurs in a singleton set, then K cannot occur in any other set in the same row, column or square. So remove it from them all.

Start with a helper function that performs tactic 1 on a given puzzle section (representing a given row, column or square of the puzzle). Then write a function that does tactic 1 on every row, column and square in a give puzzle. Make it only do a single pass over every row, column and square. The order in which the rows, columns and squares are done is not important.

Both the helper function and the full tactic 1 function should return true if a change was made to the puzzle and false if no change was made. Neither the helper function nor the full tactic 1 function should stop immediately when a change is made to the puzzle. They should continue to look for more changes, finishing each row, column and square.

Many puzzles can be solved using only tactic 1. Write the solver so that it runs tactic 1 repeatedly until tactic 1 says that it does not make any changes. The solver should then examine the puzzle and return an appropriate status result.

Test this before moving on. Puzzles 1 and 2 can be solved using only tactic 1. Puzzle 3 cannot.

Tactic 2

Tactic 2 works as follows. Suppose that, after running tactics 1 until it no longer helps, there are still nonsingleton sets, but no empty sets. Then find one of the nonsingleton sets and try each member of it as a possible value. Work on a copy of the puzzle with some speculative information installed.

You will need a function that performs tactic 2 on a puzzle. Here are some suggestions.

1. Speculate(p, i, j) tries each value for the set at row i, column j of puzzle p. For each one, it makes a copy c of puzzle p, installs the chosen value for row i, column j in the copy, then runs the solver on the copy. If the solver is successful, then speculate copies c back into p and returns solved. If the solver says the puzzle is unsolvable, speculate tries the next speculated value. If none of the values leads to a success, speculate returns unsolvable. (Speculate will never need to return working.)

2. Tactic2(p) finds a nonsingleton set (say, at row i, column j). It performs speculate(p, i, j) to try each possibility for p[i][j]. If speculate returns solved, tactic2 returns solved. If speculate returns unsolvable, tactic2 returns unsolvable.

Trace Prints

Professional software designers write their programs for testing, right from the start. They do everything they can to make them work, but then presume that there will be problems. (There usually are.) The idea is not to wait until problems show up to think about testing. Think about it from the beginning.

One way to think about testing from the start is to build in tracing capabilities. If you write

  if(trace1 > 0) 
  {
    printf("tactic 1: here is the initial puzzle\n");
    showPuzzle(p);
  }

Create two global variables trace1 and trace2, of type int.

1. If trace1 is positive, tactic 1 should show the puzzle at the beginning and the end of one full scan over the puzzle (every row, column and square). If trace1 > 1, then tactic 1 should show the sets in a puzzle section before and after processing that section. It must say what the section represents (such as row 3).

2. If trace2 is positive, tactic 2 should show the puzzle at the beginning of a call to speculate, and indicate which set it is speculating on. It should show each value that it tries and indicate whether that value worked. If trace2 > 1, then speculate should show the full puzzle (with speculated information installed) at the beginning and end of working on it.

Never print raw information, such as numbers or just a puzzle without saying indicating the context. Always say which function is showing it, and what it represents. See tracing.

Turning Tracing On and Off

Design your program to look at the command line (parameter argv to main) and to do the following.

1. If the command line contains -t1=1, then set trace1 = 1. If it contains -t1=2, then set trace1 = 2. If it contains neither of those, then set trace1 = 0.

2. If the command line contains -t2=1, then set trace2 = 1. If it contains -t2=2, then set trace2 = 2. If it contains neither of those, then set trace2 = 0.

Submitting Your Work

You must submit your program using the following method. Email submissions will not be accepted. An excuse that you do not know how to use Linux will not be accepted.

To turn in the intermediate version (3i), log into one of the Linux machines, change your directory to the one that holds your programs, and do the following command.

  ~abrahamsonk/3300/bin/submit 3i sudoku.cpp

  ~abrahamsonk/3300/bin/submit 3a sudoku.cpp

  ~abrahamsonk/3300/bin/submit 3b sudoku.cpp

Late submissions

Late submissions on version (a) will be accepted for one day after the due date. Late submissions for version (b) will be accepted for three days after the due date. If you miss a late submission deadline by a microsecond, your work will not be accepted.