111 lines
2.4 KiB
Text
111 lines
2.4 KiB
Text
use std::fmt;
|
|
|
|
const SIZE: usize = 8;
|
|
const MOVES: [(i32, i32); 8] = [
|
|
(2, 1),
|
|
(1, 2),
|
|
(-1, 2),
|
|
(-2, 1),
|
|
(-2, -1),
|
|
(-1, -2),
|
|
(1, -2),
|
|
(2, -1),
|
|
];
|
|
|
|
#[derive(Copy, Clone, Eq, PartialEq, PartialOrd, Ord)]
|
|
struct Point {
|
|
x: i32,
|
|
y: i32,
|
|
}
|
|
|
|
impl Point {
|
|
fn mov(&self, &(dx, dy): &(i32, i32)) -> Self {
|
|
Self {
|
|
x: self.x + dx,
|
|
y: self.y + dy,
|
|
}
|
|
}
|
|
}
|
|
|
|
struct Board {
|
|
field: [[i32; SIZE]; SIZE],
|
|
}
|
|
|
|
impl Board {
|
|
fn new() -> Self {
|
|
Self {
|
|
field: [[0; SIZE]; SIZE],
|
|
}
|
|
}
|
|
|
|
fn available(&self, p: Point) -> bool {
|
|
0 <= p.x
|
|
&& p.x < SIZE as i32
|
|
&& 0 <= p.y
|
|
&& p.y < SIZE as i32
|
|
&& self.field[p.x as usize][p.y as usize] == 0
|
|
}
|
|
|
|
// calculate the number of possible moves
|
|
fn count_degree(&self, p: Point) -> i32 {
|
|
let mut count = 0;
|
|
for dir in MOVES.iter() {
|
|
let next = p.mov(dir);
|
|
if self.available(next) {
|
|
count += 1;
|
|
}
|
|
}
|
|
count
|
|
}
|
|
}
|
|
|
|
impl fmt::Display for Board {
|
|
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
|
|
for row in self.field.iter() {
|
|
for x in row.iter() {
|
|
write!(f, "{:3} ", x)?;
|
|
}
|
|
write!(f, "\n")?;
|
|
}
|
|
Ok(())
|
|
}
|
|
}
|
|
|
|
fn knights_tour(x: i32, y: i32) -> Option<Board> {
|
|
let mut board = Board::new();
|
|
let mut p = Point { x: x, y: y };
|
|
let mut step = 1;
|
|
board.field[p.x as usize][p.y as usize] = step;
|
|
step += 1;
|
|
|
|
while step <= (SIZE * SIZE) as i32 {
|
|
// choose next square by Warnsdorf's rule
|
|
let mut candidates = vec![];
|
|
for dir in MOVES.iter() {
|
|
let adj = p.mov(dir);
|
|
if board.available(adj) {
|
|
let degree = board.count_degree(adj);
|
|
candidates.push((degree, adj));
|
|
}
|
|
}
|
|
match candidates.iter().min() {
|
|
// move to next square
|
|
Some(&(_, adj)) => p = adj,
|
|
// can't move
|
|
None => return None,
|
|
};
|
|
board.field[p.x as usize][p.y as usize] = step;
|
|
step += 1;
|
|
}
|
|
Some(board)
|
|
}
|
|
|
|
fn main() {
|
|
let (x, y) = (3, 1);
|
|
println!("Board size: {}", SIZE);
|
|
println!("Starting position: ({}, {})", x, y);
|
|
match knights_tour(x, y) {
|
|
Some(b) => print!("{}", b),
|
|
None => println!("Fail!"),
|
|
}
|
|
}
|