Algorithmic approach to real world problems - rook polynomials

Certain problems appear to be quite challenging, especially when the "input" is large enough so that the problem cannot be solved by a human in a reasonable time. But thankfully we have computers and algorithms. In this article I'll introduce rook polynomials, very simple algorithm that calculates them, and we'll solve a few real words problems.

^SOURCE

Defining the problem

Imagine a chessboard. Although there are a few pieces, we'll focus on rooks. Rooks can move through any number of squares in a straight line. We say that two rooks are attacking if they stand in one line (vertical or horizontal). We will be interested in counting the number of ways k rooks can be placed on n by m chessboard, so that none are attacking. Moreover, not every square will be allowed to use. If a square is not allowed to be used, we say it's forbidden. For example:

^SOURCE
is a correct placement of 8 non-attacking rooks on 8x8 board, where the middle 4 squares are forbidden. Example that ilustrates incorrect placement:

^SOURCE

Now we are ready to define rook polynomial Rb(x) of a n by m board b with some of its squares forbidden. It is just a polynomial of degree at most min(n,m), where k-th coefficient is a number of ways to place k non-attacking rooks on the board. Notice that there is one way to place zero rooks on any board, so 0-th coefficent of any Rb(x) is 1.

Towards an algorithmic solution

Take any allowed square, call it s. Notice that every placement which is of our interest either has a rook ats or it doesn't. When it doesn't use s, then the board is equivalent to one with s forbidden. When it does, in none of squares in the same row and column as s other rook can be placed. We have just proved following theorem:

Theorem: Let b be a n by m chessboard. Let s be any allowed square. Let c be a board obtained from b by making s forbidden, and d be a board obtained from b by removing column and row of s. Then Rb(x)=Rc(x)+x·Rd(x).

This simple theorem gives us a way to algorithmically calculate any rook polynomial. Let's move to implementation.

Implementing the algorithm

We'll use Haskell. Why Haskell? You might not like this language, but it makes implementing such a recursive problem trivial.

What data structure to use?

A first thought would be a matrix, with 'X' when a square is forbidden, and 'O' when a square is allowed. However, as we are only interested in allowed squares, a more wise data structure would just be a list of their indices. So for a board:

X O X O
X X O X
X X X X

our representation will be:

[(0,1), (0,3), (1,2)]

To represent polynomial we'll just use a list.

Removing row and column

In the theorem, we consider board d obtained from b by removing row and column containing s. So we need a function that does that:

removeRowAndColumn :: (Int, Int) -> [(Int, Int)] -> [(Int, Int)]
removeRowAndColumn (x, y) = filter (\(i, j) -> i /= x && j /= y)

Nothing interesting happens here, we just pass x and y (position) of s and a list of allowed squares to the function, and it returns a list of allowed squares without column and row of s

Calculate rook polynomial

Let's jump straight into code and then analyse what's going on:

calculateRookPolynomial :: [(Int, Int)] -> [Int]
calculateRookPolynomial [] = [1] 
calculateRookPolynomial (s:c) = addPolynomials (calculateRookPolynomial c) (0 : (calculateRookPolynomial d))
   where d = removeRowAndColumn s c

addPolynomials :: [Int] -> [Int] -> [Int]
addPolynomials a b = go a b []
   where 
      go [] [] current = current
      go xs [] current = current ++ xs
      go [] ys current = current ++ ys 
      go (x:xs) (y:ys) current = go xs ys (current ++ [x+y])

The base case for this recursion is empty list, so a situation, when there are no allowed squares. As we observed at the beginning, a rook polynomial for such a board is 1. For a recursive step, we use the theorem: (s:c) decomposes list into the square s and the rest of list c. Then we recursively calculate the rook polynomial for c and for d, where d is the board without column and row of s. Next, we multiply the rook polynomial of d by x, which in our representation of polynomials is equivalent to appending 0 at the beginning of the list. At the end, we add these polynomials.

This simple and elegant code computes a rook polynomial of any chessboard. Nice, isn't it? I guess it's time to solve some problems!

Assigning employees to jobs

Suppose we have 5 employees (E0, ..., E4), and 7 jobs (J0, ..., J6). How many ways are there to assign a job to each employee such that no two jobs are assigned to one employee and no two employees are assigned to one job?

Suppose employees don't have any preferences (every employee can do every job). This situation clearly corresponds to a 5 by 7 board, where each row is one employee and each column is a job:

O O O O O O O
O O O O O O O
O O O O O O O
O O O O O O O
O O O O O O O

what in our representation is:

[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(1,0),(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(2,0),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(3,0),(3,1),(3,2),(3,3),(3,4),(3,5),(3,6),(4,0),(4,1),(4,2),(4,3),(4,4),(4,5),(4,6)]

Let's use it in our algorithm! The output is the following list (polynomial):

[1,35,420,2100,4200,2520]

What does it say? Well, we are interested in the 5th coefficient, which is 2520. There is 2520 ways to place 5 non-attacking rooks on this board, so there is 2520 ways to assign jobs to employees as we wanted.

Now let's do something more interesting. Suppose that employee E0 doesn't want to to job J3; E1 doesn't want to do jobs J0, J1, J6; E3 doesn't want to do jobs J1, J3; and E4 doesn't want to do job J0. This situation is more complicated, but not for our algorithm. We just change the board into:

O O O X O O O
X X O O O O X
O O O O O O O
O X O X O O O
X O O O O O O

in our representation:

[(0,0),(0,1),(0,2),(0,4),(0,5),(0,6),(1,2),(1,3),(1,4),(1,5),(2,0),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(3,0),(3,2),(3,4),(3,5),(3,6),(4,1),(4,2),(4,3),(4,4),(4,5),(4,6)]

Now the output is:

[1,28,266,1042,1617,747]

so there are 747 ways to assign jobs this time.

Let's eliminate even more squares, consider this board:

X X O X X O X
X X O X X O X
X O X X X X X
O X O X X X X
X X O X X X X

in our representation:

[(0,2),(0,5),(1,2),(1,5),(2,1),(3,0),(3,2),(4,2)]

This time the output is:

[1,8,18,15,4]

Note that this list (polynomial) contains only 5 values, so the 5th coefficeint of this rook polynomial is 0! Thus there is no way to assign jobs to employees as we want when E0 only wants to do J2 and J5, E1 wants J2 and J5, E2 wants J1, E3 wants J0 and J2, E4 wants J2.

Exercise

This is for those who want to check their understanding of the topic and Haskell.

Imagine you are on SteemFest. You with 5 other Steemians go to a 40's-like restaurant, where you have to leave your phone in the entrance. It turns out that you'll get your phones back, but each one of you will get a random one. What is a probability that none of you will get his own phone? Use rook polynomial to solve that, and share your solution in comments :)

Conclusion

Turns out that problems that seems challenging at first can be easly solved, making a simple observation, as we did in the theorem. We managed to implement the algorithm, and test it on "real world" problems.

Further reading

1. Wikipedia
2. gvsu.edu