Teaching Kids Programming – Permutation of Rooks Do Not Attack Each Other

Teaching Kids Programming: Videos on Data Structures and Algorithms

You’ve got an integer n representing a chessboard of size n x n. Return the number of ways you can place n rooks, such that no two rooks attack each other.

Two ways are considered different if in one of the ways, some cell of the chessboard is occupied, and in the other way, the cell is not occupied.

Note: two rooks are attacking each other if they are either on the same row or on the same column.

Example 1
Input
n = 3
Output
6
Explanation
Here are the different chessboard configurations, where X is a rook.

X O O 
O X O
O O X

X O O 
O O X
O X O

O X O
X O O
O O X

O X O
O O X
X O O

O O X
O X O
X O O

O O X
X O O
O X O

number of ways of choosing n places for n items? as once we place a rook we ignore that row and column.
At first, We have n places to put the first rook, Soon we will have only n-1 for the second rook , Later we will have n-2 for the third rook and so on….

Permutation

The total number of ways to place N Rooks that do not attack each other on a NxN chessboard turns out to be a full permutation of N which is N! (factorial). We have N choices for first row, and (N-1) choices for the second row and so on.

Thus:

1
2
3
4
5
6

class Solution:
    def solve(self, n):
        ans = 1
        for i in range(2, n + 1):
            ans *= i
        return ans

class Solution:
    def solve(self, n):
        ans = 1
        for i in range(2, n + 1):
            ans *= i
        return ans

Or, we can do this recursively:

1
2
3
4
5
6
7

class Solution:
    def solve(self, n):
        def f(n):        
            if n == 1:
                return 1
            return n * f(n - 1)
        return f(n)

class Solution:
    def solve(self, n):
        def f(n):        
            if n == 1:
                return 1
            return n * f(n - 1)
        return f(n)

We don’t need to re-invent the wheel as the math.factorial does exactly the computation for us!

1
2
3

class Solution:
    def solve(self, n):
        return math.factorial(n)

class Solution:
    def solve(self, n):
        return math.factorial(n)

Time complexity is O(N) and space complexity is O(1).

See also: Teaching Kids Programming – Recursive Permutation Algorithm

–EOF (The Ultimate Computing & Technology Blog) —