I help my clients acquire new users and make more money with their web businesses. I have ten years of experience with SaaS projects. If that’s something you need help with, we should get in touch!
< Back to article list

Solving the 8 queens problem

The 8 queens problem is a popular problem: can you place n chess queens on a n*n board, so that no two queens threaten each other ?

This problem lends itself very well to backtracking; when you are studying computer science, this is often one of the exercises that help you learn it.

The time complexity for the N-queens is usually N!. It’s ok for small N (you most likely only care about N=8 anyway), when as N grows, the algorithm does not scale well.

Fortunately, the problem also has a closed-form solution that spoils all the fun. The complexity is linear, so it is way faster to generate a solution.

import random

def generate_queens(n):
    positions = []
    if ((n%2 == 0) and (n%6==2)):
        for i in range(1, n/2+1):
            positions.append([i, 2*i])
            positions.append([n/2+i, 2*i-1])
    return positions

def draw_board(positions, n):
    board = []
    empty_line = [' ' for i in range(n) ]
    board = [list(empty_line) for i in range(n) ]
    for p in positions:
        board[p[0]-1][p[1]-1] = '*'
    for i in range(n):

def is_valid(positions):
    for p in positions:
        for c in [x for x in positions if x != p]:
            if p[0] == c[0] or p[1] == c[1] or abs(p[0]-c[0])==abs(p[1]-c[1]):
                return False
    return True

n = 8;
queens = generate_queens(n)
draw_board(queens, n)


Here is another solution using the same algorithm, this time in Rust:

use std::fmt;

struct Position {

fn generate_queens(n:i32) -> Vec<Position>{
    let mut positions:Vec<Position> = Vec::new();

    if (n % 2 == 0) && (n %6 == 2) {
        for i in 1..n/2+1 {
                x: i,
                y: 2*i
                x: n/2+i,
                y: 2*i-1


pub struct Board {
    queens: Vec<Position>

impl Board {
    pub fn new(n: i32) -> Board {

impl fmt::Display for Board {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let size = self.queens.len() as i32;
        for i in 0..size {
            for j in 0..size {
                let mut has_queen = false;
                for q in self.queens.iter() {
                    if q.x-1 ==i && q.y-1 == j {
                        let _ = write!(f, "♛");
                        has_queen = true;
                if !has_queen {
                    let _ = write!(f, ".");
            let _ = write!(f, "\n");
        write!(f, "")

fn main() {
    let board = Board::new(8);
    println!("{:#?}", board);
    println!("{}", board);