Ascension problem pack

Although metaheuristics can be applied to practical problems, I normally use them to tackle the problems that are abstract in nature. Thanks to their generality, metaheuristics can be great tools for experimental mathematics. Today's Ascension update introduces five new problem definition modules, all of them related to certain integer sequences. Here is a quick overview of all the problems available right now:

N Queens

Place N queens on an N x N board so that no two queens attack each other. This problem is easily solved by all metaheuristics even if N is several thousands. It serves mostly as an example of how to create a problem definition.

3D N Queens (A068940, unsolved)

Place the maximal number of queens on an N x N x N board so that now two queens attack each other. In addition to the regular diagonals, 3D queens also attack along the spatial ones. Perfect solutions with N^2 queens only exist for certain values of N (it is conjectured that the smallest factor of N must be greater than 7). This problem is much harder than its 2D counterpart. 11 x 11 x 11 board, 121 queens:

Queen domination (A075458, unsolved)

Place the smallest number of queens on an N x N board so that every square is attacked or occupied. 9 queens dominating the 16 x 16 board:

Knight covering (A006075, unsolved)

Same as the queen domination, but with knights. This problem can give rise to beautiful configurations. 40 knights covering a 16 x 16 board:

Queen nondomination (A001366, unsolved)

Place N queens on an N x N board so as to maximize the number of unattacked vacant squares. Unique optimum for N = 16:

Peaceable queens (A250000, unsolved)

Place the maximal number of white and black queens on an N x N board so that no two queens of opposite colors attack each other. Numberphile recently did a video about the problem. 84 white and black peaceable queens on a 24 x 24 board:

Maximal density still life (A055397)

Find an N x N pattern with the largest number of live cells that stays still under the rules of Conway's game of life. Although this problem has been solved, it is a good test for various metaheuristics. Solutions typically look like this:

Maximal density subsquare-free arrangements (A227133, A240443, unsolved)

Given an N x N grid, mark the largest number of cells such that no four marked cells belong to the corners of a square. A variant of this problem only counts the axis-parallel squares. Best known solutions were obtained with Ascension. 16 x 16, 106 marked cells:

2D HP protein folding model

Given a sequence of H and P aminoacids, find the folding (a self-avoiding walk on a grid) that maximizes the number of H-H contacts. Even though this model is oversimplified, it makes for a difficult problem. Here is an example of an optimal folding:


Tier Benefits
Recent Posts