15 puzzle solver: Difference between revisions
Content deleted Content added
m →{{header|Python}}: format solutions under separate headings |
Added Rust |
||
Line 3,807: | Line 3,807: | ||
(print-path (A* initial-state))) |
(print-path (A* initial-state))) |
||
</lang> |
</lang> |
||
=={{header|Rust}}== |
|||
{{trans|C++}} |
|||
<lang Rust>const NR: [i32; 16] = [3, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3]; |
|||
const NC: [i32; 16] = [3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2]; |
|||
const I: u8 = 1; |
|||
const G: u8 = 8; |
|||
const E: u8 = 2; |
|||
const L: u8 = 4; |
|||
struct FifteenSolver { |
|||
n: usize, |
|||
limit: usize, |
|||
n0: [i32; 85], |
|||
n3: [u8; 85], |
|||
n4: [usize; 85], |
|||
n2: [u64; 85], |
|||
} |
|||
impl FifteenSolver { |
|||
fn f_y(&mut self) -> bool { |
|||
if self.n2[self.n] == 0x123456789abcdef0 { |
|||
return true; |
|||
} |
|||
if self.n4[self.n] <= self.limit { |
|||
return self.f_n(); |
|||
} |
|||
false |
|||
} |
|||
fn f_z(&mut self, w: u8) -> bool { |
|||
if w & I != 0 { |
|||
self.f_i(); |
|||
if self.f_y() { |
|||
return true; |
|||
} |
|||
self.n -= 1; |
|||
} |
|||
if w & G != 0 { |
|||
self.f_g(); |
|||
if self.f_y() { |
|||
return true; |
|||
} |
|||
self.n -= 1; |
|||
} |
|||
if w & E != 0 { |
|||
self.f_e(); |
|||
if self.f_y() { |
|||
return true; |
|||
} |
|||
self.n -= 1; |
|||
} |
|||
if w & L != 0 { |
|||
self.f_l(); |
|||
if self.f_y() { |
|||
return true; |
|||
} |
|||
self.n -= 1; |
|||
} |
|||
false |
|||
} |
|||
fn f_n(&mut self) -> bool { |
|||
self.f_z(match self.n0[self.n] { |
|||
0 => match self.n3[self.n] { |
|||
b'l' => I, |
|||
b'u' => E, |
|||
_ => I + E, |
|||
}, |
|||
3 => match self.n3[self.n] { |
|||
b'r' => I, |
|||
b'u' => L, |
|||
_ => I + L, |
|||
}, |
|||
1 | 2 => match self.n3[self.n] { |
|||
b'l' => I + L, |
|||
b'r' => I + E, |
|||
b'u' => E + L, |
|||
_ => L + E + I, |
|||
}, |
|||
12 => match self.n3[self.n] { |
|||
b'l' => G, |
|||
b'd' => E, |
|||
_ => E + G, |
|||
}, |
|||
15 => match self.n3[self.n] { |
|||
b'r' => G, |
|||
b'd' => L, |
|||
_ => G + L, |
|||
}, |
|||
13 | 14 => match self.n3[self.n] { |
|||
b'l' => G + L, |
|||
b'r' => E + G, |
|||
b'd' => E + L, |
|||
_ => G + E + L, |
|||
}, |
|||
4 | 8 => match self.n3[self.n] { |
|||
b'l' => I + G, |
|||
b'u' => G + E, |
|||
b'd' => I + E, |
|||
_ => I + G + E, |
|||
}, |
|||
7 | 11 => match self.n3[self.n] { |
|||
b'd' => I + L, |
|||
b'u' => G + L, |
|||
b'r' => I + G, |
|||
_ => I + G + L, |
|||
}, |
|||
_ => match self.n3[self.n] { |
|||
b'd' => I + E + L, |
|||
b'l' => I + G + L, |
|||
b'r' => I + G + E, |
|||
b'u' => G + E + L, |
|||
_ => I + G + E + L, |
|||
}, |
|||
}) |
|||
} |
|||
fn f_i(&mut self) { |
|||
let g = (11 - self.n0[self.n]) * 4; |
|||
let a = self.n2[self.n] & (15u64 << g); |
|||
self.n0[self.n + 1] = self.n0[self.n] + 4; |
|||
self.n2[self.n + 1] = self.n2[self.n] - a + (a << 16); |
|||
self.n3[self.n + 1] = b'd'; |
|||
self.n4[self.n + 1] = self.n4[self.n]; |
|||
let cond = NR[(a >> g) as usize] <= self.n0[self.n] / 4; |
|||
if !cond { |
|||
self.n4[self.n + 1] += 1;; |
|||
} |
|||
self.n += 1; |
|||
} |
|||
fn f_g(&mut self) { |
|||
let g = (19 - self.n0[self.n]) * 4; |
|||
let a = self.n2[self.n] & (15u64 << g); |
|||
self.n0[self.n + 1] = self.n0[self.n] - 4; |
|||
self.n2[self.n + 1] = self.n2[self.n] - a + (a >> 16); |
|||
self.n3[self.n + 1] = b'u'; |
|||
self.n4[self.n + 1] = self.n4[self.n]; |
|||
let cond = NR[(a >> g) as usize] >= self.n0[self.n] / 4; |
|||
if !cond { |
|||
self.n4[self.n + 1] += 1; |
|||
} |
|||
self.n += 1; |
|||
} |
|||
fn f_e(&mut self) { |
|||
let g = (14 - self.n0[self.n]) * 4; |
|||
let a = self.n2[self.n] & (15u64 << g); |
|||
self.n0[self.n + 1] = self.n0[self.n] + 1; |
|||
self.n2[self.n + 1] = self.n2[self.n] - a + (a << 4); |
|||
self.n3[self.n + 1] = b'r'; |
|||
self.n4[self.n + 1] = self.n4[self.n]; |
|||
let cond = NC[(a >> g) as usize] <= self.n0[self.n] % 4; |
|||
if !cond { |
|||
self.n4[self.n + 1] += 1; |
|||
} |
|||
self.n += 1; |
|||
} |
|||
fn f_l(&mut self) { |
|||
let g = (16 - self.n0[self.n]) * 4; |
|||
let a = self.n2[self.n] & (15u64 << g); |
|||
self.n0[self.n + 1] = self.n0[self.n] - 1; |
|||
self.n2[self.n + 1] = self.n2[self.n] - a + (a >> 4); |
|||
self.n3[self.n + 1] = b'l'; |
|||
self.n4[self.n + 1] = self.n4[self.n]; |
|||
let cond = NC[(a >> g) as usize] >= self.n0[self.n] % 4; |
|||
if !cond { |
|||
self.n4[self.n + 1] += 1; |
|||
} |
|||
self.n += 1; |
|||
} |
|||
fn new(n: i32, g: u64) -> Self { |
|||
let mut solver = FifteenSolver { |
|||
n: 0, |
|||
limit: 0, |
|||
n0: [0; 85], |
|||
n3: [0; 85], |
|||
n4: [0; 85], |
|||
n2: [0; 85], |
|||
}; |
|||
solver.n0[0] = n; |
|||
solver.n2[0] = g; |
|||
solver |
|||
} |
|||
fn solve(&mut self) { |
|||
while !self.f_n() { |
|||
self.n = 0; |
|||
self.limit += 1; |
|||
} |
|||
println!( |
|||
"Solution found in {} moves: {}", |
|||
self.n, |
|||
std::str::from_utf8(&self.n3[1..=self.n]).unwrap() |
|||
); |
|||
} |
|||
} |
|||
fn main() { |
|||
FifteenSolver::new(8, 0xfe169b4c0a73d852).solve(); |
|||
}</lang> |
|||
{{out}} |
|||
<pre>Solution found in 52 moves: rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd</pre> |