8queens

8queens.c

#include <stdio.h>
#include <stdint.h>

int columns[8] = {-1,-1,-1,-1,-1,-1,-1,-1};
int num_solutions = 0;

void print_queens() {
  for(int y = 0; y < 8; y++) {
    for(int x = 0; x < 8; x++) {
      putchar(columns[x] == y ? 'Q' : '.');
    }
    putchar('\n');
  }
  putchar('\n');
}

// recursively process columns, with backtracking
void find_solutions(int col, uint8_t rows, uint16_t diags_up_down, uint16_t diags_down_up) {

  if(col == 8) {
    print_queens();
    num_solutions++;
    return;
  } else {

    // use a temporary copy of rows for checking/removing candidate row bits
    uint8_t rows_to_process = rows;

    
    while(rows_to_process) {
      // find first remaining row (set bits == empty, because gcc has ffs and not ffz)
      int row = __builtin_ffs(rows_to_process)-1;    

      // get diagonal indexes for row and column
      int diags_up_down_bit = 7 + col - row;
      int diags_down_up_bit = 7 + row - (7 - col);

      // check if either diagonal was already taken by a previous column
      if((diags_up_down & (1 << diags_up_down_bit)) == 0 ||
	 (diags_down_up & (1 << diags_down_up_bit)) == 0 ) {
	goto next_row;
      }

      // clear selected diagonal and row (removing the candidate bits) 

      rows &= ~(1 << row);
      diags_up_down &= ~(1 << diags_up_down_bit);
      diags_down_up &= ~(1 << diags_down_up_bit);

      // set the row for drawing this column
      columns[col] = row;

      // recursively solve for next column and with updated rows/diagonals
      find_solutions(col+1, rows, diags_up_down, diags_down_up);
      
      // unset the row for drawing this column
      columns[col] = -1;
      
      // set selected diagonal and row (restoring the candidate bits)
      rows |= (1 << row);
      diags_up_down |= (1 << diags_up_down_bit);
      diags_down_up |= (1 << diags_down_up_bit);


    next_row:;
      // remove the row we just processed 
      rows_to_process &= ~(1 << row);
      
    }
    return;
  }
}



int main() {
  
  uint8_t rows = 0b11111111;
  // 15 diagonals in each direction (down-left/up-right and up-left/down-right)
  uint16_t diag_initial = 0b111111111111111;
  
  find_solutions(0, rows, diag_initial, diag_initial);
  printf("Found %i solutions\n", num_solutions);
  
  return 0;
}