mask_of_madness's blog

By mask_of_madness, history, 4 years ago, In English

Problem — Given an n × n chessboard, our problem is to count the number of ways we can place two queens on the board in such a way that they do not attack each other

"To get a recursive solution, we may focus on the last row and last column of the n× n board (Fig. 3.4). First, if there are no queens on the last row or column, the number of combinations is simply q(n − 1). Then, there are 2n − 1 positions for a queen on the last row or column. It attacks 3(n − 1) squares, so there are n*n − 3(n − 1) − 1 positions for the other queen. Finally, there are (n − 1)(n − 2) combinations where both queens are on the last row or column. Since we counted those combinations twice, we have to remove this number from the result. By combining all this, we get a recursive formula q(n) = q(n − 1) + (2n − 1)(n*n − 3(n − 1) − 1) − (n − 1)(n − 2) = q(n − 1) + 2(n − 1)^2(n − 2), which provides an O(n) solution to the problem."

Sorry if this is a dumb question. I am having trouble understanding the last bit which talks about the case where there are two queens placed on the last row or column of the board ((n-1)(n-2)). Why do we have to remove this from the result? (Why can't it simply be q(n) = q(n − 1) + (2n − 1)(n*n − 3(n − 1) − 1)?)

Also, there's a follow up

"Finally, it turns out that there is also a closed-form formula q(n) = n^4/2 - 5n^3/3 + 3n^2/2 - n/3 which can be proved using induction and the recursive formula. Using this formula, we can solve the problem in O(1) time."

How does one go about finding the closed form formula given a recurrence relation?

  • Vote: I like it
  • +7
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Regarding the recurrence formula: if you place the 1st queen on the last row, with the formula $$$n*n − 3(n − 1) − 1$$$ you count all the position for the second queen, including the last column. However, if you place the 1st queen on the last column the formula will also count cases where the 2nd queen is placed on the last row. These cases are counted twice by $$$(2n − 1)(n*n − 3(n − 1) − 1))$$$. See example below:

##.

##Q

Q..

The closed form in this case can be obtained by unrolling the formula and stopping at q(0) = 0. You get a sum of the form $$$\sum_1^n a*k^3+b*k^2+c*k+d$$$. Sums like $$$\sum_1^n k^p$$$ have closed forms.