N queens problem

From Hamsterworks Wiki!

Jump to: navigation, search

If the local robotics club's email list goes quiet somebody usually starts a "Choc fish challenge".

This time it was the n queens problem - see http://en.wikipedia.org/wiki/Eight_queens_puzzle for full discussion of the problem.

Contents

First 15 minute hack

This was the initial attempt to solve the problem, solves only 8x8 boards

#include <stdio.h>
#define LOOP(i) for(i=0;i< 8;i++)
char x[8];

int o(int d) {
    LOOP(d) printf("%.8s\n","XXXXXXXQXXXXXXX"+7-x[d]);
    return putchar('\n');
}

void q(int d) {
  if(d == 8 && o(d)) return;
  LOOP(x[d]) {
    int i;
    LOOP(i)
      if(x[i]==x[d]||x[i]+i==x[d]+d||x[i]-i==x[d]-d) break;
    if(i == d) q(d+1);
  }
}

int main(int c, char *v[]) {
  LOOP(x[0]) q(1);
  return 1;
} 

Remove recursion

This next version removes recursion and with it all the local variables. It's much shorter, and once again it only works for 8x8 boards.

 
#include <stdio.h>
#define L(i) for(i=0;i< 8;i++)
int d,x[8],i[8];
int main(int c, char *v[]) {
 while(d != -1) {
  if(d==8) {
   L(d) printf("%.8s\n","XXXXXXXQXXXXXXX"+8-x[d]);
   putchar('\n');
   d--;
  } else if(x[d]<8) {
   x[d]++;
   L(i[d]) if(x[i[d]]==x[d]||x[i[d]]+i[d]==x[d]+d||x[i[d]]-i[d]==x[d]-d) break;
   if(i[d] == d) x[1+d++] = 0;
  } else d--;
 }
 return 0;
} 

Final generalised fast solution

The challenge then got extended to any NxN board, and a new approach is needed. I was thinking as I was relaxing in a bath, and this is what came to me... (wreaking a perfectly good bath, I might add)

Step 1

Build masks of if a queen is placed at (x), what moves are no longer valid on the board.


   0    1   ... 4 (if N = 5)
 -xxxx  x-xxx
 xx---  xxx--
 x-x--  -x-x-
 x--x-  -x--x
 x---x  -x---

Step 2

Solve the problem with a depth-first backtracker by merging the bitmaps offset by the depth search.

 procedure queens(depth)
 begin  
   if(depth - n-1)
   begin
      solutions++;
      return;
   end
   
   look at board(depth-1), row depth
 
   for each bit in that row that is not 'x'
   begin
      board(depth) = board(depth-1) ANDed mask(i), offset by depth rows.
      qeeens(depth+1);
   end 
 end
 
 Procedure main()
 For i = 0 to n-1
   copy mask(i) to board(0);
   queens(1)
 next i
 output number of solutions

It's speed comes because it only looks forward - the earlier solutions look back to see if the current move will conflict with earlier placed pieces. The bigger the board, the deeper you search the more looking back is required.

Here is the search for the first solution, n = 5.. '1' represents a playable square, '-' isn't, and 'Q' represents a placed queen:

Placing 0 at depth 0

Q----
--111
-1-11
-11-1
-111-

Placing 2 at depth 1

Q----
--Q--
----1
-1---
-1-1-

Placing 4 at depth 2

Q----
--Q--
----Q
-1---
-1-1-

Placing 1 at depth 3

Q----
--Q--
----Q
-Q---
---1-

Placing 3 at depth 4

Q----
--Q--
----Q
-Q---
---1-

Solution 1

Q----
--Q--
----Q
-Q---
---Q-

Source code

My first go at implementation worked well, but I've played around with the algorithm to make it more performance friendly and achieving a 50% speedup in the process.

Compile with -DSHOW if you want the solutions...

