|
|
|
|
|
|
|
|
|
Programming 1 Course (202-1-9011) Web-Site |
First Semester
2002 |
|
Exercise number 3
Playing Domino
In this
exercise we play Domino. Please, remember your childhood
when you
use to play with 28 pieces of Domino. Each piece has two
numbers
from 0 to 6. Here, you use the same 28 pieces but with different
game
rules. We number the pieces in the following way:
1 0:0 8 1:1
15 2:3 22 3:6
2 0:1 9 1:2
16 2:4 23 4:4
3 0:2 10 1:3
17 2:5 24 4:5
4 0:3 11 1:4 18 2:6 25 4:6
5 0:4 12 1:5
19 3:3 26 5:5
6 0:5 13 1:6
10 3:4 27 5:6
7 0:6 14 2:2
21 3:5 28 6:6
Now
someone placed the whole 28 pieces as 7X8 matrix of numbers as shown
in the
following example.
6 4 1 6
5 2 6 2
1 3 4 0
1 0 3 2
1 5 4 4
6 6 3 2
1 1 2 3
2 1 0 4
5 5 5 6
0 4 1 3
5 0 3 0
2 6 5 4
6 0 3 3
4 2 0 5
Or if we write the same configuration with pieces number we will get:
25 25 13 13 17 17 22 14
8 21 5 5
2 2 22 14
8 21 23 23 28 28 4 16
12 9 9 15 15 11 4 16
12 26 26 7
7 11 10 10
27 1 19 3
3 18 6 24
27 1 19 20 20 18 6 24
Now,
suppose that someone gives you the upper set of numbers and ask you
to place
the 28 pieces back in place. Can you?
We sure
you do!
So, we
ask you to write a C program that can do the same work:
Given the matrix of 7X8 numbers as input,
your program writes as output
how to place
the 28 pieces so they fit to the input.
Of course,
there can be more then one answer for a given input and we
want your
program to print all the possible answers. For example: to the
our above input
there are 8 different solutions.
Now, let see
how we can make it without computer:
We look on the
top left corner of the matrix of numbers
and see two
possibilities:
1) To place the
piece 6:4 horizontally
2) To place the
6:1 vertically
Now, you are
called up to make decision. You do not know, and therefore
need to check
both options. But, we can do just one at a time.
We pick the
first choice and make a note to try the other one later.
So we write 25
25 in our solution matrix and go on.
So, now we try
to place up more pieces. We now can try to place 1:6
horizontally or
1:4 vertically. We choose the first choice and make a
note to check
the other option later and go on.
So, we now all
say load and clear: It is a recursive program!
Now, you can
see that you need to check systematically all the
possibilities.
So, in each
level, we decide to check first the horizontal option and
then the
vertical option.
However this
decision process can stuck. Why?
Because you can
find yourself trying to use a piece that you
already used
before.
We have a
binary tree of decisions and if we stuck in one decision we
cancel it and
step backward and try another option that
"we leave
as note". However, for a recursive program this is just
a return with
fail and program continues on.
So you can see
immediately that the heart of your recursive program is
two recursive
calls, one to check the horizontal option and one to check
the vertical
option.
Another small
section is to find the next empty place you want to put
the next piece.
Also when you backup, do not forget,
to erase all
the assignments in your output matrix, that you do so far.
The erase
action, in real game, it is parallel to "pick up" pieces out
of the solution
that you already try.
You need to
find all possible solutions for a given input.
How you can do
that easily? Simply, each time you find a solution
you print it
out and then "cheat" the program: You tell it that this
solution is
"no good" and send the program to search for another
solution. And
how do you do the cheating? After you put the last piece
you "pick it
up" as you do for wrong piece as in the upper paragraph,
and let the
program continue in its toil.
And here is
another hint for you: Each time you try to place a piece
on the board
you deal with two numbers, and you need to translate these
two numbers to
specific piece number.
For example,
you want to try to put the piece 1:3 and succeed, so you
want to write
the number 10 in those two places. How can you
translate 1:3
to 10? One option is to open
a 2 dimension
array 7X7 and store the pieces number there.
In our example
the entry [1][3] = 10 and also [3][1] = 10.
Another option
is an integer function that gets the two numbers and
returns the
piece number.
Since, we recommend
this array option, we permit you to define it as
global
variable, but this is the only global variable we allow.
Naturally, there are
many numbers involved in the input and the output
of this program. In
order to enable a reasonable checking we insist
on standard input
format:
7 lines. 8 numbers
from 0 to 6 in each line.
The output should be
in the same format but write 3 empty lines to
separate one solution
from the next one.
In order to get the
different solutions in the same order for all
programs we insist
that your program will check recursively first
the horizontal option
and then the vertical option.
Important
notes:
- Instructions how and
where to submit your program are in the home page (Click on the
"SUBMIT" option in the home page).
- Don't forget to check that the
input data are valid and not out of the defined range.
- Don't forget to write clear comments,
a nice presentation of the program, meaningful variable names and a
friendly interface.
- Also, do not use anything you
didn't learn in class.
- It is very recommended that
you check that your programs compiles and runs properly on Microsoft®
Visual C++ 6.00, before you submit them.
Last date to submit your work: Monday,
December 17, 2001 (At midnight between Monday and Tuesday).
GOOD
LUCK !
Zion, Tania, Tal, Olga and Eliezer.