Solve a Hidato puzzle: Difference between revisions
Content added Content deleted
(Added Wren) |
(Add Rust implementation) |
||
Line 3,906: | Line 3,906: | ||
HLPsolver may be used to solve [[Knight's tour#Ruby|Knight's tour]]: |
HLPsolver may be used to solve [[Knight's tour#Ruby|Knight's tour]]: |
||
=={{header|Rust}}== |
|||
<lang rust> |
|||
use std::cmp::{max, min}; |
|||
use std::fmt; |
|||
use std::ops; |
|||
#[derive(Debug, Clone, PartialEq)] |
|||
struct Board { |
|||
cells: Vec<Vec<Option<u32>>>, |
|||
} |
|||
impl Board { |
|||
fn new(initial_board: Vec<Vec<u32>>) -> Self { |
|||
let b = initial_board |
|||
.iter() |
|||
.map(|r| { |
|||
r.iter() |
|||
.map(|c| if *c == u32::MAX { None } else { Some(*c) }) |
|||
.collect() |
|||
}) |
|||
.collect(); |
|||
Board { cells: b } |
|||
} |
|||
fn height(&self) -> usize { |
|||
self.cells.len() |
|||
} |
|||
fn width(&self) -> usize { |
|||
self.cells[0].len() |
|||
} |
|||
} |
|||
impl ops::Index<(usize, usize)> for Board { |
|||
type Output = Option<u32>; |
|||
fn index(&self, (y, x): (usize, usize)) -> &Self::Output { |
|||
&self.cells[y][x] |
|||
} |
|||
} |
|||
impl ops::IndexMut<(usize, usize)> for Board { |
|||
/// Returns a mutable reference to an cell for a given 'x' 'y' coordinates |
|||
fn index_mut(&mut self, (y, x): (usize, usize)) -> &mut Option<u32> { |
|||
&mut self.cells[y][x] |
|||
} |
|||
} |
|||
impl fmt::Display for Board { |
|||
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
|||
let output: Vec<String> = self |
|||
.cells |
|||
.iter() |
|||
.map(|r| { |
|||
let mut row = String::default(); |
|||
r.iter().for_each(|c| match c { |
|||
None => row.push_str(format!("{:>2} ", " ").as_ref()), |
|||
Some(c) if c == &0 => row.push_str(format!("{:>2} ", ".").as_ref()), |
|||
Some(c) => row.push_str(format!("{:>2} ", c).as_ref()), |
|||
}); |
|||
row |
|||
}) |
|||
.collect(); |
|||
write!(f, "{}", output.join("\n")) |
|||
} |
|||
} |
|||
/// Structure for holding puzzle related information. |
|||
#[derive(Clone, Debug)] |
|||
struct Puzzle { |
|||
/// The state of the board. |
|||
board: Board, |
|||
/// All the numbers which were given at puzzle setup: |
|||
/// the numbers which cannot be changed during solving the puzzle. |
|||
fixed: Vec<u32>, |
|||
/// Position of the first number (1). |
|||
start: (usize, usize), |
|||
} |
|||
impl Puzzle { |
|||
/// Creates a new puzzle |
|||
/// * `initial_board` contains the layout and the startin position. |
|||
/// |
|||
/// - Simple numbers in the `initial_board` are considered as "fixed", |
|||
/// aka the solving does not change them |
|||
/// |
|||
/// - As the board can be non-rectangular, all cells which are invalid or cannot be used |
|||
/// are marked with u32::MAX in the `initial_board` |
|||
fn new(initial_board: Vec<Vec<u32>>) -> Self { |
|||
let mut s: (usize, usize) = (0, 0); |
|||
let mut f = initial_board |
|||
.iter() |
|||
.enumerate() |
|||
.flat_map(|(y, r)| r.iter().enumerate().map(move |(x, c)| (y, x, *c))) |
|||
.filter(|(_, _, c)| (1..u32::MAX).contains(c)) |
|||
.fold(Vec::new(), |mut fixed, (y, x, c)| { |
|||
fixed.push(c); |
|||
if c == 1 { |
|||
// store the position of the start |
|||
s = (y, x) |
|||
}; |
|||
fixed |
|||
}); |
|||
f.sort_unstable(); |
|||
Puzzle { |
|||
board: Board::new(initial_board), |
|||
fixed: f, |
|||
start: s, |
|||
} |
|||
} |
|||
pub fn print_board(&self) { |
|||
println!("{}", self.board); |
|||
} |
|||
fn solver(&mut self, current: (usize, usize), n: &u32, mut next: usize) -> bool { |
|||
// reached the last number, solving successful |
|||
if n > self.fixed.last().unwrap() { |
|||
return true; |
|||
} |
|||
// check for exit conditions |
|||
match self.board[current] { |
|||
// cell outside of the board |
|||
None => return false, |
|||
//cell is already has a number in it |
|||
Some(c) if c != 0 && c != *n => return false, |
|||
//cell is empty, but the to be placed number is already matching the next fixed number |
|||
Some(c) if c == 0 && self.fixed[next] == *n => return false, |
|||
// continue |
|||
_ => (), |
|||
} |
|||
let mut backup: u32 = 0; |
|||
if self.board[current] == Some(*n) { |
|||
backup = *n; |
|||
next += 1; |
|||
} |
|||
self.board[current] = Some(*n); |
|||
for y in (max(current.0, 1) - 1)..=min(current.0 + 1, self.board.height() - 1) { |
|||
for x in (max(current.1, 1) - 1)..=min(current.1 + 1, self.board.width() - 1) { |
|||
if self.solver((y, x), &(n + 1), next) { |
|||
return true; |
|||
} |
|||
} |
|||
} |
|||
// unsuccessful branch, restore original value |
|||
self.board[current] = Some(backup); |
|||
false |
|||
} |
|||
pub fn solve(&mut self) { |
|||
let start = self.start; |
|||
self.solver(start, &1, 0); |
|||
} |
|||
} |
|||
fn main() { |
|||
let input = vec![ |
|||
vec![0, 33, 35, 0, 0, u32::MAX, u32::MAX, u32::MAX], |
|||
vec![0, 0, 24, 22, 0, u32::MAX, u32::MAX, u32::MAX], |
|||
vec![0, 0, 0, 21, 0, 0, u32::MAX, u32::MAX], |
|||
vec![0, 26, 0, 13, 40, 11, u32::MAX, u32::MAX], |
|||
vec![27, 0, 0, 0, 9, 0, 1, u32::MAX], |
|||
vec![u32::MAX, u32::MAX, 0, 0, 18, 0, 0, u32::MAX], |
|||
vec![u32::MAX, u32::MAX, u32::MAX, u32::MAX, 0, 7, 0, 0], |
|||
vec![ |
|||
u32::MAX, |
|||
u32::MAX, |
|||
u32::MAX, |
|||
u32::MAX, |
|||
u32::MAX, |
|||
u32::MAX, |
|||
5, |
|||
0, |
|||
], |
|||
]; |
|||
let mut p = Puzzle::new(input); |
|||
p.print_board(); |
|||
p.solve(); |
|||
println!("\nSolution:"); |
|||
p.print_board(); |
|||
} |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
. 33 35 . . |
|||
. . 24 22 . |
|||
. . . 21 . . |
|||
. 26 . 13 40 11 |
|||
27 . . . 9 . 1 |
|||
. . 18 . . |
|||
. 7 . . |
|||
5 . |
|||
Solution: |
|||
32 33 35 36 37 |
|||
31 34 24 22 38 |
|||
30 25 23 21 12 39 |
|||
29 26 20 13 40 11 |
|||
27 28 14 19 9 10 1 |
|||
15 16 18 8 2 |
|||
17 7 6 3 |
|||
5 4 |
|||
</pre> |
|||
=={{header|Seed7}}== |
=={{header|Seed7}}== |
||
<lang seed7>$ include "seed7_05.s7i"; |
<lang seed7>$ include "seed7_05.s7i"; |