Eight queen problem

Introduction

Running code

Running the Project with Cargo

1. Navigate to the project directory:

cd ai_project

1. Run the project:

cargo run --release

This will compile and run the `src/main.rs` file. Subsequent calls will complete faster as no compilation needs to take place.

Running the binary directly

Otherwise go the github releases and use one of the binaries present there that matches your operating system.

Grundlegende problemstellung

Das 8 Queen problem besteht aus einem 8x8 Schachbrett. Bei den queen Problemen ist die Grö\ss e des Boards nxn wenn die Anzahl der zu platzierende Queens n ist. Um das problem zu lösen muss man entweder eine oder alle mögliche lösungen finden. Eine lösung ist valide wenn 8 queens auf Board sind und keine der queens direct eine andere angreifen kann. In diesem fall werden alle mögliche Lösungen gesucht.

Constraint satisfaction

• Reiheneinschränkung: Jede Dame wird in einer eindeutigen Reihe platziert, was bedeutet, dass keine zwei Damen dieselbe Spalte teilen können.
• Spalteneinschränkung: Jede Dame wird in einer eindeutigen Spalte platziert. Diese Einschränkung wird durch eine Funktion erfüllt, die jede Reihe auf eine passende Spaltennummer überprüft.
• Diagonaleinschränkungen: Keine zwei Damen dürfen sich auf derselben Diagonalen befinden. Das bedeutet, dass für zwei Damen an den Positionen $(r_1, c_1)$ und $(r_2, c_2)$ gilt:
  • Sie dürfen nicht die Bedingung $r_2 - r_1 = c_2 - c_1$ erfüllen (gleiche Diagonale mit “positiver Steigung”).
  • Sie dürfen nicht die Bedingung $r_2 - r_1 = -(c_2 - c_1)$ erfüllen (gleiche Diagonale mit “negativer Steigung”).

Wie wird es modelliert

• Die state des Boards wird anhand von der Board class dargestellt.
• Diese stellt den State der Queens auf dem Board anhand von einem Vector da.
  • Beispielsweise: $Q_1 = 1, Q_2 = 3$ bedeutet, dass die erste Dame in der ersten Zeile, erste Spalte, und die zweite Dame in der zweiten Zeile, dritte Spalte steht.
• die Constraints stellen sicher, dass keine zwei Damen dieselbe Spalte oder Diagonale teilen.
• Au\ss erdem wird der state des solvers anhand der solution count dargestellt.

was gibt das Programm im Erfolgs/Fehlerfall aus

