Mathematics Homework Help

In lecture, I presented a way to approach the knight’s total domination problem.

Suppose we want every square on a square chess board to be attacked.

If we use a queen and a bishop, what is the minimum number of knights that are needed?

For example, for a 6×6 board, we might need a queen, a bishop, and three knights to
totally dominate the board. (I just made this number up.)

Design an LP that will solve this problem for any board size (2×2 or larger).

Use lpsolve to solve the problem for boards of all sizes up to some bound determined by
the amount of time it takes to solve. The largest board you report will take you at least
10 minutes of computing time (i.e., you need to keep increasing the board size and solving
the problem until it takes your computer more than 10 minutes to solve).

Report your computation times in your writing.

You will need to explain your LP carefully, giving clear reasons for its variables,
constraints and objective function. Express your LP using proper mathematical notation.

You will need to write code that generates the lpsolve input files.

The code and the input files, and the output from lpsolve need to be included.

However, just present the input and output files for one size board.

Summarize your results in tables. For example, each row could have board size,
number of knights needed, and time to compute.

Feel free to draw figures illustrating your solutions: where should the pieces
be placed on the board to achieve total domination?

Be sure to check that your solutions are solutions by drawing the board with
the pieces located the way your solution said they should be: do these pieces achieve
total domination?

Useful links:

https://en.wikipedia.org/wiki/Mathematical_chess_p…
https://en.wikipedia.org/wiki/Chess#Movement