How many dragons (rook plus king) and how many horses (bishop plus king) can be placed on a 9x9 Shogi board...
competition/games/chess/shogi.pieces New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
How many dragons (rook plus king) and how many horses (bishop plus king) can be placed on a 9x9 Shogi board without attacking each other? How many dragons (combined rook/king) can be placed? How many horses (combined bishop/king)? Also: 32 knights can be placed on a chessboard without conflict, simply by placing them on all the white squares (or all the black squares). Prove that this solution is maximal, i.e., it is not possible to place more than 32 knights without conflict. [ Editor: problem statement reconstructed from the postings. Jonathan Haas <positron@Starbase.NeoSoft.COM> gave the 32-knight placement and asked the Shogi questions; David Karr added the request for a proof. ]
Show solution
Nine dragons. As a rook, each dragon uses up a file, so the answer is at most 9. In fact the answer is exactly 9: since each dragon attacks a subset of the squares that a queen would attack, use a solution for placing 9 queens on a 9x9 board, for example: . . . D . . . . . . . . . . D . . . . . . . . . . D . . D . . . . . . . . . . . . . D . . D . . . . . . . . . . D . . . . . . . . . . D . . . . . . . . . . . . D Fifteen horses. As a bishop, each horse uses up one of the 17 right diagonals. But there is a special problem in the corners because the two shortest diagonals in each corner (length 1 and 2) are completely covered by a single horse placed on any of the three squares. So we lump together these two diagonals in each corner, leaving 15 regions, in which we can place at most 15 horses. Here's how we place them: . H . H . H . H . . . . . . . . . . H . . . . . . . H . . . . . . . . . H . . . H . . . H . . . . . . . . . H . . . . . . . H . . . . . . . . . . H . H . H . H . -- David A. Karr <karr@cs.cornell.edu> [ Editor: no proof of the 32-knight bound was among the collected postings; see competition/games/chess/knight.most. ]