# Algorithm Implementation/Miscellaneous/N-Queens

The eight queens puzzle is the problem of putting eight chess queens on an 8×8 chessboard such that none of them is able to capture any other using the standard chess queen's moves. The queens must be placed in such a way that no two queens would be able to attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens puzzle of placing n queens on an n×n chessboard, where solutions exist only for n = 1 or n ≥ 4.

## C++

A fully commented backtracking implementation in C++

```#include <iostream>

using namespace std;

const int N = 5;
int position[N];

// Check if a position is safe
bool isSafe(int queen_number, int row_position)
{
// Check each queen before this one
for (int i = 0; i < queen_number; i++)
{
// Get another queen's row_position
int other_row_pos = position[i];

// Now check if they're in the same row or diagonals
if (other_row_pos == row_position || // Same row
other_row_pos == row_position - (queen_number - i) || // Same diagonal
other_row_pos == row_position + (queen_number - i))   // Same diagonal
return false;
}
return true;
}

// Recursively generate a tuple like [0 0 0 0], then [0 0 0 1] then etc...
void solve(int k)
{
if (k == N) // We placed N-1 queens (0 included), problem solved!
{
// Solution found!
cout << "Solution: ";
for (int i = 0; i < N; i++)
cout << position[i] << " ";
cout << endl;
}
else
{
for (int i = 0; i < N; i++) // Generate ALL combinations
{
// Before putting a queen (the k-th queen) into a row, test it for safeness
if (isSafe(k, i))
{
position[k] = i;
// Place another queen
solve(k + 1);
}
}
}
}

int main()
{
solve(0);

return 0;
}
```

## C

A backtracking depth-first search (DFS) solution in C:

```#include <stdio.h>

int
is_safe(int rows, int x, int y)
{
int i;

if (y == 0)
return 1;
for (i=0; i < y; ++i) {
if (rows[i] == x || rows[i] == x + y - i || rows[i] == x - y +i)
return 0;
}

return 1;
}

void
putboard(int rows)
{
static int s = 0;
int x, y;

printf("\nSolution #%d:\n---------------------------------\n", ++s);
for (y=0; y < 8; ++y) {
for (x=0; x < 8; ++x)
printf(x == rows[y] ? "| Q " : "|   ");
printf("|\n---------------------------------\n");
}
}

void
eight_queens_helper(int rows, int y)
{
int x;

for (x=0; x < 8; ++x) {
if (is_safe(rows, x, y)) {
rows[y] = x;
if (y == 7)
putboard(rows);
else
eight_queens_helper(rows, y+1);
}
}
}

int
main()
{
int rows;

eight_queens_helper(rows, 0);

return 0;
}
```

```import Control.Monad

queens n = foldM (\y _ -> [ x : y | x <- [1..n], safe x y 1]) [] [1..n]
safe x [] n = True
safe x (c:y) n = and [ x /= c, x /= c + n, x /= c - n, safe x y (n+1)]

main = mapM_ print \$ queens 8
```

## Python

```def queensproblem(rows, columns):
solutions = [[]]
for row in range(rows):
return solutions

return [solution + [new_column]
for solution in prev_solutions
for new_column in range(columns)
if no_conflict(new_row, new_column, solution)]

def no_conflict(new_row, new_column, solution):
return all(solution[row]       != new_column           and
solution[row] + row != new_column + new_row and
solution[row] - row != new_column - new_row
for row in range(new_row))

for solution in queensproblem(8, 8):
print(solution)
```

## Mathematica

```dispSol[sol_] := sol /. {1 -> "Q", 0 -> "-"} // Grid

solveNqueens[n_] :=
Module[{c, m, b, vars}, c = cqueens[n]; m = mqueens[n];
vars = mqueens2[n]; b = bqueens[Length[m]];
Partition[LinearProgramming[c, m, b, vars, Integers], n]]

cqueens[n_] := Table[-1, {i, n^2}]

bqueens[l_] := Table[{1, -1}, {i, l}]

mqueens2[n_] := Table[{0, 1}, {i, n^2}]

mqueens[n_] :=
Module[{t, t2, t3, t4}, t = mqueensh[n]; t2 = Append[t, mqueensv[n]];
t3 = Append[t2, mqueensd[n]]; t4 = Append[t3, mqueensdm[n]];
Partition[Flatten[t4], n^2]]

mqueensh[n_] :=
Module[{t}, t = Table[0, {i, n}, {j, n^2}];
For[i = 1, i <= n, i++,
For[j = 1, j <= n, j++, t[[i, ((i - 1)*n) + j]] = 1]]; t]

mqueensv[n_] :=
Module[{t}, t = Table[0, {i, n}, {j, n^2}];
For[i = 1, i <= n, i++,
For[j = 1, j <= n, j++, t[[j, ((i - 1)*n) + j]] = 1]]; t]

mqueensd[n_] :=
Module[{t}, t = Table[0, {i, (2*n) - 1}, {j, n^2}];
For[k = 2, k <= 2 n, k++,
For[i = 1, i <= n, i++,
For[j = 1, j <= n, j++,
If[i + j == k, t[[k - 1, ((i - 1)*n) + j]] = 1]]]]; t]

mqueensdm[n_] :=
Module[{t}, t = Table[0, {i, Sum[1, {i, 1 - n, n - 1}]}, {j, n^2}];
For[k = 1 - n, k <= n - 1, k++,
For[i = 1, i <= n, i++,
For[j = 1, j <= n, j++,
If[i == j - k, t[[k + n, ((i - 1)*n) + j]] = 1]]]]; t]
```