Question

Niklaus Wirth introduced the software engineering concept of stepwise refinement through developing an ALGOL program for this problem. Donald Knuth’s paper on “Algorithm X” uses the dancing links technique (15[1])to quickly solve various tiling problems as well as this problem, which is a case of a generalized exact cover problem. Dijkstra’s “Notes on Structured Programming” ends by deriving a backtracking algorithm to solve this problem. This problem (15[1])has solutions for all positive integers n except 2 and 3, and when n is (*) 8, there are 92 solutions including rotations and reflections. The standard algorithm for this problem runs a depth-first search to place the namesake (10[1])objects one row at a time while avoiding reusing any diagonal. (10[1])For 10 points, name this problem of placing certain pieces on a chessboard so they don’t attack each other. ■END■

Back to tossups