This recursive solution actually generates all the possible tiling of a general MxN board. It's more general than what your program requires, and therefore not optimized to just count the number of tiling of a 3xN board.
If you just want to count how many there are, you can use dynamic programming techniques and do this much faster. Also, having the number of rows fixed at 3 actually makes the problem considerably easier. Nonetheless, this general generative solution should be instructive.
public class Domino {
final int N;
final int M;
final char[][] board;
int count;
static final char EMPTY = 0;
Domino(int M, int N) {
this.M = M;
this.N = N;
board = new char[M][N]; // all EMPTY
this.count = 0;
generate(0, 0);
System.out.println(count);
}
void printBoard() {
String result = "";
for (char[] row : board) {
result += new String(row) + "\n";
}
System.out.println(result);
}
void generate(int r, int c) {
//... see next code block
}
public static void main(String[] args) {
new Domino(6, 6);
}
}
So here's the meat and potatoes:
void generate(int r, int c) {
// find next empty spot in column-major order
while (c < N && board[r][c] != EMPTY) {
if (++r == M) {
r = 0;
c++;
}
}
if (c == N) { // we're done!
count++;
printBoard();
return;
}
if (c < N - 1) {
board[r][c] = '<';
board[r][c+1] = '>';
generate(r, c);
board[r][c] = EMPTY;
board[r][c+1] = EMPTY;
}
if (r < M - 1 && board[r+1][c] == EMPTY) {
board[r][c] = 'A';
board[r+1][c] = 'V';
generate(r, c);
board[r][c] = EMPTY;
board[r+1][c] = EMPTY;
}
}
This excerpt from the last few lines of the output gives an example of a generated board, and the final count.
//... omitted
AA<><>
VVAA<>
AAVV<>
VVAA<>
<>VVAA
<><>VV
//... omitted
6728
Note that 6728 checks out with OEIS A004003.
A few things that you need to learn from this solutions are:
- Clean-up after yourself! This is a very common pattern in recursive solution that modifies a mutable shared data. Feel free to do your thing, but then leave things as you found them, so others can do their thing.
- Figure out a systematic way to explore the search space. In this case, dominoes are placed in column-major order, with its top-left corner as the reference point.
So hopefully you can learn something from this and adapt the techniques for your homework. Good luck!
Tip: if you comment out the printBoard line, you can generate all ~13 million boards for 8x8 in reasonable time. It'll definitely be much faster to just compute the number without having to generate and count them one by one, though.
Update!
Here's a recursive generator for 3xN boards. It doesn't use a shared mutable array, it just uses immutable strings instead. It makes the logic simpler (no clean up since you didn't make a mess!) and the code more readable (where and how the pieces are placed is visible!).
Since we're fixed at 3 rows, the logic is more explicit if we just have 3 mutually recursive functions.
public class Domino3xN {
static int count = 0;
public static void main(String[] args) {
addRow1(8, "", "", "");
System.out.println(count);
}
static void addRow1(int N, String row1, String row2, String row3) {
if (row1.length() == N && row2.length() == N && row3.length() == N) {
count++; // found one!
System.out.format("%s%n%s%n%s%n%n", row1, row2, row3);
return;
}
if (row1.length() > row2.length()) { // not my turn!
addRow2(N, row1, row2, row3);
return;
}
if (row1.length() < N - 1)
addRow2(N, row1 + "<>",
row2,
row3);
if (row2.length() == row1.length())
addRow3(N, row1 + "A",
row2 + "V",
row3);
}
static void addRow2(int N, String row1, String row2, String row3) {
if (row2.length() > row3.length()) { // not my turn!
addRow3(N, row1, row2, row3);
return;
}
if (row2.length() < N - 1)
addRow3(N, row1,
row2 + "<>",
row3);
if (row3.length() == row2.length())
addRow1(N, row1,
row2 + "A",
row3 + "V");
}
static void addRow3(int N, String row1, String row2, String row3) {
if (row3.length() == row2.length()) { // not my turn!
addRow1(N, row1, row2, row3);
return;
}
if (row3.length() < N - 1)
addRow1(N, row1,
row2,
row3 + "<>");
}
}
You don't often see 3 mutually recursive functions like this, so this should be educational.