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[8], int x, int y)  
{
    int i;
 
    for (i=1; i <= y; ++i) {
       if (rows[y-i] == x || rows[y-i] == x-i || rows[y-i] == x+i)
            return 0;
    }
 
    return 1;
}
 
void
putboard(int rows[8])  
{
    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[8], 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[8];
 
    eight_queens_helper(rows, 0);
 
    return 0;
}

Haskell

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):
        solutions = add_one_queen(row, columns, solutions)
    return solutions
 
def add_one_queen(new_row, columns, prev_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)