N-Queens

Background

The n-queens problem involves placing n queens on an n × n chessboard, where solutions exist for all natural numbers n with the exception of n=2 and n=3. [1]

Challenge

So, the challenge is to solve the n queen problem for up to 12 queens as efficiently as possible. The brute force algorithm must check every combination of queens until a solution is found. n will be provided either through a command line argument or user input.

The n queens problem is defined briefly as such:

Given an n × n chess board, place n queens on the board such that no queen can capture another. Queens can move in a straight line up, down, left, right or diagonally any number of spaces. A queen is said to be able to "capture" another queen if it can legally move to the space that another queen is occupying.

Implementation details are up to the programmer. The only restriction is that the program must reliably solve the problem every time the program is executed. The program should also print the board to the screen once a solution has been found. The letter X will represent empty spaces, and the letter Q will represent queens.

As an example, a solution to 4 queens would print as:

X X Q X
Q X X X
X X X Q
X Q X X