minsweeper_rs/solver/
mia.rs

1use crate::board::{Board, BoardSize, Point};
2use crate::solver::Operation::{Chord, Flag, Reveal};
3use crate::solver::{Action, Actionable, GameResult, Logic, Move, Reason, Solver};
4use crate::{CellState, CellType, GameState, GameStatus, Minsweeper};
5use std::cmp::Ordering;
6use std::collections::HashSet;
7use std::fmt::{Display, Formatter};
8use std::hash::{Hash, Hasher};
9use std::ops::Sub;
10use enumset::{EnumSet, EnumSetType};
11
12#[derive(Copy, Clone, Debug, Ord, PartialOrd, Eq, PartialEq, Hash)]
13pub enum Level {
14    Beginner,
15    Intermediate,
16    Expert
17}
18
19impl Level {
20    fn logics(self) -> EnumSet<MiaLogic> {
21        match self {
22            Level::Beginner => MiaLogic::Chord | MiaLogic::FlagChord,
23            Level::Intermediate => MiaLogic::RegionDeductionReveal | MiaLogic::RegionDeductionFlag
24                    | MiaLogic::ZeroMinesRemaining,
25            Level::Expert => MiaLogic::BruteForce | MiaLogic::BruteForceExhaustion,
26        }
27    }
28}
29
30#[derive(Copy, Clone, Debug)]
31pub struct MiaSolver {
32    skill_level: Level,
33    required_level: Option<Level>,
34}
35
36impl MiaSolver {
37    const BRUTE_FORCE_LIMIT: usize = 30;
38
39    pub const fn skill(level: Level) -> Self {
40        Self {
41            skill_level: level,
42            required_level: None,
43        }
44    }
45
46    pub const fn only(level: Level) -> Self {
47        Self {
48            skill_level: level,
49            required_level: Some(level),
50        }
51    }
52}
53
54impl Default for MiaSolver {
55    fn default() -> Self {
56        Self::skill(Level::Expert)
57    }
58}
59
60impl Display for MiaSolver {
61    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
62        write!(f, "{:?}", self)
63    }
64}
65
66impl MiaSolver {
67    fn internal_solve(&self, state: &GameState) -> Option<(Move, MiaLogic)> {
68
69        let size = state.board.size();
70
71        if state.status != GameStatus::Playing { return None };
72
73        for point in size.points() {
74            let CellType::Safe(number) = state.board[point].cell_type else { continue };
75
76            let mut marked_mines = HashSet::new();
77            let mut empty_spaces = HashSet::new();
78
79            for point in size.neighbours(point) {
80                match state.board[point].cell_state {
81                    CellState::Flagged => {
82                        marked_mines.insert(point);
83                        empty_spaces.insert(point);
84                    }
85                    CellState::Unknown => {
86                        empty_spaces.insert(point);
87                    }
88                    _ => {}
89                }
90            }
91
92            if number as usize == marked_mines.len() && empty_spaces.len() > marked_mines.len() {
93                return Some((Move::single(Action::new(point, Chord), Some(Reason::new(MiaLogic::Chord, marked_mines))), MiaLogic::Chord))
94            } else if number as usize == empty_spaces.len() {
95                let clicks: HashSet<_> = size.neighbours(point)
96                        .filter(|e| state.board[*e].cell_state == CellState::Unknown)
97                        .map(|e| Action::new(e, Flag))
98                        .collect();
99
100                if !clicks.is_empty() {
101                    return Some((Move::multi(clicks, Some(Reason::new(MiaLogic::FlagChord, empty_spaces))), MiaLogic::FlagChord));
102                }
103            } else if (number as usize) < marked_mines.len() {
104                let clicks: HashSet<_> = size.neighbours(point)
105                        .filter(|e| state.board[*e].cell_state == CellState::Flagged)
106                        .map(|e| Action::new(e, Flag))
107                        .collect();
108
109                return Some((Move::multi(clicks, Some(Reason::new(MiaLogic::FlagChord, empty_spaces))), MiaLogic::FlagChord));
110            }
111        }
112
113        if self.skill_level < Level::Intermediate {
114            return None
115        }
116
117        // hehe logical deduction
118        // i hope this isn't too hateful to implement in Rust
119
120        #[derive(Clone, Debug, Eq, PartialEq)]
121        struct Flag {
122            number: i8,
123            points: HashSet<Point>
124        }
125
126        impl Flag {
127            pub const fn new(number: i8, points: HashSet<Point>) -> Self {
128                Self { number, points }
129            }
130
131            pub fn contains(&self, other: &Self) -> bool {
132                self.number >= other.number
133                        && self.points.is_superset(&other.points)
134            }
135        }
136
137        impl PartialOrd for Flag {
138            fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
139                if self == other {
140                    return Some(Ordering::Equal)
141                }
142
143                if self.contains(other) {
144                    return Some(Ordering::Greater)
145                }
146
147                if other.contains(self) {
148                    return Some(Ordering::Less)
149                }
150
151                None
152            }
153        }
154
155        impl Sub for &Flag {
156            type Output = Flag;
157
158            fn sub(self, rhs: Self) -> Self::Output {
159                // if !(self >= rhs) {
160                //     panic!("mewo");
161                // }
162
163                let mut points = self.points.clone();
164
165                for point in &rhs.points {
166                    points.remove(point);
167                }
168
169                Flag::new(self.number - rhs.number, points)
170            }
171        }
172
173        impl Hash for Flag {
174            fn hash<H: Hasher>(&self, state: &mut H) {
175                self.number.hash(state);
176                for point in &self.points {
177                    point.hash(state)
178                }
179            }
180        }
181
182        #[cfg(feature = "linked-hash-set")]
183        let mut flags = hashlink::LinkedHashSet::new();
184        #[cfg(not(feature = "linked-hash-set"))]
185        let mut flags = HashSet::new();
186
187        for point in size.points() {
188            let CellType::Safe(mut required) = state.board[point].cell_type else {
189                continue
190            };
191
192            for point in size.neighbours(point) {
193                if state.board[point].cell_state == CellState::Flagged {
194                    required = required.saturating_sub(1)
195                }
196            }
197
198            if required == 0 {
199                continue
200            }
201
202            let neighbours: HashSet<_> = size.neighbours(point)
203                    .filter(|e| state.board[*e].cell_state == CellState::Unknown)
204                    .collect();
205
206            if neighbours.is_empty() {
207                continue
208            }
209
210            flags.insert(Flag::new(required as i8, neighbours));
211        }
212
213        let mut changed = true;
214        while changed {
215
216            let mut to_add = HashSet::new();
217            for flag in &flags {
218                // entirely contained stuffs
219                {
220                    let contained_flags: Vec<_> = flags.iter()
221                            .filter(|e| flag >= e)
222                            .collect();
223
224                    for contained in contained_flags {
225                        let remaining = flag - contained;
226
227                        if remaining.points.is_empty() {
228                            continue
229                        }
230
231                        if remaining.number == 0 {
232                            return Some((Move::multi(
233                                remaining.points
234                                        .into_iter()
235                                        .map(|e| Action::new(e, Reveal))
236                                        .collect(),
237                                Some(Reason::new(MiaLogic::RegionDeductionReveal, contained.points.clone()))
238                            ), MiaLogic::RegionDeductionReveal))
239                        } else if remaining.number > 0 && remaining.number as usize == remaining.points.len() {
240                            return Some((Move::multi(
241                                remaining.points
242                                        .into_iter()
243                                        .map(|e| Action::new(e, Flag))
244                                        .collect(),
245                                Some(Reason::new(MiaLogic::RegionDeductionFlag, contained.points.clone()))
246                            ), MiaLogic::RegionDeductionFlag))
247
248                        }
249
250                        to_add.insert(remaining);
251                    }
252                }
253
254                // not entirely contained stuffs
255                {
256                    let touching_flags = flags.iter()
257                            .filter(|e| e.points.iter()
258                                    .any(|e| flag.points.contains(e)));
259
260                    for touching in touching_flags {
261                        let remaining = flag - touching;
262
263                        if remaining.points.is_empty() {
264                            continue
265                        }
266
267                        if remaining.number > 0 && remaining.number as usize == remaining.points.len() {
268                            return Some((Move::multi(
269                                remaining.points
270                                        .into_iter()
271                                        .map(|e| Action::new(e, Flag))
272                                        .collect(),
273                                Some(Reason::new(MiaLogic::RegionDeductionFlag, touching.points.clone()))
274                            ), MiaLogic::RegionDeductionFlag))
275                        }
276                    }
277                }
278            }
279
280            changed = to_add.into_iter()
281                    .map(|e| flags.insert(e))
282                    .reduce(|a, b| a || b)
283                    .unwrap_or(false);
284        }
285
286        if state.remaining_mines == 0 {
287            let clicks: HashSet<_> = size.points()
288                    .filter(|e| state.board[*e].cell_state == CellState::Unknown)
289                    .map(|e| Action::new(e, Reveal))
290                    .collect();
291
292            if !clicks.is_empty() {
293                return Some((Move::multi(clicks, Some(Reason::new(MiaLogic::ZeroMinesRemaining, HashSet::new()))), MiaLogic::ZeroMinesRemaining))
294            }
295        }
296
297        if self.skill_level < Level::Expert {
298            return None
299        }
300
301        let mut empties = HashSet::new();
302        let mut adjacents = HashSet::new();
303
304        for point in size.points() {
305            if state.board[point].cell_state == CellState::Unknown {
306                for neighbour in size.neighbours(point) {
307                    if matches!(state.board[neighbour].cell_type, CellType::Safe(number) if number > 0) {
308                        empties.insert(point);
309                        adjacents.insert(neighbour);
310                    }
311                }
312            }
313        }
314
315        if empties.len() < Self::BRUTE_FORCE_LIMIT && !adjacents.is_empty() {
316            // let states: Vec<GameState> = brute_force(&adjacents.into_iter().collect(), 0, state)
317            //         .collect();
318
319            let mut result = BruteForceResult::new(size);
320
321            brute_force_3(&empties, &adjacents.iter().copied().collect(), 0, &mut state.clone(), &mut result);
322            // brute_force_2(&empties.iter().copied().collect(), 0, &mut state.clone(), &mut result);
323
324            if result.solve {
325                let mut clicks = HashSet::new();
326
327                for point in empties.iter().copied() {
328                    if result.never_flag.contains(&point) {
329                        clicks.insert(Action::new(point, Reveal));
330                    }
331                    if result.always_flag.contains(&point) {
332                        clicks.insert(Action::new(point, Flag));
333                    }
334                }
335
336                if !clicks.is_empty() {
337                    return Some((Move::multi(clicks, Some(Reason::new(MiaLogic::BruteForce, empties))), MiaLogic::BruteForce))
338                }
339
340                if result.exhaustion {
341                    for point in size.points() {
342                        if state.board[point].cell_state == CellState::Unknown
343                                && result.never_flag.contains(&point) {
344                            clicks.insert(Action::new(point, Reveal));
345                        }
346                    }
347                }
348
349                if !clicks.is_empty() {
350                    return Some((Move::multi(clicks, Some(Reason::new(MiaLogic::BruteForceExhaustion, empties))), MiaLogic::BruteForceExhaustion))
351                }
352
353            }
354
355        }
356
357        None
358    }
359}
360
361impl Solver for MiaSolver {
362
363    fn solve(&self, state: &GameState) -> Option<Move> {
364        self.internal_solve(state)
365                .map(|(e, _)| e)
366    }
367
368    fn solve_game(&self, minsweeper: &mut dyn Minsweeper) -> GameResult {
369        let mut requirement_met = self.required_level.is_none();
370        let required_logic = self.required_level
371                .map(Level::logics)
372                .unwrap_or_default();
373        let mut state = minsweeper.gamestate();
374
375        while state.status == GameStatus::Playing {
376            let Some((Move { actions, ..}, logic)) = self.internal_solve(state) else { break };
377
378            if !requirement_met && required_logic.contains(logic) {
379                requirement_met = true;
380            }
381
382            for action in actions {
383                state = minsweeper.action(action).into()
384            }
385        }
386
387        match state.status {
388            GameStatus::Won if requirement_met => GameResult::Won,
389            GameStatus::Lost => GameResult::Lost,
390            GameStatus::Playing => GameResult::Resigned,
391            _ => GameResult::Resigned
392        }
393
394    }
395}
396
397struct BruteForceResult {
398    solve: bool,
399    always_flag: HashSet<Point>,
400    never_flag: HashSet<Point>,
401    exhaustion: bool
402}
403
404impl BruteForceResult {
405    pub fn new(board_size: BoardSize) -> Self {
406        Self { solve: false, always_flag: board_size.points().collect(), never_flag: board_size.points().collect(), exhaustion: true }
407    }
408}
409
410fn brute_force_3(empties: &HashSet<Point>, adjacents: &Vec<Point>, adjacent_index: usize, state: &mut GameState, result: &mut BruteForceResult) {
411    if is_solved(&state.board) {
412        if state.remaining_mines != 0 {
413            result.exhaustion = false;
414        }
415
416        for point in empties {
417            if state.board[*point].cell_state == CellState::Flagged {
418                result.never_flag.remove(point);
419            } else {
420                result.always_flag.remove(point);
421            }
422        }
423
424        result.solve = true;
425        return
426    }
427    if state.remaining_mines == 0 {
428        return
429    }
430    if adjacent_index >= adjacents.len() {
431        return
432    }
433
434    let adjacent = adjacents[adjacent_index];
435    let CellType::Safe(n) = state.board[adjacent].cell_type else { unreachable!() };
436    let flagged = state.board.size()
437            .neighbours(adjacent)
438            .filter(|point| state.board[*point].cell_state == CellState::Flagged)
439            .count();
440    if n < flagged as u8 {
441        return
442    }
443    let flaggable = state.board.size()
444            .neighbours(adjacent)
445            .filter(|point| state.board[*point].cell_state == CellState::Unknown)
446            .collect();
447    recurse_flag(empties, adjacents, adjacent_index, &flaggable, 0, n as usize - flagged, state, result);
448}
449
450fn recurse_flag(empties: &HashSet<Point>, adjacents: &Vec<Point>, adjacent_index: usize, flaggable: &Vec<Point>, start: usize, mines_to_flag: usize, state: &mut GameState, result: &mut BruteForceResult) {
451
452    if mines_to_flag == 0 {
453        for point in &flaggable[start..] {
454            simulate_reveal(state, *point);
455        }
456        brute_force_3(empties, adjacents, adjacent_index + 1, state, result);
457        for point in &flaggable[start..] {
458            simulate_unreveal(state, *point);
459        }
460        return
461    }
462    for i in start..flaggable.len() {
463
464        simulate_right_click(state, flaggable[i]);
465        recurse_flag(empties, adjacents, adjacent_index, flaggable, i + 1, mines_to_flag - 1, state, result);
466        simulate_right_click(state, flaggable[i]);
467        simulate_reveal(state, flaggable[i])
468    }
469    for point in &flaggable[start..] {
470        simulate_unreveal(state, *point);
471    }
472}
473
474// fn brute_force_2(empties: &Vec<Point>, start: usize, state: &mut GameState, result: &mut BruteForceResult) {
475//     if is_solved(&state.board) {
476//         if state.remaining_mines != 0 {
477//             result.exhaustion = false;
478//         }
479//
480//         for point in empties {
481//             if state.board[*point].cell_state == CellState::Flagged {
482//                 result.never_flag.remove(point);
483//             } else {
484//                 result.always_flag.remove(point);
485//             }
486//         }
487//
488//         result.solve = true;
489//         return
490//     }
491//     if state.remaining_mines == 0 {
492//         return
493//     }
494//     for i in start..empties.len() {
495//         simulate_right_click(state, empties[i]);
496//         if no_overflags(&state.board) {
497//             brute_force_2(empties, i + 1, state, result);
498//         }
499//         simulate_right_click(state, empties[i]);
500//         simulate_reveal(state, empties[i]);
501//
502//     }
503//     for point in empties {
504//         simulate_unreveal(state, *point)
505//     }
506// }
507//
508// fn no_overflags(board: &Board) -> bool {
509//     for point in board.size().points() {
510//         if let CellType::Safe(n) = board[point].cell_type && n > 0
511//                 && board.size()
512//                 .neighbours(point)
513//                 .map(|neighbour| if board[neighbour].cell_state == CellState::Flagged { 1 } else { 0 })
514//                 .sum::<u8>() > n {
515//             return false
516//         }
517//     }
518//     for point in board.size().points() {
519//         if let CellType::Safe(n) = board[point].cell_type && n > 0
520//                 && board.size()
521//                 .neighbours(point)
522//                 .map(|neighbour| if matches!(board[neighbour].cell_state, CellState::Flagged | CellState::Unknown) { 1 } else { 0 })
523//                 .sum::<u8>() < n {
524//             return false
525//         }
526//     }
527//     true
528// }
529
530fn is_solved(board: &Board) -> bool {
531    for point in board.size().points() {
532        if let CellType::Safe(n) = board[point].cell_type && n > 0
533                && board.size()
534                .neighbours(point)
535                .map(|neighbour| if board[neighbour].cell_state == CellState::Flagged { 1 } else { 0 })
536                .sum::<u8>() != n {
537            return false
538        }
539    }
540    true
541}
542
543// fn brute_force(points: &Vec<Point>, index: usize, state: &GameState) -> Box<dyn Iterator<Item = GameState>> {
544//     let size = state.board.size();
545//     let mut empties = vec![];
546//     let current = points[index];
547//
548//     let mut flags = 0;
549//
550//     let CellType::Safe(number) = state.board[current].cell_type else {
551//         unreachable!()
552//     };
553//
554//     for point in size.neighbours(current) {
555//         match state.board[point].cell_state {
556//             CellState::Unknown => empties.push(point),
557//             CellState::Flagged => flags += 1,
558//             _ => {}
559//         }
560//     }
561//
562//     let mines_to_flag = number as isize - flags;
563//
564//     if mines_to_flag > state.remaining_mines || mines_to_flag as usize > empties.len() {
565//         return Box::new(std::iter::empty())
566//     }
567//
568//     if mines_to_flag == 0 || empties.is_empty() {
569//         if index + 1 == points.len() {
570//             return Box::new(std::iter::once(state.clone()));
571//         }
572//         return brute_force(points, index + 1, state);
573//     };
574//
575//     let mut stream: Vec<Box<dyn Iterator<Item = GameState>>> = vec![];
576//
577//     for flag_combinations in get_flag_combinations(&empties, mines_to_flag) {
578//         let mut state_copy = state.clone();
579//
580//         for point in &empties {
581//             if flag_combinations.contains(point) {
582//                 simulate_right_click(&mut state_copy, *point)
583//             } else {
584//                 simulate_reveal(&mut state_copy, *point)
585//             }
586//         }
587//
588//         if index + 1 == points.len() {
589//             stream.push(Box::new(std::iter::once(state_copy)))
590//         } else {
591//             stream.push(Box::new(brute_force(points, index + 1, &state_copy)))
592//         }
593//     }
594//
595//     Box::new(stream.into_iter()
596//             .flatten())
597// }
598//
599// fn get_flag_combinations(empties: &Vec<Point>, mines_to_flag: isize) -> Vec<HashSet<Point>> {
600//     if empties.len() < mines_to_flag as usize {
601//         return Vec::new()
602//     }
603//
604//     recursive_get_flag_combinations(HashSet::new(), empties, 0, mines_to_flag)
605//             .collect()
606// }
607//
608// fn recursive_get_flag_combinations(selected: HashSet<Point>, empties: &Vec<Point>, start: usize, mines_to_flag: isize) -> Box<dyn Iterator<Item = HashSet<Point>>> {
609//     if mines_to_flag < 1 {
610//         return Box::new(std::iter::empty())
611//     }
612//
613//     let mut stream: Vec<Box<dyn Iterator<Item = HashSet<Point>>>> = vec![];
614//
615//     for i in start..empties.len() {
616//         let mut selected = selected.clone();
617//         selected.insert(empties[i]);
618//         if mines_to_flag == 1 {
619//             stream.push(Box::new(std::iter::once(selected)))
620//         } else {
621//             stream.push(recursive_get_flag_combinations(selected, empties, start + 1, mines_to_flag - 1));
622//         }
623//     }
624//
625//     Box::new(stream.into_iter()
626//             .flatten())
627// }
628
629fn simulate_right_click(state: &mut GameState, point: Point) {
630    let cell = &mut state.board[point];
631    match cell.cell_state {
632        CellState::Unknown => {
633            cell.cell_state = CellState::Flagged;
634            state.remaining_mines -= 1;
635        }
636        CellState::Flagged => {
637            cell.cell_state = CellState::Unknown;
638            state.remaining_mines += 1;
639        }
640        CellState::Revealed => unreachable!()
641    }
642}
643
644fn simulate_reveal(state: &mut GameState, point: Point) {
645    // it is normally illegal to have a revealed cell still be unknown
646    // but such are the circumstances we find ourselves in
647    state.board[point].cell_state = CellState::Revealed;
648}
649fn simulate_unreveal(state: &mut GameState, point: Point) {
650    // it is normally illegal to have a revealed cell still be unknown
651    // but such are the circumstances we find ourselves in
652    state.board[point].cell_state = CellState::Unknown;
653}
654
655
656#[derive(EnumSetType, Debug)]
657pub enum MiaLogic {
658    Chord,
659    FlagChord,
660    RegionDeductionReveal,
661    RegionDeductionFlag,
662    ZeroMinesRemaining,
663    BruteForce,
664    BruteForceExhaustion,
665}
666
667impl Display for MiaLogic {
668    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
669        match self {
670            MiaLogic::Chord => write!(f, "the amount of flags around the cell matches its number"),
671            MiaLogic::FlagChord => write!(f, "the amount of flaggable cells around the cell matches its number"),
672            MiaLogic::RegionDeductionReveal => write!(f, "the surrounding cells force the cells to be safe"),
673            MiaLogic::RegionDeductionFlag => write!(f, "the surrounding cells force the cells to be a mine"),
674            MiaLogic::ZeroMinesRemaining => write!(f, "0 mines remaining, all unknown cells must be safe"),
675            MiaLogic::BruteForce => write!(f, "in every possible mine configuration the cells are safe/mines"),
676            MiaLogic::BruteForceExhaustion => write!(f, "in every possible mine configuration every mine is determined, all unused cells must be safe")
677        }
678    }
679}
680
681impl Logic for MiaLogic {
682
683}
minsweeper_rs/solver/mia.rs

minsweeper_rs/solver/
mia.rs