Board size Solutions Time
14 365596 0m0.847s
15 2279184 0m5.602s
16 14772512 0m38.122s
17 95815104 4m31
 #include <stdio.h>
 #include <stdlib.h>
 
 static unsigned masks[32][32];
 static unsigned progress[32][32];
 static int width;
 static int solutions;
 
 static void buildMasks(void)
 {
  int i;
  for(i = 0; i < 32; i++)
  {
    unsigned right,left,middle;
    int j;
    left=right=middle = (1<<i);
    /* Set mask 0 to have a hole on the chosen bit */
    masks[i][0] = middle;
    left  *=2;
    right /=2;
    for(j = 1; j < 32; j++)
    {
      masks[i][j] = ~(left|middle|right);
      masks[i][j] &= (1<<width)-1;
      left *=2;
      right/=2;
    }
  }
 } 
 
 static void solution(void)
 {
   if(progress[1][0] == 0)
     return;

    solutions++;
 #ifdef SHOW
    printf("Solution %i\n", solutions);
    for(i = 0; i < width; i++)
      printrow(progress[i][i]);
    putchar('\n');
 #endif
    return;
 }
 
 static void queens1(void)
 {
  int i;

  for(i = 0; i < width; i++)
  {
    if(progress[2][1] & (1<<i))
    {
      progress[1][0] = (progress[2][0] & masks[i][1]);
      if(progress[1][0] == 0) continue;
      progress[1][1] = masks[i][0];
      solution();
    }
  }
 }
 
 static void queens2(void)
 {
  int i;

  for(i = 0; i < width; i++)
  {
    if(progress[3][2] & (1<<i))
    {
      progress[2][1] = (progress[2+1][1] & masks[i][1]);
      if(progress[2][1] == 0) continue;
      progress[2][0] = (progress[2+1][0] & masks[i][2]);
      if(progress[2][0] == 0) continue;
      progress[2][2] = masks[i][0];
      queens1();
    }
  }
 }
 
 static void queens3(void)
 {
  int i;
  for(i = 0; i < width; i++)
  {
    if(progress[4][3] & (1<<i))
    {
      progress[3][2] = (progress[4][2] & masks[i][1]);
      if(progress[3][2] == 0) continue;
      progress[3][1] = (progress[4][1] & masks[i][2]);
      if(progress[3][1] == 0) continue;
      progress[3][0] = (progress[4][0] & masks[i][3]);
      if(progress[3][0] == 0) continue;
      progress[3][3] = masks[i][0];
      queens2();
    }
  }
 }
 
 static void queens4(void)
 {
  int i;

  for(i = 0; i < width; i++)
  {
    if(progress[5][4] & (1<<i))
    {
      progress[4][3] = (progress[5][3] & masks[i][1]);
      if(progress[4][3] == 0) continue;
      progress[4][2] = (progress[5][2] & masks[i][2]);
      if(progress[4][2] == 0) continue;
      progress[4][1] = (progress[5][1] & masks[i][3]);
      if(progress[4][1] == 0) continue;
      progress[4][0] = (progress[5][0] & masks[i][4]);
      if(progress[4][0] == 0) continue;
      progress[4][4] = masks[i][0];
      queens3();
    }
  }
 }

 void queens(int depth)
 {
  int i;

  for(i = 0; i < width; i++)
  {
    if(progress[depth+1][depth] & (1<<i))
    {
      int j,m;
      j = depth;
      m = 0;
      progress[depth][j--] = masks[i][m++];
      while(j >= 0)
      {
        progress[depth][j] = (progress[depth+1][j] & masks[i][m++]);
        if(progress[depth][j] == 0) break;
        j--;
      }
      if(j < 0)
      {
        if(depth != 5)
          queens(depth-1);
        else
          queens4();
      }
    }
  }
 }

 int main(int c, char *v[])
 {
  int i;
  int depth;
 
  if(c != 2 || (width = atoi(v[1])) < 1)
  {
    printf("usage : %s <size>\n",v[0]);
    return 0;
  }
  buildMasks();
  depth = width-1;
  for(i = 0; i < width; i++)
  {
    int j;
    for(j = 0; j < width; j++)
      progress[depth][depth-j] = masks[i][j];

    switch(depth)
    {
      case 0: break;
      case 1: solution(); break;
      case 2: queens1(); break;
      case 3: queens2(); break;
      case 4: queens3(); break;
      case 5: queens4(); break;
      default:
        queens(depth-1);
    }
  }
  printf("%i solutions found at %i\n",solutions,width);
  return 0;
 }

Personal tools