puzzle-solvers

  1// Obvious things left to do:
  2//
  3// Heuristic for choosing squares.  We want the most amount of information
  4// per play, so that probably means going where we'd get a row and/or column to
  5// the lowest possible number, since we can then set a whole bunch of cells in
  6// one shot.
  7//
  8// Is it reasonable to try to be smart about whether setting water or ships?
  9//
 10// Should play more of the game to find more strategies to use.
 11
 12use std::fmt::Display;
 13use Cell::*;
 14
 15#[derive(Eq, PartialEq, PartialOrd, Ord, Clone, Copy, Debug)]
 16struct Point {
 17    row: i32,
 18    col: i32,
 19}
 20
 21#[derive(Copy, Clone)]
 22enum Direction {
 23    Up,
 24    Right,
 25    Down,
 26    Left,
 27}
 28
 29impl Direction {
 30    fn opposite(&self) -> Direction {
 31        match self {
 32            Direction::Up => Direction::Down,
 33            Direction::Right => Direction::Left,
 34            Direction::Down => Direction::Up,
 35            Direction::Left => Direction::Right,
 36        }
 37    }
 38}
 39
 40impl Point {
 41    fn new(col: i32, row: i32) -> Point {
 42        Point { row, col }
 43    }
 44
 45    fn travel(&self, d: Direction) -> Self {
 46        match d {
 47            Direction::Up => Point::new(self.col, self.row - 1),
 48            Direction::Right => Point::new(self.col + 1, self.row),
 49            Direction::Down => Point::new(self.col, self.row + 1),
 50            Direction::Left => Point::new(self.col - 1, self.row),
 51        }
 52    }
 53
 54    fn index(&self, size: i32) -> usize {
 55        (self.row * size + self.col) as usize
 56    }
 57
 58    fn neighbors_orthogonal(&self) -> [Point; 4] {
 59        [
 60            Point::new(self.col + 1, self.row),
 61            Point::new(self.col, self.row + 1),
 62            Point::new(self.col - 1, self.row),
 63            Point::new(self.col, self.row - 1),
 64        ]
 65    }
 66
 67    fn neighbors_diagonal(&self) -> [Point; 4] {
 68        [
 69            Point::new(self.col + 1, self.row + 1),
 70            Point::new(self.col - 1, self.row + 1),
 71            Point::new(self.col - 1, self.row - 1),
 72            Point::new(self.col + 1, self.row - 1),
 73        ]
 74    }
 75
 76    fn neighbors_all(&self) -> [Point; 8] {
 77        [
 78            Point::new(self.col + 1, self.row),
 79            Point::new(self.col + 1, self.row + 1),
 80            Point::new(self.col, self.row + 1),
 81            Point::new(self.col - 1, self.row + 1),
 82            Point::new(self.col - 1, self.row),
 83            Point::new(self.col - 1, self.row - 1),
 84            Point::new(self.col, self.row - 1),
 85            Point::new(self.col + 1, self.row - 1),
 86        ]
 87    }
 88}
 89
 90#[derive(Eq, PartialEq, Debug, PartialOrd, Ord, Clone, Copy)]
 91enum Cell {
 92    Empty,
 93    Water,
 94    Ship,
 95}
 96
 97enum InputCell {
 98    ShipSingle,
 99    ShipLeft,
100    ShipRight,
101    ShipTop,
102    ShipBottom,
103    ShipMiddle,
104    Water,
105}
106
107#[derive(Default, Eq, PartialEq, Debug, Clone)]
108struct Game {
109    cols: Vec<i32>,
110    rows: Vec<i32>,
111    board: Vec<Cell>,
112    ships: Vec<i32>,
113    size: i32,
114}
115
116#[derive(Debug)]
117enum SetResult {
118    Ok,
119    Bad,
120    Solved,
121}
122
123impl Display for Game {
124    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
125        write!(f, "  ")?;
126        for col in &self.cols {
127            write!(f, "{} ", col)?;
128        }
129        writeln!(f)?;
130
131        for row in 0..self.size {
132            write!(f, "{} ", self.rows[row as usize])?;
133            for col in 0..self.size {
134                let p = Point { row, col };
135                match self.get(p) {
136                    Cell::Empty => write!(f, ". ")?,
137                    Cell::Ship => write!(f, "S ")?,
138                    Cell::Water => write!(f, "~ ")?,
139                }
140            }
141            writeln!(f)?;
142        }
143
144        Ok(())
145    }
146}
147
148static ts: &[Cell] = &[Cell::Water, Cell::Ship];
149
150impl Game {
151    fn solve(&mut self) -> SetResult {
152        //println!("{self}");
153
154        'outer: for row in 0..self.size {
155            for col in 0..self.size {
156                let p = Point { row, col };
157                if self.get(p) != Cell::Empty {
158                    continue;
159                }
160
161                for cell in ts {
162                    let mut new = self.clone();
163                    match new.set(p, *cell) {
164                        SetResult::Ok => (),
165                        SetResult::Bad => continue,
166                        SetResult::Solved => return SetResult::Solved,
167                    }
168
169                    match new.solve() {
170                        SetResult::Ok => panic!("returned ok??"),
171                        SetResult::Bad => continue,
172                        SetResult::Solved => return SetResult::Solved,
173                    }
174                }
175
176                break 'outer;
177            }
178        }
179
180        let ships = self.clone().num_ships();
181
182        if ships.len() != self.ships.len()
183            || ships
184                .iter()
185                .zip(self.ships.iter())
186                .any(|(one, two)| one != two)
187        {
188            SetResult::Bad
189        } else {
190            SetResult::Solved
191        }
192    }
193
194    fn flood_fill_ship(&mut self, p: Point) -> Option<i32> {
195        // Flood fill. We will always hit from the top left, since
196        // we iterate from the top left to bottom right.
197
198        debug_assert!(self.maybe_get(p).unwrap_or(Cell::Empty) == Cell::Ship);
199
200        let orig_p = p;
201        let d = if self
202            .maybe_get(p.travel(Direction::Right))
203            .unwrap_or(Cell::Empty)
204            == Cell::Ship
205        {
206            Direction::Right
207        } else if self
208            .maybe_get(p.travel(Direction::Down))
209            .unwrap_or(Cell::Empty)
210            == Cell::Ship
211        {
212            Direction::Down
213        } else if p
214            .neighbors_orthogonal()
215            .into_iter()
216            .any(|p| self.maybe_get(p).unwrap_or(Cell::Water) == Cell::Empty)
217        {
218            self.set_internal(p, Cell::Water);
219            return None;
220        } else {
221            self.set_internal(p, Cell::Water);
222            return Some(1);
223        };
224
225        let mut p = p;
226        let mut size = 0;
227        while self.maybe_get(p).unwrap_or(Cell::Empty) == Cell::Ship {
228            size += 1;
229            self.set_internal(p, Cell::Water);
230            p = p.travel(d);
231        }
232
233        if self.maybe_get(p).unwrap_or(Cell::Water) != Cell::Water
234            || self
235                .maybe_get(orig_p.travel(d.opposite()))
236                .unwrap_or(Cell::Water)
237                != Cell::Water
238        {
239            None
240        } else {
241            debug_assert!(size != 0);
242            Some(size)
243        }
244    }
245
246    fn num_ships(&mut self) -> Vec<i32> {
247        let mut ships: Vec<i32> = Vec::with_capacity(15);
248        for row in 0..self.size {
249            for col in 0..self.size {
250                let p = Point::new(col, row);
251
252                if self.get(p) == Cell::Ship {
253                    let f = self.flood_fill_ship(p);
254                    match f {
255                        Some(size) => {
256                            if size as usize >= ships.len() {
257                                ships.resize(size as usize + 1, 0);
258                            }
259                            ships[size as usize] += 1;
260                        }
261                        None => continue,
262                    }
263                }
264            }
265        }
266
267        ships
268    }
269
270    fn reduce_row<T>(&self, row: i32, init: T, f: fn(T, Cell) -> T) -> T {
271        let mut p = Point { row, col: 0 };
272        let mut acc = init;
273        while p.col < self.size {
274            acc = f(acc, self.get(p));
275            p.col += 1;
276        }
277
278        acc
279    }
280
281    fn reduce_col<T>(&self, col: i32, init: T, f: fn(T, Cell) -> T) -> T {
282        let mut p = Point { row: 0, col };
283        let mut acc = init;
284        while p.row < self.size {
285            acc = f(acc, self.get(p));
286            p.row += 1;
287        }
288
289        acc
290    }
291
292    fn set_internal(&mut self, p: Point, c: Cell) {
293        debug_assert_ne!(c, Cell::Empty);
294        self.board[p.index(self.size)] = c;
295    }
296
297    fn set_maybe(&mut self, p: Point, c: Cell) -> SetResult {
298        if p.row >= self.size || p.row < 0 || p.col >= self.size || p.col < 0 {
299            SetResult::Ok
300        } else {
301            self.set(p, c)
302        }
303    }
304
305    fn set_input(&mut self, p: Point, c: InputCell) -> SetResult {
306        match c {
307            InputCell::ShipSingle => {
308                match self.set(p, Cell::Ship) {
309                    SetResult::Ok => (),
310                    SetResult::Bad => return SetResult::Bad,
311                    SetResult::Solved => return SetResult::Solved,
312                };
313
314                for p in p.neighbors_all() {
315                    match self.set_maybe(p, Cell::Water) {
316                        SetResult::Ok => (),
317                        SetResult::Bad => return SetResult::Bad,
318                        SetResult::Solved => return SetResult::Solved,
319                    };
320                }
321            }
322
323            InputCell::ShipLeft => {
324                match self.set(p, Cell::Ship) {
325                    SetResult::Ok => (),
326                    SetResult::Bad => return SetResult::Bad,
327                    SetResult::Solved => return SetResult::Solved,
328                };
329
330                match self.set(
331                    Point {
332                        row: p.row,
333                        col: p.col + 1,
334                    },
335                    Cell::Ship,
336                ) {
337                    SetResult::Ok => (),
338                    SetResult::Bad => return SetResult::Bad,
339                    SetResult::Solved => return SetResult::Solved,
340                };
341
342                match self.set_maybe(
343                    Point {
344                        row: p.row,
345                        col: p.col - 1,
346                    },
347                    Cell::Water,
348                ) {
349                    SetResult::Ok => (),
350                    SetResult::Bad => return SetResult::Bad,
351                    SetResult::Solved => return SetResult::Solved,
352                };
353            }
354            InputCell::ShipRight => {
355                match self.set(p, Cell::Ship) {
356                    SetResult::Ok => (),
357                    SetResult::Bad => return SetResult::Bad,
358                    SetResult::Solved => return SetResult::Solved,
359                };
360
361                match self.set(
362                    Point {
363                        row: p.row,
364                        col: p.col - 1,
365                    },
366                    Cell::Ship,
367                ) {
368                    SetResult::Ok => (),
369                    SetResult::Bad => return SetResult::Bad,
370                    SetResult::Solved => return SetResult::Solved,
371                };
372
373                match self.set_maybe(
374                    Point {
375                        row: p.row,
376                        col: p.col + 1,
377                    },
378                    Cell::Water,
379                ) {
380                    SetResult::Ok => (),
381                    SetResult::Bad => return SetResult::Bad,
382                    SetResult::Solved => return SetResult::Solved,
383                };
384            }
385            InputCell::ShipTop => {
386                match self.set(p, Cell::Ship) {
387                    SetResult::Ok => (),
388                    SetResult::Bad => return SetResult::Bad,
389                    SetResult::Solved => return SetResult::Solved,
390                };
391
392                match self.set(
393                    Point {
394                        row: p.row + 1,
395                        col: p.col,
396                    },
397                    Cell::Ship,
398                ) {
399                    SetResult::Ok => (),
400                    SetResult::Bad => return SetResult::Bad,
401                    SetResult::Solved => return SetResult::Solved,
402                };
403
404                match self.set_maybe(
405                    Point {
406                        row: p.row - 1,
407                        col: p.col,
408                    },
409                    Cell::Water,
410                ) {
411                    SetResult::Ok => (),
412                    SetResult::Bad => return SetResult::Bad,
413                    SetResult::Solved => return SetResult::Solved,
414                };
415            }
416            InputCell::ShipBottom => {
417                match self.set(p, Cell::Ship) {
418                    SetResult::Ok => (),
419                    SetResult::Bad => return SetResult::Bad,
420                    SetResult::Solved => return SetResult::Solved,
421                };
422
423                match self.set(
424                    Point {
425                        row: p.row - 1,
426                        col: p.col,
427                    },
428                    Cell::Ship,
429                ) {
430                    SetResult::Ok => (),
431                    SetResult::Bad => return SetResult::Bad,
432                    SetResult::Solved => return SetResult::Solved,
433                };
434
435                match self.set_maybe(
436                    Point {
437                        row: p.row + 1,
438                        col: p.col,
439                    },
440                    Cell::Water,
441                ) {
442                    SetResult::Ok => (),
443                    SetResult::Bad => return SetResult::Bad,
444                    SetResult::Solved => return SetResult::Solved,
445                };
446            }
447
448            InputCell::ShipMiddle => match self.set(p, Cell::Ship) {
449                SetResult::Ok => (),
450                SetResult::Bad => return SetResult::Bad,
451                SetResult::Solved => return SetResult::Solved,
452            },
453            InputCell::Water => match self.set(p, Cell::Water) {
454                SetResult::Ok => (),
455                SetResult::Bad => return SetResult::Bad,
456                SetResult::Solved => return SetResult::Solved,
457            },
458        };
459
460        SetResult::Ok
461    }
462
463    fn set(&mut self, p: Point, c: Cell) -> SetResult {
464        if self.get(p) != Cell::Empty && self.get(p) != c {
465            return SetResult::Bad;
466        }
467        if self.get(p) == c {
468            return SetResult::Ok;
469        }
470        debug_assert_ne!(c, Cell::Empty);
471
472        let mut sets: Vec<(Point, Cell)> = Vec::new();
473
474        self.set_internal(p, c);
475        if c == Cell::Ship {
476            if self.cols[p.col as usize] == 0 || self.rows[p.row as usize] == 0 {
477                return SetResult::Bad;
478            }
479
480            self.cols[p.col as usize] -= 1;
481            self.rows[p.row as usize] -= 1;
482
483            for p in p.neighbors_diagonal() {
484                sets.push((p, Cell::Water));
485            }
486        }
487
488        let row_empty =
489            self.reduce_row::<i32>(
490                p.row,
491                0,
492                |acc, c| if c == Cell::Empty { acc + 1 } else { acc },
493            );
494
495        // In this case, it's impossible to fill the row with ships
496        if row_empty < self.rows[p.row as usize] {
497            return SetResult::Bad;
498        }
499
500        // Fill all empty cells in row if that's the only possibility.
501        if row_empty == self.rows[p.row as usize] {
502            let mut p = Point { row: p.row, col: 0 };
503            while p.col < self.size {
504                if self.get(p) == Cell::Empty {
505                    sets.push((p, Cell::Ship));
506                }
507
508                p.col += 1
509            }
510        }
511
512        // Fill with water if there shouldn't be any more ships in this row.
513        if self.rows[p.row as usize] == 0 {
514            let mut p = Point { row: p.row, col: 0 };
515            while p.col < self.size {
516                if self.get(p) == Cell::Empty {
517                    sets.push((p, Cell::Water));
518                }
519
520                p.col += 1;
521            }
522        }
523
524        let col_empty =
525            self.reduce_col::<i32>(
526                p.col,
527                0,
528                |acc, c| if c == Cell::Empty { acc + 1 } else { acc },
529            );
530        if col_empty < self.cols[p.col as usize] {
531            return SetResult::Bad;
532        }
533        if col_empty == self.cols[p.col as usize] {
534            let mut p = Point { row: 0, col: p.col };
535            while p.row < self.size {
536                if self.get(p) == Cell::Empty {
537                    sets.push((p, Cell::Ship));
538                }
539
540                p.row += 1;
541            }
542        }
543
544        // Fill with water if there shouldn't be any more ships in this column.
545        if self.cols[p.col as usize] == 0 {
546            let mut p = Point { row: 0, col: p.col };
547            while p.row < self.size {
548                if self.get(p) == Cell::Empty {
549                    sets.push((p, Cell::Water));
550                }
551
552                p.row += 1;
553            }
554        }
555
556        for set in sets {
557            match self.set_maybe(set.0, set.1) {
558                SetResult::Ok => (),
559                SetResult::Bad => return SetResult::Bad,
560                SetResult::Solved => return SetResult::Solved,
561            };
562        }
563
564        let ships = self.clone().num_ships();
565        if ships.len() > self.ships.len()
566            || ships
567                .iter()
568                .zip(self.ships.iter())
569                .any(|(set, target)| *set > *target)
570        {
571            SetResult::Bad
572        } else {
573            SetResult::Ok
574        }
575    }
576
577    fn maybe_get(&self, p: Point) -> Option<Cell> {
578        if p.row >= self.size || p.col >= self.size || p.row < 0 || p.col < 0 {
579            None
580        } else {
581            Some(self.get(p))
582        }
583    }
584
585    fn get(&self, p: Point) -> Cell {
586        debug_assert!(p.row < self.size);
587        debug_assert!(p.col < self.size);
588        debug_assert!(p.row >= 0);
589        debug_assert!(p.col >= 0);
590
591        self.board[p.index(self.size)]
592    }
593}
594
595fn main() {
596    // let mut game = Game {
597    //     cols: vec![1, 2, 2, 0, 2, 3],
598    //     rows: vec![3, 0, 3, 2, 0, 2],
599    //     board: vec![Empty; 8 * 8],
600    //     ships: vec![0, 3, 2, 1],
601    //     size: 6,
602    // };
603
604    // println!(
605    //     "{:?}",
606    //     game.set_input(Point { row: 0, col: 1 }, InputCell::ShipSingle)
607    // );
608    // println!("{game}");
609
610    // let mut game = Game {
611    //     cols: vec![2, 0, 7, 0, 3, 0, 1, 4, 3, 6, 0, 4, 0, 2, 3],
612    //     rows: vec![3, 1, 3, 4, 3, 1, 1, 0, 5, 3, 4, 2, 2, 1, 2],
613    //     board: vec![Empty; 15 * 15],
614    //     ships: vec![0, 5, 4, 3, 2, 1],
615    //     size: 15,
616    // };
617
618    // println!(
619    //     "{:?}",
620    //     game.set_input(Point { row: 0, col: 6 }, InputCell::ShipLeft)
621    // );
622    // println!("{game}");
623    // println!(
624    //     "{:?}",
625    //     game.set_input(Point { row: 0, col: 8 }, InputCell::ShipRight)
626    // );
627    // println!("{game}");
628    // println!(
629    //     "{:?}",
630    //     game.set_input(Point { row: 3, col: 4 }, InputCell::ShipTop)
631    // );
632    // println!("{game}");
633    // println!(
634    //     "{:?}",
635    //     game.set_input(Point { row: 3, col: 8 }, InputCell::ShipLeft)
636    // );
637    // println!("{game}");
638    // println!(
639    //     "{:?}",
640    //     game.set_input(Point { row: 5, col: 0 }, InputCell::ShipBottom)
641    // );
642    // println!("{game}");
643    // println!(
644    //     "{:?}",
645    //     game.set_input(Point { row: 10, col: 13 }, InputCell::ShipSingle)
646    // );
647    // println!("{game}");
648    // println!(
649    //     "{:?}",
650    //     game.set_input(Point { row: 11, col: 9 }, InputCell::ShipMiddle)
651    // );
652    // println!("{game}");
653    // println!(
654    //     "{:?}",
655    //     game.set_input(Point { row: 11, col: 11 }, InputCell::ShipTop)
656    // );
657    // println!("{game}");
658    // println!(
659    //     "{:?}",
660    //     game.set_input(Point { row: 13, col: 11 }, InputCell::ShipMiddle)
661    // );
662    // println!("{game}");
663    // println!(
664    //     "{:?}",
665    //     game.set_input(Point { row: 14, col: 8 }, InputCell::ShipSingle)
666    // );
667    // println!("{game}");
668
669    let mut game = Game {
670        cols: vec![3, 1, 1, 5, 2, 1, 1, 5, 1, 3, 2, 2, 4, 2, 2],
671        rows: vec![3, 2, 2, 3, 1, 7, 0, 1, 0, 8, 0, 5, 1, 2, 0],
672        board: vec![Empty; 15 * 15],
673        ships: vec![0, 5, 4, 3, 2, 1],
674        size: 15,
675    };
676
677    println!("{:?}", game.set_input(Point::new(1, 0), InputCell::Water));
678    println!(
679        "{:?}",
680        game.set_input(Point::new(7, 4), InputCell::ShipBottom)
681    );
682    println!(
683        "{:?}",
684        game.set_input(Point::new(10, 5), InputCell::ShipMiddle)
685    );
686    println!(
687        "{:?}",
688        game.set_input(Point::new(12, 7), InputCell::ShipSingle)
689    );
690    println!(
691        "{:?}",
692        game.set_input(Point::new(2, 9), InputCell::ShipLeft)
693    );
694    println!(
695        "{:?}",
696        game.set_input(Point::new(6, 11), InputCell::ShipLeft)
697    );
698    println!(
699        "{:?}",
700        game.set_input(Point::new(11, 11), InputCell::ShipLeft)
701    );
702    println!(
703        "{:?}",
704        game.set_input(Point::new(0, 12), InputCell::ShipMiddle)
705    );
706    println!(
707        "{:?}",
708        game.set_input(Point::new(10, 13), InputCell::ShipSingle)
709    );
710
711    println!("{:?}", game.solve());
712}