3

ルークkとチェス盤があれば、ルークはさまざまな方法でn by nボードに安全に配置できます。W

W = k!(n C k)^2
written differently W = n!n!/(k!(n-k)!(n-k)!)

問題文：

チェス盤の上で実行されるプログラムを作成し、ルークをボードに安全に配置できるn by nすべての方法を数えます。k

私の研究：

インターネットを検索した後、私はついにGeekviewpointnQueensSolutionでコードを見つけ、それを以下のように変更しました。ただし、私のコードは。誰かがこれを解決する方法を知っていますか？k = nk<n

これが私のコードです：

static int kRooksPermutations(int[] Q, int col, int k, int kLimit) {
    int count = 0;
    for (int x = 0; x < Q.length && col < Q.length; x++)
        if (safeToAdd(Q, x, col)) {
            if (k == kLimit - 1) {
                count++;
                Q[col] = -1;
            } else {
                Q[col] = x;
                count += kRooksPermutations(Q, col + 1, k + 1, kLimit);
            }
        }
    return count;
}//

static boolean safeToAdd(int[] Q, int r, int c) {
    for (int y = 0; y < c; y++)
        if (Q[y] == r)
            return false;
    return true;
}//

これがテストコードです

public static void main(String... strings) {
    kRooksPermutations(8,5);
}
4

2 に答える 2

3

とった！

  // Empty
  static final int MT = -1;

  static int kRooksPermutations(int[] Q, int col, int rooksInHand) {
    // Are we at the last col?
    if (col >= Q.length) {
      // If we've placed K rooks then its a good'n.
      return rooksInHand == 0 ? 1 : 0;
    }

    // Count at this level starts at 0
    int count = 0;
    // Have we run out of rooks?
    if (rooksInHand > 0) {
      // No! Try putting one in each row in this column.
      for (int row = 0; row < Q.length; row++) {
        // Can a rook be placed here?
        if (safeToAdd(Q, row, col)) {
          // Mark this spot occupied.
          Q[col] = row;
          // Recurse to the next column with one less rook.
          count += kRooksPermutations(Q, col + 1, rooksInHand - 1);
          // No longer occupied.
          Q[col] = MT;
        }
      }
    }
    // Also try NOT putting a rook in this column.
    count += kRooksPermutations(Q, col + 1, rooksInHand);

    return count;
  }

  static boolean safeToAdd(int[] Q, int row, int col) {
    // Unoccupied!
    if (Q[col] != MT) {
      return false;
    }
    // Do any columns have a rook in this row?
    // Could probably stop at col here rather than Q.length
    for (int c = 0; c < Q.length; c++) {
      if (Q[c] == row) {
        // Yes!
        return false;
      }
    }
    // All clear.
    return true;
  }

  // Main entry - Build the array and start it all going.
  private static void kRooksPermutations(int N, int K) {
    // One for each column of the board.
    // Contains the row number in which a rook is placed or -1 (MT) if the column is empty.
    final int[] Q = new int[N];
    // Start all empty.
    Arrays.fill(Q, MT);
    // Start at column 0 with no rooks placed.
    int perms = kRooksPermutations(Q, 0, K);
    // Print it.
    System.out.println("Perms for N = " + N + " K = " + K + " = " + perms);
  }

  public static void main(String[] args) {
    kRooksPermutations(8, 1);
    kRooksPermutations(8, 2);
    kRooksPermutations(8, 3);
    kRooksPermutations(8, 4);
    kRooksPermutations(8, 5);
    kRooksPermutations(8, 6);
    kRooksPermutations(8, 7);
    kRooksPermutations(8, 8);
  }

プリント：

Perms for N = 8 K = 1 = 64
Perms for N = 8 K = 2 = 1568
Perms for N = 8 K = 3 = 18816
Perms for N = 8 K = 4 = 117600
Perms for N = 8 K = 5 = 376320
Perms for N = 8 K = 6 = 564480
Perms for N = 8 K = 7 = 322560
Perms for N = 8 K = 8 = 40320
于 2012-04-24T01:18:03.233 に答える
0

私はおそらく別の方法で問題を解決するでしょう：

solutions = 0;
k = number_of_rooks;
recurse(0,k);
print solutions;
...

recurse(row, numberOfRooks) {
   if (numberOfRooks == 0) {
      ++solution;
      return;
      }
   for(i=row; i<n; i++) {
      for(j=0; j<n; j++) {
         if (rook_is_ok_at(i, j)) {
            place rook at i, j
            recurse(i+1, numberOfRooks-1)
            remove rook from i, j
         }
      }
   }
}

これにより、一般的な場合の問題が解決されます。8ルーク、5ルークは関係ありません。すべてのルークは一意であるため、ルークを配置するときに（0,0）からやり直す必要がないことに注意してください。

ここで編集してください：いくつかの結果：

これが私が1から8ルークで得た結果です：

For 1 rooks, there are 64 unique positions
For 2 rooks, there are 1568 unique positions
For 3 rooks, there are 18816 unique positions
For 4 rooks, there are 117600 unique positions
For 5 rooks, there are 376320 unique positions
For 6 rooks, there are 564480 unique positions
For 7 rooks, there are 322560 unique positions
For 8 rooks, there are 40320 unique positions
于 2012-04-23T23:37:19.783 に答える