KNIght DOmination R ANnealing: a simulated annealing algorithm used to solve Knight Domination problems.

Written as a student at St. Mary’s College of Maryland. The following is an excerpt of the write-up we did for this program. This program, written in R, attempts to minimize the set of dominating knights for an NxN board. It uses a simulated annealing approach.

For an NxN board, minimizing the set of dominating knights is equivalent to minimizing the over-coverage(how much each spot on the board is “overcovered”: covered by more than one knight), and the spillage: how much possible coverage spills off the sides of the board (http://home.earthlink.net/~morgenstern/large/center.html).

As a board gets larger and larger - the amount that spilling contributes is minimal. Thus, we can find an NXN board with minimal coverage to get an estimate of the dominating set of knights for that board.

In order to produce a board with minimal overcoverage, we used simulated annealing, which essentially tells the computer whether to keep a knight assignment based on some heuristic function and a little bit of probability. Our heuristic function was minimal undercoverage - with large weights placed on any configurations with undercoverage (thus not being dominating sets) to avoid their being picked. As simulated annealing goes, a “bad” configuration will be kept at a probability which decreases each iteration according to a cooling function.

Our particular algorithm was divided into two parts. In the first part, we start with a board filled with knights, and in each iteration of the algorithm we remove a random knight from the board, picking knights which overcover more of the board. An example of how this part of our algorithm works is shown below on the left for a 20x20 board. We do this for a specified number of runs, and after approaching a point where removing knights more often produces undercoverage - we take the resulting board configuration and run it through our second part.

In our second part, during each iteration we generate a successor based on taking one knight and moving it to a random empty space on the board - the resulting board is kept based on the same heuristic and probability (cooling function) as the first part. This second part seems to fine tune our configuration. An example, which is shown below on the right - and begins with the last board configuration from the instance on the bottom left. For a 20x20 board, the smallest set of knights to dominate a board ere we were able to find was 80, which differs by 18 from the set described here(http://home.earthlink.net/~morgenstern/solution/intro.htm). Similar results were found for boards slightly larger, and slightly bigger than 20. After applying the second part, we can take the output again and feed it into an instance of our first part of our algorithm.