Rook Polynomials and Chess

Rook Polynomials and Chess Introduction Chess is a complex strategical board game. The board on which the game is played is an eight by eight grid. Each player begins the game with 16 pieces: eight pawns, two knights, two bishops , two rooks, one queen, and a single king. Each of the six piece types move differently, and each are able to attack, or remove a certain piece, in different directions. The objective of chess is to checkmate the opposing king by placing ones own pieces around the king where it is being attacked no matter what action it takes.. While chess is primarily a recreational activity, the complexity of the movement of the pieces has resulted in it having significant mathematical properties. Chess analysis is complicated because of the multitude of movement options open to both players at every single move. Many mathematical chess problems involve discovering how specific placement of pieces can result in none of the pieces attacking each other, I.e. None of the pieces are within the same line of sight. One particular variation of these problems is the rook polynomial. The rook piece is able to move horizontally or vertically up to a max of eight squares. In combinatorial mathematics, a rook polynomial generates the combinations of non-attacking rooks; no two rooks are in the same row or column. A board is any layout of squares of a rectangular board with (y) rows and (z) columns. While there are, numerous formulas determining rook placement for rook polynomials, this investigation will look into the method of classifying all quadratic polynomials which are the rook polynomial for some generalized board G. Rook Movement and Application As stated, in chess, rooks are able to attack   any square in its line of sight,( i.e. its row or column)   exhibited below If a rook were to fall in the line of sight of another rook, they would be attacking. Rook polynomials focus on nonattacking rooks. The board of a rook polynomial is defined as a square n x n chessboard, but can also include any subset of a board. For instance, on a 2 x 3 chess board, or an L shaped chessboard would be subset of a regular board. To denote the patterns in which multiple nonattacking rooks can be placed on a generalized board, the variable S can represent the ways to place a number of non-attacking rooks. R will represent the rook, and (G) the size of the generalized board, creating the formula rs(G). rs(G) will be stated as rs when the size of the board (G) as the size of the board will be apparent. For all boards, r0 will always be equal to one, because it is impossible to set 0 rooks in differing combinations. R1 will always be the number of squares on the board because rook can be placed anywhere as no other rooks are on the board to attack. Rs = 0 when k is greate r than the number of rows or columns on the board, as there will be no way to place all the nonattacking rooks. The following generalized board provides an example of the equation: According to our determined parameters, for this particular subset r0 would again be equal to 1, and r1 would be equal to the number of squares, in this case six. For r2 there are 8 ways to place 2 non attacking rooks, demonstrated below. x x x x x x x x x X X x x x x x Three rooks placed on the board only allow for 3 different non-attacking combinations, meaning r3 equals 3 x x X X x X X x x Since there are only 3 rows for this particular generalized board any rs>3 as being equal to 0. Using this general principle it is possible to create a polynomial that tracks all of the potential rook combinations on a generalized board. The rss would be the coefficients of xs, resulting in the formula: r0 + r1x + r2x2 + à ¢Ã¢â€š ¬Ã‚ ¦+rs-1xs-1+ rsxk The rook placement numbers from the previous generalized board: r0 = 1, r1 = 6, r2 = 8, r3 = 3, r4 = 0, r5, r6,à ¢Ã¢â€š ¬Ã‚ ¦ = 0 Resulting in the following polynomial: 1+ 6x + 8x2 + 3x3 However it is important to understand that rook polynomials are not unique to a single generalized board. Any board with a similar 3 column lay out would have the same polynomial formula. This leads to the purpose of this mathematics investigation which is to classify all quadratic polynomials which are the rook combinations for a generalized board G. Determining the Quadratic Polynomial Since r0= 1 will always be true, and   r1 = number of squares of (g) the root of the quadratic is: 1 + r1x + r2x2 r1 is determined by board size, therefore it is necessary to discover any r2s where r3 is equal to 0.   If r3 is greater than zero, the rook polynomial could potentially be a cubic, or even quartic. As demonstrated in the previous example, generalized boards with 3 rows will result in polynomials where r4=0 When examining the requirements of r4 = 0, the generalized board must contain two rows of a board and contain squares that are consecutive in each row. As determined preciously, r1 is equal to the number of squares on the generalized board. With that information, we can summarize each row of the board as variables (y) and (z). In this case r1= y+z. With this methodology, (y) and (z) will be placed in a way that the spaces in row (y) are consecutive, and (z) squares are consecutive in the next row. Another important aspect is the number of columns created by (y) and (z). The overlap of the rows will be labeled (p). Using the number of squares in the example, consider r1 to be equal to 12. The possible pairs for (y) and (z) are: 1,11; 2,10; 3,9; 4,8; 5,7; 6,6 To create a formula outlining all the potential quadratic equations of a rook polynomial, any of these numbered pairs will work. In the case of 4,8, if none of the rows overlapped, r2 would be equal to 48. To determine r2 when squares are overlapping, it is necessary to multiply the number of squares in row (y) which are not overlapping by (z), and that to the product of the number of squares overlapping between the two of them and the number of squares not overlapping in row (z). Each square overlap should reduce r2 by 1. To demonstrate: 28+27 18+37 47 If a closer look is taken at each of these equations, it is possible to expand it to and relabel the numbers with variables to create a formula. To demonstrate (38) + (17) = (4-1)8 + 1(8-1) (28) + (27) = (4-2)8 + 2(8-1) (18) + (37) = (4-3)8 +3(8-1) The numerals in these expanded equations can be replaced to reform the formula: r2= (y-i)(z) + (p)(z-1) Simplifying into r2 = yz -pz + pz -   p r2 = yz -p We can insert this equation into the rook polynomial already established to create a formula which can calculate all potential rook polynomial combinations. For example if a generalized board contains row (y) with 6 squares, and row (z) contains 9 squares, with an overlap of p=4, the quadratic polynomial would appear as: 1+(y+z)x +(yz-p)x2 1+(6+9)x +((69)-4)x2 1+15x +((54)-4)x2 1+ 15x + 50x2 Therefore the formula to calculate all potential rook polynomial combinations is 1 + (y+z)x + (yz-p)x2 Discussion and Conclusion Rook polynomials, despite appearing as only a theoretical chess puzzle, actually have a number of practical applications. Various organization problems and layouts can be modeled by the rook problem by equating the objects involved to acting as rooks. A practical application stems from company scheduling. Management may require a specifc number of employees to work their jobs at specific times. However there maybe scheduling issues to ensure no two workers are performing the same job at the same time. A rook polynomial calculation could give insight into the number of combinations of how the workers could be scheduled. The number of workers could represent row (z), and the times available row (y). Each worker must be be at the job and only one time, which is similar to the concept of a rook being at a specific spot that is not attacking any other rook. Depending on the overlap of times and workers available schedule, the formula produce in this investigation could be used to determin e the number of combinations. Another example is if a company desires to hire a certain (y)number of employees on a number (z) different jobs. Each job can only be held by only one employee. By putting both employee number and job number on the rows of a generalized chessboard chessboard, the result is similar to that of a rooks dilemma. When worker A is appointed to job B, it is like a rook is placed on the square where row (y)overlaps row (z). Every occupation will be performed by a single worker, and every worker is assigned to a single job. Therefore all rows and columns in the pattern will contain only one rook, signifying that the rooks will not be attacking one another. The rook polynomial formula could be used to calculate the number of ways the assignments can be executed. However, the investigation in creating a quadratic rook polynomial formula did have limitations. I was unable to expand the formula to examine greater sized generalized boards, requiring that it not reach cubic or quartic levels. I had initially attempted this, but found that I could not find a generalized rule for each and every combination of a generalized board. For this reason, the application to general life problems is limited. My process could have been improved by investigating further into complex rook polynomials such as the Lagueree polynomial.   Ultimately the complexity of chess allow for both simple and complex mathematical analysis, which can produce formulas which have real life application. Having chess as a visual and interactive tool to explore various concepts of math was a helpful resource when performing this investigation. Not only this, but my own enthusiasm for playing chess and studying the intricacies of the math behind the pieces pushed me to write the investigation.