Volume 9, Issue 2

Articles
In and Out
Trott's Corner
New Products
New Publications
Calendar
News Bulletins
New Resources
Classifieds

Editorial Policy
Staff
Submissions
Subscriptions
Back Issues
Contact Information

A Generator of Rook Polynomials

Code and Program Details

Here is the program for converting a list of nonrepeating (row, column) chessboard cells to a rook polynomial and its application to our small example.

When stacklist reaches {{{1}},{{x},...,{x}}} under While loop control, stacklist has reached its correct, final value. This is the only value that yields the rook polynomial directly. Also, Union[Flatten[stacklist]] equals {1,x} only for the final stacklist value.

SameColumnValues uses the pattern properties of the Position command to obtain a list of positions from the top of the stack that have the same column values as the leading (row, column) entry at the top of the stack list. SameRowValues does the same for the row values. Their Union gives the list of (row, column) EntriesToEliminate in forming the next inclusion chessboard, which is completed by appending x. The exclusion chessboard list is completed by deleting the first term from the top of the stack. After that, the inclusion and exclusion chessboard strings are appended to the bottom of the stack before the old top of the stack is discarded.

The lists move up (actually over to the left) and the next list becomes the new top of the stack. If not prevented, the program will try to process any stack tops that have leading x's. Accordingly, the top of a stack list consisting entirely of x's is moved to the bottom of the stack in the last While loop. When stacklist eventually meets the condition for shutting down the main While loop, the Apply line converts stacklist to the rook polynomial.

In this manner, RookPolynomial[{{row,column},...,{row,column}}] can be determined for any connected chessboard.