Printable View
I have attached the assignment given by my professor. I'm just a little confused. I can't develop and algorithm for this. I know I need a 2-D array for the board, but I don't know how to fill it and then rearrange the Dominoes to find the number of different ways to fill the board. If I'm not clear just tell me and I will clarify.
Thanks!!!!
Psycho
my file didn't attach so here it is:
CSCE 1040.001/.002
Program # 4, 100 points
Due: April 30, 2010 at 10:00pm.
You are to write a Java method which will count the number of different ways that a 3xN board can be completely filled with dominos (a domino is 1x2). Completely, in this case, means there are no unfilled cells in the board. The best way to fill the board is to fill columns left-to-right using recursion (see Chapter 11 of the text). The value of N (N>1) will be passed to your program via args[0].
Dominoes may be placed horizontally or vertical. At any position, both possible domino placements should be tried. I.e – placing a domino horizontally.
Your program (main) is to call the method defined above and produce one number, the number of possible ways to completely fill a 3xN board, with appropriate formatting and description, of course. Also, your program should contain appropriate comments.
Submit a single java file via Blackboard.
NOTES:
There are three ways to completely fill a 3 x 2.
There are zero ways to completely fill a 3 x 3.
The board can be a 2-dimentional integer array. Your program must work for any value of N (N>1). Therefore you must allocate memory for any arrays dynamically, either in main or inside of a class.
I strongly recommend that you write a printBoard method to help you with debugging. A good way to keep track of dominoes (mark them on the board) is to number them sequentially and to print them out mod 10. Thus, the first solution of the 3x3 would be printed as
1 3
1 3
2 2
One possible way to split up the work would be to write the two methods.
1. tryHorizontal(row, col) which would try to place a domino horizontally at board[row, col] and board[row, col+1], checking, of course, for conditions like board position already filled, placing part of a domino outside of the board, etc.
2. and tryVertical(row, col) which would try to place a domino vertically.
These two methods would be used inside of a method tryRowCol(row, col).
E.g.
public tryRowCol( int row, int col){
if (.…) tryHorizontal(row, col);
if (…..) tryVertical(row, col);
} // end tryRowCol