Department of Engineering

University of Cambridge >  Engineering Department >  computing help

Queens: recursion and bit arithmetic

This program counts the number of ways that 8 queens can be placed on a chess board without any 2 of them being on the same row, column or diagonal. It was written by M. Richards at cl.cam.ac.uk

#include <stdio.h>
int count;

void try(int row, int ld, int rd){

  if (row == 0xFF)
    count++;
  else{
    int poss = 0xFF & ~(row | ld | rd); 
    while (poss){
      int p = poss& -poss;
      poss = poss -p;
      try(row+p, (ld+p)<<1, (rd+p)>>1);
    }
  }
}

int main(int argc, char *argv[]){
  printf("Eight Queens\n");
  count = 0;
  try(0,0,0);
  printf("Number of solutions is %d\n", count);
  exit(0);
}