# KeiruaProd

## 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):
print(board[i])

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
print(p)
return True

n = 8;
queens = generate_queens(n)
print(queens)
print("Board:")
draw_board(queens, n)

print(is_valid(queens))


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

use std::fmt;

#[derive(Debug)]
struct Position {
x:i32,
y:i32
}

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 {
positions.push(Position{
x: i,
y: 2*i
});
positions.push(Position{
x: n/2+i,
y: 2*i-1
});
}
}

positions
}

#[derive(Debug)]
pub struct Board {
queens: Vec<Position>
}

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

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;
break;
}
}
if !has_queen {
let _ = write!(f, ".");
}
}
let _ = write!(f, "\n");
}
write!(f, "")
}
}

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


See a typo ? You can suggest a modification on Github.