Computer Science 3300
Spring 2007
Section 001
Programming Assignment 2

Read the entire assignment before you start working on it. It will appear very large and difficult at first. But, if you do it the way that I have suggested, you will only need to write roughly 250-300 lines. Just work your way forward, one step at at time.

Table of contents

1. Background
2. Requirements
3. Sets
4. Puzzles
5. Getting a section of a puzzle
6. Reading and writing puzzles
7. Tactic 1
8. Repeating tactic 1
9. Tactic 2
10. Tactic 3
11. Debug prints
12. 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.

Requirements

Write a C++ program that reads a sudoku puzzle and prints a solution to that puzzle. 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. 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

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
• intset.cpp

Use sets as follows.

1. Include intset.h in your program, as follows.

     #include "intset.h"
   

   (Notice the quotes instead of <...>. The quotes tell the compiler to look for intset.h in the folder that this file is in, while <...> tell the compiler to look in the standard library folder.)

2. Copy this Makefile to the directory that holds your program. Compile using command make. The makefile assumes that your program is called sudoku.cpp, and it builds an executable program called sudoku. It also contains a target called clean, so that command make clean removes all machine-generated files, and a target run, so that command make run runs the program on file puzzle1.txt. You can modify the makefile to make it do different things.

Here is a brief description of how to use 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}.

emptySet

emptySet is an empty set. For example,

  SetOfSmallInts s;
  s = emptySet;

creates a variable s, and initializes it to hold an empty set.

isEmpty(s)

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

rangeSet(x,y)

rangeSet(x,y) is a set {x, x+1, ..., y} holding all numbers 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}.

singletonSet(x)

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

  SetOfSmallInts t;
  t = singletonSet(1);

makes t hold set {1}.

isSingleton(x)

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

onlyMember(s)

If s is a singleton set, then onlyMember(s) returns the member of s. If s is not a singleton set, then onlyMember(s) returns 0. For example,

  SetOfSmallInts s = singletonSet(3);
  int n = onlyMember(s);

