Trouble understanding Two Queens Problem solution

Revision en1, by mask_of_madness, 2020-08-11 12:20:23

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?

Tags combinations, #recursion, #formula, chess board

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English mask_of_madness 2020-08-11 12:20:23 1669 Initial revision (published)