Created
August 31, 2023 14:12
-
-
Save rphuber/4d99c1061767c6981456003fe3184815 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| use std::time::Instant; | |
| // the board dimensions | |
| const NUM_ROWS: usize = 6; | |
| const NUM_COLS: usize = NUM_ROWS; | |
| fn main() { | |
| // create a new board with all entries set to UNVISITED | |
| let mut board = [[','; NUM_COLS]; NUM_ROWS]; | |
| let start = Instant::now(); | |
| let success = place_queens_1(&mut board, 0, 0); | |
| // let success = place_queens_2(&mut board, 0, 0, 0); | |
| // let success = place_queens_3(&mut board); | |
| let duration = start.elapsed(); | |
| println!("Time: {:?}", duration); | |
| if success { | |
| println!("Success!"); | |
| } else { | |
| println!("Could not find a tour!"); | |
| } | |
| dump_board(&mut board); | |
| } | |
| fn dump_board(board: &mut [[char; NUM_COLS]; NUM_ROWS]) { | |
| for row in 0..NUM_ROWS { | |
| for col in 0..NUM_COLS { | |
| print!("{:<02}", board[row][col]); | |
| } | |
| println!(); | |
| } | |
| } | |
| fn series_is_legal( | |
| board: &mut [[char; NUM_COLS]; NUM_ROWS], | |
| r0: i32, | |
| c0: i32, | |
| dr: i32, | |
| dc: i32, | |
| ) -> bool { | |
| let mut has_queen = false; | |
| let mut r = r0; | |
| let mut c = c0; | |
| loop { | |
| if board[r as usize][c as usize] == 'Q' { | |
| if has_queen { | |
| return false; | |
| } | |
| has_queen = true; | |
| } | |
| // move to the next square | |
| r += dr; | |
| c += dc; | |
| // check if we are off the board | |
| if r >= NUM_ROWS as i32 || c >= NUM_COLS as i32 || r < 0 || c < 0 { | |
| return true; | |
| } | |
| } | |
| } | |
| fn board_is_legal(board: &mut [[char; NUM_COLS]; NUM_ROWS]) -> bool { | |
| // check each row | |
| for r in 0..NUM_ROWS { | |
| if !series_is_legal(board, r as i32, 0, 0, 1) { | |
| return false; | |
| } | |
| } | |
| // check each column | |
| for c in 0..NUM_COLS { | |
| if !series_is_legal(board, 0, c as i32, 1, 0) { | |
| return false; | |
| } | |
| } | |
| // check each diagonal | |
| for r in 0..NUM_ROWS { | |
| if !series_is_legal(board, r as i32, 0, 1, 1) { | |
| return false; | |
| } | |
| } | |
| for c in 1..NUM_COLS { | |
| if !series_is_legal(board, 0, c as i32, 1, 1) { | |
| return false; | |
| } | |
| } | |
| // check each anti-diagonal | |
| for r in 0..NUM_ROWS { | |
| if !series_is_legal(board, r as i32, NUM_COLS as i32 - 1, 1, -1) { | |
| return false; | |
| } | |
| } | |
| for c in 0..NUM_COLS - 1 { | |
| if !series_is_legal(board, 0, c as i32, 1, -1) { | |
| return false; | |
| } | |
| } | |
| true | |
| } | |
| fn board_is_a_solution(board: &mut [[char; NUM_COLS]; NUM_ROWS]) -> bool { | |
| // check the board is legal | |
| if !board_is_legal(board) { | |
| return false; | |
| } | |
| // check that there are NUM_ROWS queens on the board | |
| let mut num_queens = 0; | |
| for r in 0..NUM_ROWS { | |
| for c in 0..NUM_COLS { | |
| if board[r][c] == 'Q' { | |
| num_queens += 1; | |
| } | |
| } | |
| } | |
| num_queens == NUM_ROWS | |
| } | |
| fn place_queens_1(board: &mut [[char; NUM_COLS]; NUM_ROWS], r: usize, c: usize) -> bool { | |
| if r >= NUM_ROWS { | |
| return board_is_a_solution(board); | |
| } | |
| // find the next square | |
| let mut next_r = r; | |
| let mut next_c = c + 1; | |
| if next_c >= NUM_COLS { | |
| next_c = 0; | |
| next_r += 1; | |
| } | |
| // try not placing a queen | |
| if place_queens_1(board, next_r, next_c) { | |
| return true; | |
| } | |
| // try placing a queen | |
| board[r][c] = 'Q'; | |
| if place_queens_1(board, next_r, next_c) { | |
| return true; | |
| } | |
| board[r][c] = ','; | |
| false | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment