lotus

previous page: 111 competition/games/chess/queen.most.p
  
page up: Puzzles FAQ
  
next page: 113 competition/games/chess/rook.paths.p

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:













TOP
previous page: 111 competition/games/chess/queen.most.p
  
page up: Puzzles FAQ
  
next page: 113 competition/games/chess/rook.paths.p