In einem Erfolgsfall werden all mögliche lösung ausgegeben und auch die Anzahl and gefundene lösungen. In einem Fehlerfall (Z.b wenn eine nicht implementierte anzahl von queens dem solver gegeben werden kommt eine Fehlermeldung die dies sagt.

welche heuristische funktionen werden verwendet?

Es gibt mehrere bekannte heuristische Funktionen die anwendbar sind. Diese Funktionen würden aber nur für die findung einer einzelne lösung nutzlich sein oder für eine größeres n Queen Problem, da diese uns helfen würden die einfachste lösung zu finden indem wir Z.b. nur die Queens mit den wenigsten constraints setzen. Wir wollen aber alle lösung finden also wurden sie hier nicht angewandt.[cite:@martinjak2007comparisonheuristicalgorithms] Mögliche Heuristische Funktionen:

Implementation

Structure

#[derive(Debug)]
struct Board {
    size: usize,
    board: Vec<Option<i8>>, // Each row points to a column (None if no queen is present)
}

impl Board {
    /// Constructor to initialize the board
    fn new(size: usize) -> Self {
        Self {
            size,
            board: vec![None; size],
        }
    }

getter

/// Getter for column of queen in provided row
fn get(&self, row: usize) -> Option<i8> {
    if row < self.size  {
        self.board[row]
    } else {
        None
    }
}

Constraints

row and column constraint

Two queens on the same row would cause them to attack eachother, we have implemented via the structure the constraint that only one queen can exist per row. As the Vector we use to model the queen placement can only have one number per index.

/// checks for column conflicts
 fn check_column(&self, column: i8) -> bool {
     !self.board.iter().any(|&col| col == Some(column))
 }

Diagonal constraint

/// returns true if diagonal is fine
fn check_diagonal(&self, row_one: usize, col_one: i8, row_two: usize, col_two: i8) -> bool {
    // Calculate differences
    let col_diff = (col_one - col_two).abs();
    let row_diff = (row_one as i8 - row_two as i8).abs();
    !(row_diff == col_diff) // Return whether the diagonal placement is valid
}

/// returns true if all queen diagonals don't conflict with coord
fn check_all_diagonal(&self, row: usize, col: i8) -> bool {
    for q_row in 0..(self.size-1) {
        if let Some(q_col) = self.get(q_row) {//handles the case where q_col is None
            if !self.check_diagonal(row, col, q_row, q_col) {
                return false;
            }
        }
    }
    return true;
}

Check constraints

/// uses all checks to check if coordinate is valid
fn check_valid(&self, row :usize,column: i8) -> bool {
    if !(self.check_column(column)) {
            return false;
    } else if !(row < self.size && column >= 0 && column < self.size as i8) {
            return false;
    } else if !self.check_all_diagonal(row, column) {
            return false;
    }
    return true;
}

setters

/// Setter to place a queen at a specific column and row
fn set(&mut self, row: usize, column: i8) -> bool {
    if self.check_valid(row, column) {
        self.board[row] = Some(column);
        return true;
    } else {
        println!("Invalid Queen position: column={}, row={}. Board size is {}.",column, row, self.size);
        return false;
    }
}

/// unsetter to remove a queen at a specific column and row
fn unset(&mut self, row: usize, column: i8) -> bool {
    if !(row < self.size && column >= 0 && column < self.size as i8) {
        println!("Invalid position: row={}, column={}. Board size is {}.",row, column, self.size);
        return false;
    } else {
        self.board[row] = None;
        return true
    }
}

printing state

/// Get state of all queens via a string
fn get_queens(&self) -> String {
    let queens: Vec<String> = self
        .board
        .iter()
        .enumerate() // Get (row, Option<column>) for each row
        // Map to formatted string if column exists
        .filter_map(|(row, &col)| col.map(|c| format!("{{{}, {}}}", row, c)))
        .collect();
    format!("Queens: [{}]", queens.join(", "))
}

/// print queens state to terminal
fn print_queens(&self) {
    println!("{}", self.get_queens());
}

/// nicer printing of current queen state
fn print_board_grid(&self) {
    print!("===");
    for i in 0..self.size {
        print!("{i}==")
    }
    println!();
    for col in 0..self.size {
        print!("{col}|");
        for row in 0..(self.size as i8) {
            if let Some(queen_col) = self.get(col) {
                if queen_col == row {
                    print!(" Q "); // Queen
                } else {
                    print!(" . "); // Empty
                }
            } else {
                print!(" . "); // Empty
            }
        }
        println!("|"); // Newline after each row
    }
    for _i in 0..self.size {
        print!("===")
    }
    println!("===");
}

end board class

}

Implementing the solver

Most of the work is already done as I can already check for validity and the board has already been modelled with the Board struct. This implements the backtracking solution which finds all possible solutions by repeatedly backtracking till all solutions have been found.

struct Solver {
    solution_count: i32,
}


impl Solver {
    /// Constructor to initialize the solver
    fn new() -> Self {
        Self {
            solution_count: 0,
        }
    }
    fn get_solution_count(&self) -> i32 {
        return self.solution_count;
    }
    fn iterate_solution_count(&mut self) {
        self.solution_count += 1;
    }

    /// the backtrack solution for queen 8x8 problem
    fn backtrack(&mut self, board: &mut Board, row: usize) {
        if row == board.size {
            board.print_board_grid();
            board.print_queens();
            self.iterate_solution_count();
            return
        }
        for col in 0..board.size as i8  {
            if board.check_valid(row, col) {
                board.set(row, col);
                self.backtrack(board, row + 1);
                board.unset(row, col);
            }
        }
        return
    }
}

/// solve 8x8 queens
pub fn solve_n_queens(n: usize) -> i32 {
    let mut board = Board::new(n);
    let mut solver = Solver::new();
    if n <= 10 && n > 0 {
        solver.backtrack(&mut board, 0);
        println!("Solved {n}x{n} Queens problem with {} solutions!", solver.get_solution_count());
        return solver.get_solution_count();
    } else if n < 1{
        println!("Can't solve queen problem for a board that doesn't exist")
    } else {
        println!("Solving for larger than 10 hasn't been implemented yet");
        return 0;
    }
}

fn main() -> Result<(), String> {
    solve_n_queens(8);
    Ok(())
}

Inbetween hidden

#[cfg(test)]
mod tests {
    use super::*;

tests

Some tests that were implemented that check that functions work the way they are intended to.

 #[test]
fn create_queen() {
    let mut board =  Board::new(8);
    let create = board.set(0, 0);
    assert_eq!(create, true);
}

#[test]
fn diagonal_found() {
    let mut board =  Board::new(8);
    board.set(0, 0);
    let bad_coord = board.set(1, 1);
    assert_eq!(bad_coord, false);
    assert_eq!(board.check_diagonal(0,0, 1,1), false);
}

#[test]
fn conflicting_column_found() {
    let mut board =  Board::new(8);
    board.set(1, 2);
    assert_eq!(board.check_column(1),true);
    assert_eq!(board.check_column(2),false);
    assert_eq!(board.check_column(3),true);
}

#[test]
fn too_big() {
    let board =  Board::new(8);
    let too_big = board.check_valid(0, 8);
    let other_too_big = board.check_valid(8, 0);
    let way_too_big = board.check_valid(8, 8);
    let okay_size = board.check_valid(0, 0);
    assert_eq!(too_big, false);
    assert_eq!(other_too_big, false);
    assert_eq!(way_too_big, false);
    assert_eq!(okay_size,true);
}

#[test]
fn too_small() {
    let board =  Board::new(8);
    let too_small = board.check_valid(0, -1);
    let way_too_small = board.check_valid(0, -90);
    assert_eq!(too_small, false);
    assert_eq!(way_too_small, false);
}

#[test]
fn output_test() {
    let mut board =  Board::new(8);
    board.set(0, 0);
    let mut queens = board.get_queens();
    assert_eq!(queens,"Queens: [{0, 0}]");
    board.set(1, 4);
    queens = board.get_queens();
    assert_eq!(queens,"Queens: [{0, 0}, {1, 4}]");
    board.set(2, 7);
    board.set(3, 5);
    queens = board.get_queens();
    assert_eq!(queens,"Queens: [{0, 0}, {1, 4}, {2, 7}, {3, 5}]");
    board.set(4, 2);
    board.set(5, 6);
    queens = board.get_queens();
    assert_eq!(queens,"Queens: [{0, 0}, {1, 4}, {2, 7}, {3, 5}, {4, 2}, {5, 6}]");
    board.set(6, 1);
    board.set(7, 3);
    queens = board.get_queens();
    assert_eq!(queens,"Queens: [{0, 0}, {1, 4}, {2, 7}, {3, 5}, {4, 2}, {5, 6}, {6, 1}, {7, 3}]");
    println!("Test getter:"); // done here as it is easier than setting all queens again
    assert_eq!(board.get(0), Some(0));
    assert_eq!(board.get(1), Some(4));
    assert_eq!(board.get(2), Some(7));
    assert_eq!(board.get(3), Some(5));
    assert_eq!(board.get(4), Some(2));
    assert_eq!(board.get(5), Some(6));
    assert_eq!(board.get(6), Some(1));
    assert_eq!(board.get(7), Some(3));
}

Project auch auf github auffindbar

Link to personal github repo

Tangle only block end

}