One of the more famous
chess puzzles, the eight queens puzzle asks that the solver place eight
queens on a chess board in such a way that none of them is under attack from any of the others. Excluding rotations and reflections, there are twelve different ways to do this.
Writing an efficient algorithm to solve the problem is an instructive exercise undertaken in many computer science courses, since it builds understanding of recursion and backtracking. Here's a rough sketch of a very bad algorithm which produces many duplicate answers, but illustrates the general idea:
solve(numqueens)
if no captures possible then
if numqueens = 8 then
output solution
else
for each unoccupied square
place queen on square
solve(numqueens+1)
remove queen
The puzzle generalises easily to other square boards, the 4x4 board being the smallest on which a solution exists.