makes n = 3.

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.

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.

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 = range(1,5);
  t = range(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 = range(1,5);
  t = range(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.

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, remove(x,s) returns s.

size(s)

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

Puzzles

A puzzle is a 9x9 array of sets. If you include definition

  typedef SetOfSmallInts Puzzle[9][9];

To get you going, here is a function that copies a puzzle. You can copy it into your program. (Just copy and paste. Do not copy it by hand!)

/****************************************************************
 *                      copyPuzzle                              *
 ****************************************************************
 * Copy puzzle p into pp.  For example, if p is a puzzle, then  *
 *    Puzzle pp;                                                *
 *    copyPuzzle(pp, p);                                        *
 * stores a copy of puzzle p into pp.                           *
 ****************************************************************/

void copyPuzzle(Puzzle pp, Puzzle p)
{
  int i, j;
  for(i = 0; i < 9; i++) 
  {
    for(j = 0; j < 9; j++) 
    {
      pp[i][j] = p[i][j];
    }
  }
}

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, not just to look at them. You can do that as follows. Copy the following into your program. (Just copy and paste. Do not copy it by hand!)

typedef SetOfSmallInts* PuzzleSection[9];
#define val(x) (*(x))

/****************************************************************
 *                      getRow                                  *
 ****************************************************************
 * Store the i-th row of puzzle p into R, an array of variables.*
 * The rows are numbered from 0 to 8.                           *
 *                                                              *
 * After doing this, the k-th set in row i is val(R[k]).        *
 * Do not omit val(...). The cells in the row are numbered      *
 * 0,1,...,8.                                                   *
 ****************************************************************/

void getRow(PuzzleSection R, Puzzle p, int i)
{
  int j;
  for(j = 0; j < 9; j++) 
  {
    R[j] = &(p[i][j]);
  }
}


/****************************************************************
 *                      getColumn                               *
 ****************************************************************
 * Store the j-th column of puzzle p into R, an array of        *
 * variables.  The columns are numbered from 0 to 8.            *
 *                                                              *
 * After doing this, the k-th set in column j is                *
 * val(R[i]).  Do not omit val(...).  The cells in the          *
 * column are numbered 0,1,...,8.                               *
 ****************************************************************/

void getColumn(PuzzleSection R, Puzzle p, int j)
{
  int i;
  for(i = 0; i < 9; i++) 
  {
    R[i] = &(p[i][j]);
  }
}

/**************************************************************** 
 *                      getSquare                               *
 ****************************************************************
 * Store the k-th square of puzzle p into R, an array of        *
 * variables.   The squares are numbered as follows.            *
 *           0 1 2                                              *
 *           3 4 5                                              *
 *           6 7 8                                              *
 *                                                              *
 * After doing this, the i-th set in the square is val(R[i]).   *
 * Do not omit val(...). The cells in the square are numbered   *
 * 0,1,...,8, in the same pattern shown above for the squares   *
 * themselves.                                                  *
 ****************************************************************/

void getSquare(PuzzleSection R, Puzzle p, int k)
{
  int i;
  for(i = 0; i < 9; i++) 
  {
    R[i] = &(p[k - k%3 + i/3][3*(k%3) + i%3]);
  }
}

Now suppose that p has type Puzzle.

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

For example, statement

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

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

Reading and writing puzzles

Start by writing three functions, one to read a puzzle and two to write a puzzle. Use the following headings.

void readPuzzle(Puzzle p)

Read a puzzle from the standard input (cin) in the form shown above. Store it into p.

void printPuzzle(Puzzle p)

Print puzzle p on the standard output (cout), in the same form as the input. If a set is a singleton set, write the number in that set. If it is not singleton, write '-'. The purpose of this is the show the puzzle that you read.

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}

Also write a main program that reads a puzzle and prints it back out using both printPuzzle and showPuzzle. Make sure that all three of these 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

Tactic 1

There are a few tactics that people use to solve sudoku puzzles. The simplest, and most useful, tactic 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. A simple way to run this tactic is to go through each row, then each column, then each square. At each singleton set in a row, go back through the entire row, excluding the position of the singleton set, and remove the given value from all of the sets in that row. Do the same for columns and squares.

Write a function that performs tactic 1, doing just one scan through all of the rows, columns and squares. Make it return a boolean result: true if it changed any set, and false if it did not make any changes. (How can you tell if it made a change? Removing K from a set that does not contain K does not make a change.)

It is awkward if you have to write separate code to handle rows, then to handle columns, then to handle squares. (The squares are especially difficult.) But remember that you have a function that will extract a section of the puzzle. If you write a function that does this tactic on a section, be it a row, column or square, then you can use that function for every row, column and square. Do that.

Now write another function (let's call it the solver) whose job is to find a solution to a given puzzle. The puzzle should be a parameter. Make it run tactic 1 just once, and return. It should be very short.

You now have three functions: the solver, the function that does tactic 1 on all rows, columns and squares, and the function that does tactic 1 on a section.

Modify your main function so that it reads a puzzle, runs the solver, then prints the puzzle, using showPuzzle. Try it. Does it appear to be working? Are the sets modified in a sensible way? Remember that this simple solver will probably not reach a final solution. Do not move on until you have checked this part, and it looks like it is performing one round of tactic 1 correctly.

Repeating tactic 1

Now modify the solver so that it does tactic 1 over and over, until it no longer makes any changes. Test it. Show the puzzle after each time you do tactic 1 on it.

For easy puzzles, this is all that is required. For example, what you have now should be adequate to solve puzzle 1 given above. Write a function that checks whether all of the sets in the puzzle are singleton. Modify the solver so that it returns true when it has completely solved the puzzle, and returns false if it has not solved it. Add a test to your solver: when all of the sets are singleton, it should return true.

Your new solver should have the following rough (pseudo-code) form.

  Loop {tactic 1 loop}
    1. Run tactic 1.  
    2. Do a debug print: show the puzzle, along with a clear
       indication that it was produced by tactic 1.
    3. If all sets are singleton, then return true from solver.
    4. If tactic 1 returned 0 in step 1, then exit the loop.
  end loop
  Return false from solver. (The solver did not finish the puzzle,
    but tactic 1 cannot help any more.)

Tactic 2

Some puzzles will still remain unsolved after tactic 1 has nothing more to contribute. But there is another commonly employed tactic that can help. Suppose that you look at all of the sets in a given row, and only one of those sets contains 2. Then, clearly, that cell must hold 2. So you change it to {2}, a singleton set.

You can do the same for every row, column and square, and for every number from 1 to 9. Write a function that does this to a section, by checking, for every number k from 1 to 9, whether there is just one set in the section that holds k. If so, it should make that set be the singleton set {k}.

Modify your solver to work as follows. (This is a description of the algorithm, in pseudo-code, not a C++ program.)

  Loop (main loop)
    1. Run tactic 1 repeatedly until it returns false.  (This is the
        tactic 1 loop in the preceding algorithm.)
    2. Run tactic 2 once.  If it returns false, exit the main loop.
    3. Do a debug print: show the puzzle, as modified by tactic 2.
    4. If all of the sets are singleton, return true from the solver.
  end loop
  Return false from the solver.

Test this. Try it on puzzle 3. (It will not finish, but if you are showing the puzzle at every step, you will see the progress.) Do not move on until your program seems to be working so far. Do not take it for granted that it works. Look at what your program is doing with a critical eye.

  for i = 0, ..., 8
    for j = 0, ..., 8
      if p[i][j] is not a singleton set  (try values for this set)
        for k = 1, ..., 9
          if k is a member of p[i][j]
            Make a copy (pp) of puzzle p.
            pp[i][j] = {k}  (a singleton set -- this is where we try k)
            Run the solver on pp.  
            If the solver returned 1, then 
              Copy pp back into p
              Return true (the puzzle is solved)
            end if
          end if 
        end for
        return false (none of the values for this set work, so
                      the puzzle has no solution)
      end if
    end for
  end for

Debug prints

It is a very good idea to include some debug prints in this program, as explained above, so that you can see what is happening. Of course, when the program is finished, you do not want them to run. But if you remove them, you might find later on that you want them back. For example, what if you thought that the program was working, but then discover a problem later? There is an easy way to leave the debug prints in the program, and to give yourself the ability to turn them on and off. Write a debug print as in the following example.

# ifdef DEBUG
   cout << ... (print what you want)
# endif

#define DEBUG

//#define DEBUG

Submitting Your Work

You will turn in two versions of this program, unless your grade on version 1 is one that you prefer to keep. To submit a version of a program, run one of the following commands in a terminal window. I am assuming that your program is called sudoku.cpp. If it has a different name, substitute that name.

First version

~karl/3300/bin/submit 2a sudoku.cpp

Second version

~karl/3300/bin/submit 2b sudoku.cpp