Search code examples
algorithmdata-structuresgraphheuristics

Why does the queen have only 10 unique positions in chessboards covering?


In the chessboards covering problem

The covering problem is that 1 king, 1 queen, 2 knights, 2 bishops, 2 rooks can threat the all 64 squares. Where should they be?

in order to reduce the search space, we can limit the queen's possible places to only 10.

Getting the job done would require significant pruning. Our first idea was to remove symmetries. Accounting for orthogonal and diagonal symmetries left only ten distinct positions for the queen, shown in Figure

Queen's possible places

Ok. I don't understand this.

Why queen's possible places can be limited like that?

Why symmetries can be considered for limiting queen's places? So in the above figure, queen being placed at the bottom left corner is the same as it being placed at the bottom right corner? Why is that?


Solution

  • In general, the symmetry is only valid for the first piece placed. Once a piece is placed on the board, you lose some or all of the symmetry: the board no longer looks the same when mirrored or rotated.

    The problem you post appears to assume that the queen is the first piece placed. For the specific problem, this makes sense, since the queen can cover more of the board than any other, so it may reduce the work required to place the remaining pieces. However, the symmetry aspect is similar for whatever piece you place first: only the first piece can take advantage of the full board symmetry.


    Note that, once the first piece is placed, there may still be some residual symmetry, that can save additional time. For instance, if the first piece is placed along the diagonal, you can still mirror along that diagonal. However, this residual symmetry would take more complex (and error-prone) code to take advantage of...