15 puzzle solver: Difference between revisions

Content added Content deleted
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>
Retrieved from "https://rosettacode.org/wiki/15_puzzle_solver"