CODEWITHSUNDEEP
javarecursiondynamic-programming
kasavbere
kasavbere

Reputation: 6003

how many ways can we place k rooks on a nxn chessboard safely

Given k rooks and a n by n chess board, the rooks can safely be placed on the board W different ways, where

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

PROBLEM STATEMENT:

Write a program that will run over a n by n chessboard and count all the ways that k rooks can safely be placed on the board.

MY RESEARCH:

After searching the internet I finally find a nQueensSolution code on Geekviewpoint and I modify it as below. However my code only works when k = n. Does anyone have an idea how to solve this for k<n?

Here is my code:

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

Here is a test code

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

Upvotes: 3

Views: 5026

Answers (2)

OldCurmudgeon
OldCurmudgeon

Reputation: 65821

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

Upvotes: 3

Tony Ennis
Tony Ennis

Reputation: 12299

I'd probably solve the problem a different way:

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

This solves the problem in the general case. 8 rooks, 5 rooks, doesn't matter. Because all the rooks are unique, note when we place a rook we don't have to start over at (0,0)

Edit here are some results:

Here's are results I get for 1 to 8 rooks:

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

Upvotes: 0

Related Questions