| Assigned: | September 16 |
| First version due: | October 4, 11:59pm |
| Second version due: | October 15, 11:59pm |
Read the entire assignment before you start working on it. It might 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.
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 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 --4You cannot assume that there are spaces or empty lines. So the input might also be as follows.
1--489--6 73-----4- -----1295 --712-6-- 5--7-3--8 --6-957-- 9146----- -2-----37 8--512--4
The output should be the solved puzzle, in a similar style. Please write the output with spaces and line breaks the way it was shown in the first input example, regardless of the original form of the input. For example, the output might be as follows.
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
You will want to store a set of possible values for each cell. You can use the following implementation of sets. Get both files.
To use sets, do the following.
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.)
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
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)
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(x)
onlyMember(s)
SetOfSmallInts s = singletonSet(3); int n = onlyMember(s);makes n = 3.
smallest(s)
SetOfSmallInts s = rangeSet(3,6); int n = smallest(s);makes n = 3.
member(x,s)
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 = range(1,5); t = range(3,7); u = setIntersection(s,t);makes u = {3,4,5}.
setDifference(s,t)
SetOfSmallInts s,t,u; s = range(1,5); t = range(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)
size(s)
A puzzle is a 9x9 array of sets. If you include definition
typedef SetOfSmallInts Puzzle[9][9];then you can use Puzzle as a type, indicating a 9x9 array of sets. 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 the puzzle is puzzle[0][0].
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! Be sure to copy the comment too, not just the function definition.)
/****************************************************************
* copyPuzzle *
****************************************************************
* Copy puzzle p into pp. For example, if p is a puzzle, then *
* Puzzle q; *
* copyPuzzle(q, p); *
* stores a copy of puzzle p into q. *
****************************************************************/
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];
}
}
}
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. So what you really want is a pointer back into the original array, so that any changes you make affect the original array. You can do that as follows. Copy the following into your program. (Just copy and paste. Do not copy it by hand! Copy the comments too.)
typedef SetOfSmallInts* PuzzleSection[9];
/****************************************************************
* getRow *
****************************************************************
* Store the i-th row of puzzle p into puzzle section R. *
* The rows are numbered from 0 to 8. *
* *
* After doing this, the k-th set in row i is *(R[k]). *
* Do not omit *(...). 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 puzzle section R. *
* The columns are numbered from 0 to 8. *
* *
* After doing this, the k-th set in column j is *
* *(R[i]). Do not omit *(...). 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 puzzle section R. *
* The squares are numbered as follows. *
* 0 1 2 *
* 3 4 5 *
* 6 7 8 *
* For example, square 4 is the middle square in the puzzle. *
* *
* After doing getSquare, the i-th set in the square is *(R[i]).*
* Do not omit *(...). The cells in the square are numbered *
* 0,1,...,8, in the same pattern shown above for the squares *
* themselves. For example *(R[3]) is the first position in *
* the second row of the square. *
****************************************************************/
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]);
}
}
Suppose that p has type Puzzle.
PuzzleSection Sec; getSquare(Sec, p, 0);makes Sec hold the square in the upper-left corner of puzzle p (square 0). The members of array Sec correspond to cells in puzzle p, as follows.
| Section entry | Corresponds to |
|---|---|
| *(Sec[0]) | p[0][0] |
| *(Sec[1]) | p[0][1] |
| *(Sec[2]) | p[0][2] |
| *(Sec[3]) | p[1][0] |
| *(Sec[4]) | p[1][1] |
| *(Sec[5]) | p[1][2] |
| *(Sec[6]) | p[2][0] |
| *(Sec[7]) | p[2][1] |
| *(Sec[8]) | p[2][2] |
For example, statement
*(Sec[4]) = setDifference(*(Sec[4]), s);has the same effect as
p[1][1] = setDifference(p[1][1], s);
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, if you use the iostream library) in the form shown above. Store it into p.
void printPuzzle(Puzzle p)
Print puzzle p on the standard output (cout, if you use the iostream library), in a form suitable for the final output. If a set is a singleton set, write the number in that set. If it is not singleton, write '-'. If it is empty, write 0.
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 4You 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 0 rather
than showing nothing at all.
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.
There are a few tactics that people (and computers) use to solve Sudoku puzzles. A simple and obvious 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. 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, in addition to the ones that I gave you: a function that runs tactic 1 on a section; a function that runs tactic 1 once for each row, column and square; and the solver, which just calls the prior function to do tactic 1 on each row, column and square.
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, so the sets will not all be singleton. Do not move on until you have checked this part, and it looks like it is performing one round of tactic 1 correctly.
Write a function that takes a puzzle as a parameter and returns true if all of the sets in the puzzle are singleton sets, and false if there is at least one nonsingleton set.
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. Make the solver return true if it ends with all sets singleton, and false if there is a nonsingleton set left at the end. Your new solver should have the following rough (pseudo-code) form.
1. Loop {tactic 1 loop}
a. Run tactic 1.
b. Do a debug print: show the puzzle, along with a clear
indication that it was produced by tactic 1.
c. If all sets are singleton, then return true from solver.
d. If tactic 1 returned 0 in step 1, then exit the loop. Otherwise,
run the loop body again.
end loop
2. Return false from solver. (The solver did not finish the puzzle,
but tactic 1 cannot help any more.)
For easy puzzles, this is all that is required. For example, what you have now should be adequate to solve puzzle 1 given above.
Some puzzles will still remain unsolved after tactic 1 has nothing more to contribute. But there is another commonly employed tactic that can help. (This tactic is the one that people tend to use, since it is easy to keep track of what you are doing.) 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.)
1. Loop (main loop)
a. Run tactic 1 once on the entire puzzle. Remember
its result, telling whether it made any progress.
b. Run tactic 2 once on the entire puzzle. Remember
its result, telling whether it made any progress.
c. If neither tactic 1 nor tactic 2 made any progress,
then exit the main loop. (The solver will return false.
But do not just say 'return false'. You will want to
do more things after the loop later.)
d. If all of the sets are singleton, then return true from the solver,
indicating that the puzzle is solved.
end loop
2. Return false from the solver.
Test this. Try it on puzzle 3. (It will not finish, and the solver should return false, 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. Are the tactics doing sensible things? Are your debug prints readable, so that you can tell?
Many puzzles can be solved using only tactics 1 and 2. But some, such as puzzle 3, are more stubborn. We will end with a tactic that is guaranteed to finish the job, for every puzzle.
Suppose that, after running tactics 1 and 2 until they no longer help, there are still nonsingleton sets. Then find one of the nonsingleton sets, and try each possible value for it.
Of course, some of your choices will not work. So you have to consider the possibility that a puzzle is not solvable. The solver already returns a boolean value. Previously, that value was true to indicate that the puzzle was solved, and false to indicate that the puzzle had not yet been solved. Change the meaning of the returned value so that true means the puzzle is solved, and false means that the puzzle has no solution. (After adding tactic 3, there will never be a case where the puzzle is solvable, but the solver does not finish the job.) When you make a change of meaning like this, always update the documentation.
(Remember that tactics 1 and 2 return true to indicate that they made a change and false to indicate that they did not make a change. Do not change anything about them. They still work the same way.)
Add a function that performs tactic 3 on a puzzle. It should also return true if the puzzle has been solved, and false if the puzzle has no solution. Tactic 3 works roughly as follows, where p is the puzzle that it is working on.
for i = 0, ..., 8
for j = 0, ..., 8
if p[i][j] is not a singleton set
comment: try values for this set
for k = 1, ..., 9
if k is a member of p[i][j]
Make a copy (q) of puzzle p.
q[i][j] = {k} (a singleton set -- this is where we try k)
Do a debug print showing the puzzle being tried.
Run the solver on q.
If the solver returned 1, then
Copy q back into p
Return true (the puzzle is solved)
end if
Do a debug print explaining that the solver
is backing up and trying a different value.
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
It is important to work on a copy of the puzzle, so that the changes that you make will not wreck what you have. Also, notice that tactic 3 only tries values for the first non-singleton set that it encounters. If it cannot find a value to use for that set, there is no point in going ahead and looking for values for other sets. All it takes is one spot that cannot be filled in to make the puzzle unsolvable. If you move the return of false outside of the for loops, then you will discover that your program runs for hours or days, even on a puzzle that has a solution, because it keeps trying options that could easily have been ruled out.
With the addition of tactic 3, you now have the possibility that the puzzle has no solution. It is important to check to see whether any of the sets has become empty, since an empty set indicates that no values will work. Write a function that checks whether any of the sets in a puzzle are empty. Modify the solver function so that it works as follows. Added parts are in red.
1. Loop (main loop)
a. Run tactic 1 once on the entire puzzle. Remember
its result, telling whether it made any progress.
b. If the puzzle contains an empty set, then return
false from the solver.
c. Run tactic 2 once on the entire puzzle. Remember
it result, telling whether it made any progress.
d. If neither tactic 1 nor tactic 2 made any progress,
then exit the main loop.
e. If all of the sets are singleton, then return true from the solver,
indicating that the puzzle is solved.
end loop
2. Run tactic 3 on the puzzle,
and return the same answer as tactic 3 returns.
(True indicates that the puzzle is solved, and false indicates that there
is no solution.)
Notice that you do not try tactic 3 every time around the main loop. The
reason is that tactic 3 is relatively expensive, and you would prefer to use
it only when the cheaper tactics 1 and 2 have nothing more to contribute.
Note. The solver uses tactic 3, and tactic 3 uses the solver. That is allowed. It is called mutual recursion. But you will need to help the compiler, so that you can use a function before it is defined. If you want to use the solver before it is defined, copy the heading of the solver to an earlier place in the program, and write a semicolon at the end of the heading. That tells the compiler that the definition of the solver is coming, but lets you use the solver before you define it. For example, write
bool solve(Puzzle p);somewhere before the occurrence of tactic 3, so that tactic 3 can use solve.
Test your program. Do not just presume that it works.
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 the program appears to be working, but then you discover a problem later when you try it on a new puzzle? 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(You can use either the iostream or the stdio libraries to do the printing.) This tells the compiler only to put this in the program is symbol DEBUG is defined. You can define DEBUG by adding
#define DEBUGsomewhere near the top of the program. To turn off the debug prints, just replace that by
//#define DEBUGso that DEBUG is not defined. Do not remove the debug prints. If you leave them in place, then you can easily turn them on again later by removing the //.
Software needs to be tested extensively. Any time you make a modification, you really should go back and redo all of your tests to make sure that you have not inadvertantly ruined something that used to work. But you do not want to do that by hand; that is far too much work. So you put together a suite of tests, called regression tests, that run automatically. You generally leave tests in the suite, even after they work, unless they are testing something that the software no longer supports.
The Makefile that I supplied contains a target called run so that command make run runs just one test. It does command
sudoku <puzzle1.txtwhich says to run executable program sudoku with the standard input being read from file puzzle1.txt. Modify the Makefile. Add a target called test so that command make test will run sudoku on each of puzzle1.txt, puzzle2.txt and puzzle3.txt in turn.
(Regression tests are normally done with debugging turned off. You only turn debugging on when a test does not work and you want to find out why not. Ideally, each test checks its own work and you only get output shown if the test is incorrect. Yours won't do that. But if you did want to automate checking, you would run another program that captures the standard output from sudoku and checks it. For example, command
sudoku <puzzle1.txt | checkpuzzle puzzle1.anssends the standard output of the sudoku program to the standard input of the checkpuzzle program. That is, checkpuzzle sees in its standard input just what sudoku writes to its standard output. You would write checkpuzzle to read the given file (puzzle1.ans) and to read its standard input, and check whether the two are identical.)
You will turn in two versions of this program, unless your grade on version 1 is one that you are willing 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. Submit both your source program and your Makefile. Do not submit your executable program or test files (puzzle1.txt, etc.)
~abrahamsonk/3300/bin/submit 2a sudoku.cpp Makefile
~abrahamsonk/3300/bin/submit 2b sudoku.cpp Makefile