No label defined (Q4464798)

The puzzle of placing eight queens on a chessboard so that no queen attacks another is an old and pleasant one, with relevance to finite geometry and design theory. A trivial ``pigeonhole'' argument shows that nine queens (or even rooks) cannot be so placed. However, 32 knights may be so placed (on every black square; every square attacked is of course white!). This family of problems may be generalized to boards of other sizes and shapes, and translates naturally into graph theory: given a graph whose vertices are the squares and whose edges are lines of attack, find a maximum independent set (or its size, the independence number of the graph). Here, the authors consider triangular boards of hexagonal cells. Of course, chess pieces must undergo a certain amount of reinvention, some more than others. The rook's move on a honeycomb is fairly unambiguous. Other pieces are harder to convert: in particular, there are several claimants to the role of honeycomb knight. The independence numbers for several of these pieces (king, rook, one knight variant, and a piece that moves only to adjacent squares) have already been determined. Here, the authors obtain exact independence numbers for three more knight variations. For the bishop and queen, they obtain exact independence numbers for some board sizes and bounds for the rest.