112 competition/games/chess/queens.p
Description
This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.
112 competition/games/chess/queens.p
How many ways can eight queens be placed so that they control the board?
competition/games/chess/queens.s
92. The following program uses a backtracking algorithm to count positions:
#include <stdio.h>
static int count = 0;
void try(int row, int left, int right) {
int poss, place;
if (row == 0xFF) ++count;
else {
poss = ~(row|left|right) & 0xFF;
while (poss != 0) {
place = poss & -poss;
try(row|place, (left|place)<<1, (right|place)>>1);
poss &= ~place;
}
}
}
void main() {
try(0,0,0);
printf("There are %d solutions.\n", count);
}
--
Tony Lezard IS tony@mantis.co.uk OR tony%mantis.co.uk@uknet.ac.uk
OR EVEN arl10@phx.cam.ac.uk if all else fails.
Continue to:
My Books
