The crippled Queen placement problem (Q1060835): Difference between revisions

In designing an algorithm and a computer program for the solution of a nontrivial problem, a number of alternative mathematical approaches are often possible. If the resulting computer program is constructed in a hierarchical fashion, from the highest level of abstraction to the lowest, similar discrete choices of algorithms occur at each level of refinement. In the current paper, the authors attempt to document the effects of making such choices, as a function of the level of abstraction at which choices occur, for one such nontrivial problem. The problem is presented in the form of an abstract, simple input and output specification: Gien an n by m chess-board, calculate the maximum number of ''Crippled Queens'' (CQs) which can be placed on that chess- board, in such a way that no CQ can attack another. Print this number, N(n,m), and also C(n,m) \(=\) the number of ways N(n,m)CQs can be so placed. A CQ is a chess queen which can attack squares at most two away from its location, along any row, column, or diagonal of the chess-board. Presented in this form, the problem is seen as a generalization of the famous Eight Queens problem presented by Nauck (1850). Several independently-designed programs which solve the problem were obtained from a class of computer science graduate students, most of which solved the problem by exhaustively enumerating all solution-configurations of CQs, using recursive methods similar to those used to solve the Eight Queens problem. However, further study of the mathematical structure of the CQ problem produced classes of solutions with significantly better characteristics as computer programs, along all the dimensions on which computer programs are usually judged. That is, these solutions executed more rapidly, and were simpler and more easily debugged, than were the exhaustive enumeration methods. One class of improved solutions originated in the idea that preprocessing a single column of a chess-board could result in an exhaustive list of all the solutions which were valid for a single column. Various branch- and-bound solutions based on choosing the solution for an entire column at a time proved superior to those solutions which chose to place one CQ at each recursion level. From these column-at-a-time recursive solutions, a much faster approach to the enumeration, based on dynamic programming, emerged. Finally, the presence of comparatively fast computer programs for solving this problem allowed exploration of cases with fairly large values of n and m. Study of these cases led to the discovery of many solutions with the same values for C(n,m), independent of n and m. In turn, this led to the speculation, later proved correct, that C(n,m) could be calculated by a closed formula, without enumerating solutions, either implicitly (using dynamic programming) or explicitly. This discovery, and attempts to prove it correct, led also to similar closed- form solutions for N(n,m) and C(n,m) for all large values of n and m. The data collected is organized by the level of abstraction at which a given choice was made. Choices at the highest level considered, the overall mathematical structure being analyzed, resulted in a great deal of program improvement. On the other hand, choices of data structures, within any one general solution approach such as that of dynamic programming led to considerably smaller improvements. In one such case, an elaborate data structure reduced run-time by about a factor of 2, while increasing the complexity of the program text by a factor nearly 3. Debugging time was found to be a linear function of the textual length, in this case.