Assigned: | Wednesday, February 11 |
Intermediate version due: | Wednesday, February 18, 11:59pm |
Version (a) due: | Wednesday, February 25, 11:59pm |
Version (b) due: | Sunday, March 22, 11:59pm |
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.
Write a C++ program that reads a Sudoku puzzle and prints a solution to that puzzle.
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
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.
The program requires you to provide tracing capabilities in your program. See tracing, below.
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.
Get the template for this assignment. It has the things discussed below already installed in it.
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.
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
emptySet
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)
size(s)
rangeSet(x, y)
SetOfSmallInts s; s = rangeSet(1, 9);makes set s = {1,2,3,4,5,6,7,8,9}.
singletonSet(x)
SetOfSmallInts t; t = singletonSet(1);makes t hold set {1}.
isSingleton(s)
member(x, s)
smallest(s)
SetOfSmallInts s = rangeSet(3,6); int n = smallest(s);makes n = 3.
setUnion(s, t)
SetOfSmallInts s, t, u; s = singletonSet(2); t = singletonSet(6); u = setUnion(s,t);makes u hold set {2,6}.
setIntersection(s, t)
SetOfSmallInts s,t,u; s = rangeSet(1,5); t = rangeSet(3,7); u = setIntersection(s,t);makes u = {3,4,5}.
setDifference(s, t)
SetOfSmallInts s,t,u; s = rangeSet(1,5); t = rangeSet(3,7); u = setDifference(s,t);makes u = {1,2}.
insert(x, s)
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)
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
The template file contains a function, copyPuzzle, that makes a copy of a puzzle. Look at it to see how to use 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;indicating that a PuzzleSection is a pointer to an array of pointers, where each of those pointers points to one set. Three functions for extracting sections from puzzles.
getRow(s, p, i)
getColumn(s, p, i)
getSquare(s, p, i)
Suppose that p has type Puzzle. Then
PuzzleSection Sec = newPuzzleSection(); getSquare(Sec, p, 0);makes Sec hold the square in the upper-left corner of puzzle p (square 0). Then *(Sec[0]) is equivalent to p[0][0], the upper left corner of that square. Statement
*(Sec[4]) = setDifference(*(Sec[4]), s);has the same effect as
p[1][1] = setDifference(p[1][1], s);since the set at index 4 in Sec is the middle one in the square.
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();creates a variable p of type Puzzle and makes p point to newly allocated memory. When you are finished with puzzle p, give the memory back using
deletePuzzle(p);Function newPuzzleSection() allocates a new puzzle section and deletePuzzleSection(s) gives that memory back.
To build your program, copy file Makefile to the directory containing your program. It contains a few targets to make. For example, command
make sudokucompiles and links the program. Command
make run1compiles and runs the program on puzzle1.txt. Command
make testruns the program on puzzle1.txt, puzzle2.txt and puzzle3.txt.
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.
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.
Once the readPuzzle, printPuzzle and showPuzzle functions are working, submit them as assignment 3i. Include a main function that tests them.
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};
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.
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 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.
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.)
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.
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); }inside tactic 1, then you make tactic 1 show what it is doing. Of course, you do not always want it to do that. So you have a switch (variable trace1) to turn it on or off.
Create two global variables trace1 and trace2, of type int.
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).
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.
Design your program to look at the command line (parameter argv to main) and to do the following.
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.
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.
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
To turn in version (a),
do the following.
~abrahamsonk/3300/bin/submit 3a sudoku.cpp
To turn in version (b), do the following.
~abrahamsonk/3300/bin/submit 3b sudoku.cpp
After submitting, you should receive confirmation that the
submission was successful. If you do not receive confirmation,
assume that the submission did not work.
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.