Databases
StackOverflow2013
Postsdbo
PO
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    text
    copied!<p>This recursive solution actually <em>generates</em> all the possible tiling of a general <em>MxN</em> board. It's more general than what your program requires, and therefore not optimized to just <em>count</em> the number of tiling of a <em>3xN</em> board.</p> <p>If you just want to <em>count</em> how many there are, you can use <a href="http://en.wikipedia.org/wiki/Dynamic_programming" rel="nofollow noreferrer">dynamic programming techniques</a> and do this <em>much faster</em>. Also, having the number of rows fixed at 3 actually makes the problem <em>considerably easier</em>. Nonetheless, this general generative solution should be instructive.</p> <pre><code>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); } } </code></pre> <p>So here's the meat and potatoes:</p> <pre><code> void generate(int r, int c) { // find next empty spot in column-major order while (c &lt; N &amp;&amp; board[r][c] != EMPTY) { if (++r == M) { r = 0; c++; } } if (c == N) { // we're done! count++; printBoard(); return; } if (c &lt; N - 1) { board[r][c] = '&lt;'; board[r][c+1] = '&gt;'; generate(r, c); board[r][c] = EMPTY; board[r][c+1] = EMPTY; } if (r &lt; M - 1 &amp;&amp; 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; } } </code></pre> <p>This excerpt from the last few lines of the output gives an example of a generated board, and the final count.</p> <pre><code>//... omitted AA&lt;&gt;&lt;&gt; VVAA&lt;&gt; AAVV&lt;&gt; VVAA&lt;&gt; &lt;&gt;VVAA &lt;&gt;&lt;&gt;VV //... omitted 6728 </code></pre> <p>Note that 6728 checks out with <a href="http://www.research.att.com/~njas/sequences/A004003" rel="nofollow noreferrer">OEIS A004003</a>.</p> <p>A few things that you need to learn from this solutions are:</p> <ul> <li><strong>Clean-up after yourself!</strong> This is a very common pattern in recursive solution that modifies a mutable shared data. Feel free to do <em>your</em> thing, but then <em>leave things as you found them</em>, so others can do <em>their</em> thing.</li> <li><strong>Figure out a systematic way to explore the search space.</strong> In this case, dominoes are placed in <a href="http://en.wikipedia.org/wiki/Row-major_order" rel="nofollow noreferrer">column-major order</a>, with its top-left corner as the reference point.</li> </ul> <p>So hopefully you can learn something from this and adapt the techniques for your homework. Good luck!</p> <hr> <p>Tip: if you comment out the <code>printBoard</code> 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.</p> <hr> <h3>Update!</h3> <p>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!).</p> <p>Since we're fixed at 3 rows, the logic is more explicit if we just have <em>3 mutually recursive functions</em>.</p> <pre><code>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 &amp;&amp; row2.length() == N &amp;&amp; row3.length() == N) { count++; // found one! System.out.format("%s%n%s%n%s%n%n", row1, row2, row3); return; } if (row1.length() &gt; row2.length()) { // not my turn! addRow2(N, row1, row2, row3); return; } if (row1.length() &lt; N - 1) addRow2(N, row1 + "&lt;&gt;", 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() &gt; row3.length()) { // not my turn! addRow3(N, row1, row2, row3); return; } if (row2.length() &lt; N - 1) addRow3(N, row1, row2 + "&lt;&gt;", 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() &lt; N - 1) addRow1(N, row1, row2, row3 + "&lt;&gt;"); } } </code></pre> <p>You don't often see 3 mutually recursive functions like this, so this should be educational.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload