With Bit manipulation the N Queens problem runs quite faster than the trivial method of solving N Queens where we always have to check whether the queen can be placed in the current cell (defined as

I ran N Queens for N = 14 and it took less than

The

`place(row, col)`

say), & this checking is also not made in constant time! But using Bit manipulation we are only traversing through the cells where a queen can be placed!! i.e. we are not only removing the cost for `place(row, col)`

but also we are completely ignoring the cells where a queen cannot be placed.
I ran N Queens for N = 14 and it took less than

**1s**to run. While trivial method of cost O(N!) took**> 15s**import java.util.Arrays; class NQueens { static int N, count; static int[] column; public static void main (String[] args) { N = 5; column = new int[N]; nQueens(0, 0, 0, 0); System.out.println(count); } private static void nQueens(int row, int ltDiag, int rtDiag, int down) { if (row == N) { System.out.println(Arrays.toString(column)); count++; return; } int mask = ltDiag | rtDiag | down; while (mask < (1 << N) - 1) { int col = ~mask & mask + 1; // gets rightmost 0-bit column[row] = Integer.numberOfTrailingZeros(col); int lD = (ltDiag | col) >> 1; int rD = (rtDiag | col) << 1 & (1 << N) - 1; nQueens(row + 1, lD, rD, down | col); mask |= col; } } }

**Output**[0, 2, 4, 1, 3] [0, 3, 1, 4, 2] [1, 3, 0, 2, 4] [1, 4, 2, 0, 3] [2, 0, 3, 1, 4] [2, 4, 1, 3, 0] [3, 0, 2, 4, 1] [3, 1, 4, 2, 0] [4, 1, 3, 0, 2] [4, 2, 0, 3, 1] 10

`column[]`

contains the solution, where `column[i]`

gives where in the i^{th}row the Queen will be placed (Zero based indexing)

## No comments:

## Post a Comment