eight_puzzle_core/
state.rs

1use crate::direction::Direction;
2use std::cmp::Eq;
3use std::hash::Hash;
4
5pub const NUMBER_OF_STATES: u32 = 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2;
6
7pub trait State: Eq + Hash + Clone
8where
9    Self: Sized,
10{
11    /// Returns the board as an array of length 9.
12    fn to_array(&self) -> [u8; 9];
13
14    /// Returns the `State` from the board.
15    /// If the array is illegal, i.e. not a permutation of 0..9, the result is undefined.
16    fn from_array(array: &[u8; 9]) -> Self;
17
18    /// Returns the hash of the states.
19    /// It should be in range of 0..NUMBER_OF_STATES.
20    fn hash(&self) -> u32;
21
22    fn neighbors(&self) -> Vec<(Direction, Self)> {
23        let mut result = Vec::new();
24        let mut arr: [u8; 9] = self.to_array();
25        for i in 0..9 {
26            if arr[i] == 0 {
27                let mut add_state = |pre: bool, offset: isize, direction: Direction| {
28                    if pre {
29                        let new_i = (i as isize + offset) as usize;
30                        arr[i] = arr[new_i];
31                        arr[new_i] = 0;
32                        result.push((direction, Self::from_array(&arr)));
33                        arr[new_i] = arr[i];
34                    }
35                };
36
37                add_state(i >= 3, -3, Direction::Down);
38                add_state(i < 6, 3, Direction::Up);
39                add_state(i % 3 != 0, -1, Direction::Right);
40                add_state(i % 3 != 2, 1, Direction::Left);
41            }
42        }
43        result
44    }
45
46    fn move_blank<I: Iterator<Item = usize>>(&self, indices: I, offset: isize) -> Option<Self> {
47        let mut arr = self.to_array();
48        for i in indices {
49            if arr[i] == 0 {
50                let new_i = (i as isize + offset) as usize;
51                arr[i] = arr[new_i];
52                arr[new_i] = 0;
53
54                return Some(Self::from_array(&arr));
55            }
56        }
57        None
58    }
59
60    fn up(&self) -> Option<Self> {
61        self.move_blank(3..9, -3)
62    }
63
64    fn down(&self) -> Option<Self> {
65        self.move_blank(0..6, 3)
66    }
67
68    fn left(&self) -> Option<Self> {
69        self.move_blank((1..9).filter(|x| x % 3 != 0), -1)
70    }
71
72    fn right(&self) -> Option<Self> {
73        self.move_blank((0..8).filter(|x| x % 3 != 2), 1)
74    }
75}
76
77#[derive(Hash, PartialEq, Eq, Clone, Copy, Debug)]
78pub struct HashState {
79    hash: u32,
80}
81
82impl State for HashState {
83    fn to_array(&self) -> [u8; 9] {
84        let mut result = [0u8; 9];
85        {
86            let mut rest_hash = self.hash;
87            for i in 1u32..=9u32 {
88                result[(9 - i) as usize] = (rest_hash % i) as u8;
89                rest_hash /= i;
90            }
91        }
92        {
93            let mut appeared = [false; 9];
94            for ele in &mut result {
95                let mut i = 0;
96                while i <= *ele {
97                    if appeared[i as usize] {
98                        *ele += 1
99                    }
100                    i += 1
101                }
102                appeared[*ele as usize] = true;
103            }
104        }
105
106        result
107    }
108
109    fn from_array(arr: &[u8; 9]) -> HashState {
110        let mut hash = 0u32;
111        for i in 0usize..9usize {
112            hash = hash * (9 - i as u32) + arr[i] as u32
113                - arr.iter().take(i as usize).filter(|&&x| x < arr[i]).count() as u32;
114        }
115
116        HashState { hash }
117    }
118
119    fn hash(&self) -> u32 {
120        self.hash
121    }
122}
eight_puzzle_core/state.rs

eight_puzzle_core/
state.rs
