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

Got it!

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

Prints:

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 回答