Amzi! Support

[Chip Eastham]

Recently this link was posted on the sci.math newsgroup:

http://people.moreheadstate.edu/fs/d.chatham/n+kqueens.html

It discusses an interesting generalization of the N Queens problem that is often the subject of Prolog programming examples.

In the usual problem one is asked to place (on an NxN chessboard) N Queens, chess pieces that "attack" in eight directions (vertical, horizontal, and diagonal), so that no piece attacks another.

The generalized problem asks how many could be so placed if we are also allowed to remove a limited number of squares from the chessboard, e.g. removing one square could be represented by placing a Pawn on that square to "block" attacks between Queens.

As in the usual problem, where N Queens are a maximum on an NxN board, it is clear by counting columns that at least k missing squares (or Pawns) are needed to allow N+k Queens.

regards, chip

[Chip Eastham]

It is not possible to place 5+1 Queens on a 5x5 board with one missing square (equivalent to blocking with one Pawn), but the 6+1 Queens problem is feasible (7 Queens & and a Pawn on a 6x6 board, with no Queen attacking another).

Some heuristics for placing the Pawn: It has to separate a pair of Queens on both its rank and its file (row and column of the board), so the Pawn must be placed on an interior square (not at an edge of the board). Symmetries limit the possible positions of the Pawn to a tiny number of squares, and once it is placed the locations of four Queens (two in the same row and two in the same column as the Pawn) are tightly constrained.

Another consideration for placing the Pawn first is that it makes it simpler to write a predicate that checks whether a pair of Queens attack one another, since the Pawn's location will be "known" by that time.

regards, chip