All geek questions in one place

Java array recursion

I need to create a program that will find all possible ways to fill a square of size x by y. You put a block that takes 2 spaces to completely fill.

The problem is that I donโ€™t know how to encode it to such an extent that you can remember the location of each square. I can get him to where he fills the board once, and possibly twice, but nothing has passed. I also know that I have to use recursion to figure this out. Here is the code that I started so far. There is also a basic method, and I have an initial even / odd work check. This is the part that I have no idea about.

    public void recurDomino(int row, int column) {
            if (Board[2][x - 1] != false) {

            } else if(Board[1][x-1]!=false)
            {

            }
            else {
                for (int n=0; n < x - 1; n++) {
                    Board[row][column] = true;
                    Board[row][column+1] = true;
                    column++;
                    counter++;
                } 
                recurDomino(1, 0);
                recurDomino(2, 0);

            }
        }

Thank you for any help you guys can give me. 


******************* EDIT ****************************************

I'm a little confused. I came up with this algorithm, but I always get 2 for any value greater than or equal to 2.

public boolean tryHorizontal(int row , int col){
        if( row < 0 || row >= array[0].length-1)
            return false;
        else
            return true;
    }

    public boolean tryVertical(int row, int col){
        if( col < 0 || col >= 2 )
            return false;
        else
            return true;
    }

    public boolean tryRowCol(int row, int col){
        if(this.tryHorizontal(row, col) && this.tryVertical(row, col)){
            return true;
        }
        else
            return false;
    }

    public int findWays(int row, int col){
        int n = 0;
        if( !this.tryRowCol(row, col))
            return 0;
        else
            n =+ 1 + this.findWays(row+1, col+1);

        return n;
    }
+3
3

MxN. , , , 3xN.

, , . , , 3, . , .

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);
    }
}

:

    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;
        }
    }

.

//... omitted

AA<><>
VVAA<>
AAVV<>
VVAA<>
<>VVAA
<><>VV

//... omitted

6728

, 6728 OEIS A004003.

, :

, , - . !

. printBoard, ~ 13 8x8 . , , , .

!

3xN. , . ( , !), , ( , !).

3 , , - .

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 + "<>");
   }
}

3 , , .

+3

CSP ( ):

4 ( , ). . " ". - 3xN .

. , 4 . , ( , - - ).

- EDIT-- , N , , .

+2

:

, , : .

- , , , ( ).

, 2 3 * N/2, , , , sstate ( , ).

In many states there will be more than one field that allows only two possibilities; with a smart strategy for choosing the next field, you can make sure that you will never find the same solution in two different ways, so you donโ€™t even need to check solutions for duplicates.

The state of the board should record which fields are free and which fields are occupied, but also which fields are occupied by the same domino, so the array intcan do the trick.

0
source

Source: https://habr.com/ru/post/1742330/

More articles:


All Articles