Queen

Queen.cpp

#include <iostream>
#include <ctime>
using namespace std;

int solve(int board_size) {
  int total = 0;
  int res[18];
  int col[18];
  int pos[18];
  int neg[18];
  int stack[18];
  int p = 0;
  int lsb = 0;
  int bitfield=0;
  int board_minus = board_size - 1;
  int odd = board_size & 1;
  int mask = (1 << board_size) - 1;
  for (int i = 0; i < 1 + odd; ++i) {
    bitfield = 0;
    if (0 == i) {
      int half = board_size >> 1;
      bitfield = (1 << half) - 1;
      p = 0;

      res[0] = 0;
      col[0] = pos[0] = neg[0] = 0;
    } else {
      bitfield = 1 << (board_size >> 1);

      res[0] = bitfield;
      col[0] = pos[0] = neg[0] = 0;

      col[1] = bitfield;
      pos[1] = bitfield << 1;
      neg[1] = bitfield >> 1;
      stack[p] = 0;
      p += 1;
      bitfield = (bitfield - 1) >> 1;
    }

    for (;;) {
      lsb = bitfield ^ (bitfield & (bitfield - 1));
      if (0 == bitfield) {
        if (p == 0) break;
        bitfield = stack[p - 1];
        p -= 1;
        continue;
      }
      bitfield &= ~lsb;
      res[p] = lsb;
      if (p < board_minus) {
        col[p + 1] = col[p] | lsb;
        pos[p + 1] = (pos[p] | lsb) << 1;
        neg[p + 1] = (neg[p] | lsb) >> 1;
        stack[p] = bitfield;
        p += 1;
        bitfield = mask & ~(col[p] | pos[p] | neg[p]);
        continue;
      } else {
        total += 1;
        bitfield = stack[p - 1];
        p -= 1;
        continue;
      }
    }
  }

  return total * 2;
}

int main() {
    for(int i=12;i<17;++i){
    clock_t begin = clock();

    int total = solve(i);

    clock_t end = clock();
    double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
    cout<<"-----"<<i<<"-----"<<endl;
    cout<<"total : "<<total<<endl;
    cout<<"time  : "<<elapsed_secs<<"s"<<endl;
    }
    return 0;
}

//-----12-----
//total : 14200
//time  : 0.00666s
//-----13-----
//total : 73712
//time  : 0.020162s
//-----14-----
//total : 365596
//time  : 0.099816s
//-----15-----
//total : 2279184
//time  : 0.630011s
//-----16-----
//total : 14772512
//time  : 4.19015s

Queen.py

class Queen:
    def __init__(self, number_of_queens):
        self.N = number_of_queens

    def valid(self, choice):
        return self.valid_diagonals(choice, lambda x, y: y - x + self.N - 1) \
               and \
               self.valid_diagonals(choice, lambda x, y: x + y)

    def valid_diagonals(self, choice, index_callback):
        diagonals = [False] * (2 * self.N - 1)
        for row in range(self.N):
            col = choice[row]

            index = index_callback(col, row)
            if diagonals[index]:
                return False
            else:
                diagonals[index] = True
        return True

class BitQueen:
    @staticmethod
    def solve(board_size):
        total = 0
        res = [0] * board_size
        col = [0] * board_size
        pos = [0] * board_size
        neg = [0] * board_size
        stack = [0] * board_size
        p=lsb=bitfield= 0
        board_minus = board_size - 1
        odd = board_size & 1
        mask = (1 << board_size) - 1
        for i in range(1+odd):
            bitfield=0
            if 0 == i:
                half = board_size >> 1
                bitfield = (1<<half)-1
                p=0

                res[0]=0
                col[0]=pos[0]=neg[0]=0
            else:
                bitfield=1<<(board_size >> 1)

                res[0]=bitfield
                col[0]=pos[0]=neg[0]=0

                col[1]=bitfield
                pos[1]=bitfield<<1
                neg[1]=bitfield>>1
                stack[p]=0
                p+=1
                bitfield=(bitfield-1)>>1

            while True:
                lsb=bitfield^(bitfield&(bitfield-1))
                if 0 == bitfield:
                    if p == 0:
                        break
                    bitfield=stack[p-1]
                    p-=1
                    continue
                bitfield&=~lsb
                res[p] = lsb
                if p<board_minus:
                    col[p+1]=col[p]|lsb
                    pos[p+1]=(pos[p]|lsb)<<1
                    neg[p+1]=(neg[p]|lsb)>>1
                    stack[p]=bitfield
                    p+=1
                    bitfield=mask&~(col[p]|pos[p]|neg[p])
                    continue
                else:
                    total+=1
                    bitfield = stack[p-1]
                    p-=1
                    continue
        return total*2

if __name__ == '__main__':
    import time
    from itertools import permutations

    for n in range(2, 18):
        cnt = 0
        start = time.time()
        ## version 1
        # queen = Queen(n)
        # for choice in permutations(range(queen.N)):
        #     if queen.valid(choice):
        #         # print(choice)
        #         cnt += 1

        ##version 2
        queen = BitQueen
        cnt=queen.solve(n)

        print('----- %d -----' % n)
        print('total : %d' % cnt)
        print('time  : %.3fs' % (time.time() - start))