Created
August 24, 2023 14:00
-
-
Save rphuber/299e0d751fc9584517b1e93315968478 to your computer and use it in GitHub Desktop.
This file contains hidden or 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 = 8; | |
| const NUM_COLS: usize = NUM_ROWS; | |
| const INUM_ROWS: isize = NUM_ROWS as isize; | |
| const INUM_COLS: isize = NUM_COLS as isize; | |
| // Whether we want an open or closed tour | |
| const REQUIRE_CLOSED_TOUR: bool = false; | |
| // Value to represent a square that has not been visited | |
| const UNVISITED: isize = -1; | |
| fn main() { | |
| // Initialize the vector of move offsets. | |
| let mut offsets = [ | |
| [-2, -1], | |
| [-1, -2], | |
| [2, -1], | |
| [1, -2], | |
| [-2, 1], | |
| [-1, 2], | |
| [2, 1], | |
| [1, 2], | |
| ]; | |
| // create a num_rows x num_cols vectore with all the values set to UNVISITED | |
| let mut board = [[UNVISITED; NUM_COLS]; NUM_ROWS]; | |
| // start at board[0][0] | |
| board[0][0] = 0; | |
| // try to find a tour | |
| let start = Instant::now(); | |
| let success = find_tour(&mut board, &mut offsets, 0, 0, 1); | |
| let duration = start.elapsed(); | |
| println!("Time elapsed in find_tour() is: {:?}", duration); | |
| if success { | |
| println!("Found a tour!"); | |
| } else { | |
| println!("No tour found."); | |
| } | |
| dump_board(&mut board); | |
| } | |
| fn dump_board(board: &mut [[isize; NUM_COLS]; NUM_ROWS]) { | |
| for row in board.iter().take(NUM_ROWS) { | |
| for col in row.iter().take(NUM_COLS) { | |
| print!("{:3} ", col); | |
| } | |
| println!(); | |
| } | |
| println!(); | |
| } | |
| fn find_tour( | |
| board: &mut [[isize; NUM_COLS]; NUM_ROWS], | |
| offsets: &mut [[isize; 2]; 8], | |
| cur_row: isize, | |
| cur_col: isize, | |
| count: isize, | |
| ) -> bool { | |
| // If we have visited all the squares, then we are done | |
| if count == (NUM_ROWS * NUM_COLS) as isize { | |
| if REQUIRE_CLOSED_TOUR { | |
| // If we require a closed tour, then we must be able to move from the last square to the first square | |
| for offset in offsets.iter() { | |
| let next_row = cur_row + offset[0]; | |
| let next_col = cur_col + offset[1]; | |
| if next_row == 0 && next_col == 0 { | |
| return true; | |
| } | |
| } | |
| return false; | |
| } else { | |
| // If we don't require a closed tour, then we are done | |
| return true; | |
| } | |
| } | |
| // Try each of the possible moves | |
| for i in 0..8 { | |
| let next_row = cur_row + offsets[i][0]; | |
| let next_col = cur_col + offsets[i][1]; | |
| // Make sure the move is valid | |
| if (0..INUM_ROWS).contains(&next_row) | |
| && (0..INUM_COLS).contains(&next_col) | |
| && board[next_row as usize][next_col as usize] == UNVISITED | |
| { | |
| // If the move is valid, then make it | |
| board[next_row as usize][next_col as usize] = count; | |
| // If the move leads to a solution, then we are done | |
| if find_tour(board, offsets, next_row, next_col, count + 1) { | |
| return true; | |
| } | |
| // Otherwise, undo the move | |
| board[next_row as usize][next_col as usize] = UNVISITED; | |
| } | |
| } | |
| // If we get here, then we did not find a solution | |
| false | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment