prev • index • info • next

code guessing, round #83 (completed)

started at ; stage 2 at ; ended at

specification

solve 1d minesweeper quickly, please. I'm in a predicament! how hard could it be? submissions can be written in any language.

minesweeper is a-- do you really not know? minesweeper is a logic puzzle game where you clear a grid of tiles, some of which are hidden mines, by revealing 1 time at a time: if you reveal a mine, you lose. you are aided by numerical hints that appear on each revealed tile, telling you exactly how many of the neighbouring tiles are mines. the game is usually played in 2 dimensions. technically, it works the same with any number. it doesn't even have to be a grid; any graph could be used to represent the "neighbouring" relation.

today we will be playing on a line.

there are but 2 visible states for a minesweeper tile during the course of play:

given a line of these tiles ("board"), our goal will be to determine a good one to reveal; one that hopefully isn't a mine.

you may see a problem. let's pretend we've survived the first reveal, and we see this:

- - 1 - -

uh-oh. there's no solution here, no safe tile to reveal. or is there? if we knew that the board only had 1 mine on it, we'd know that both tiles on the edge have to be safe, since the single mine on the board has to be next to the 1. so we can reveal either of these, and be done:

- - 1 - -
^       ^

that's trick #1. the number of mines on the board ("mine count") is always known, and we can use that information to make deductions. but what about when we can't? take a look at this board with 5 mines in total:

- - - 1 0 1 - - 1 - -
? ? *       * ?   ? ?

the location of 2 of the mines is clear, but the rest could be anywhere! what should we do?

...yeah, you know where this is going. time for trick #2: get out the / signs, because where we're going, we need probability. the way to maximize our chances of survival is to choose whichever tile is the least likely to be a mine, since we'll be seeing few guaranteed safe tiles on our journey.

let's see: ½ of the two tiles neighbouring the isolated 1 are mines, and ⅔ of the remaining three unknowns are mines also. so the tiles next to the 1 are safer here. we can do either of these, right?

- - - 1 0 1 - - 1 - -
              ^   ^

right... well, no. not right. we need trick #3 here as well. yes, the chance of either of these two tiles being a mine is 50%. but think about the future! this is minesweeper, not minefair. the game won't cut us a break just because we were forced to guess. our goal is to clear the board, and optimizing our chances of doing so requires upping our game!

imagine we reveal the left option, and it's clear. we already know there's 1 mine next to it, so we're guaranteed to see this:

- - - 1 0 1 - 1 1 - -
? ? *       *     * ?

we're forced to take a 33/66 on one of the tiles. if we're right, we win, and if we're wrong, we lose. all in all, we end up with a ⅙ chance of winning because of the two guesses we made having ½ and ⅓ chances to survive respectively. but what if we had made a different choice?

if we reveal the right option instead, things look better for us. we might see this:

- - - 1 0 1 - - 1 1 -
? ? *       * *     *

since our click revealed more information, we now only have another 50/50 to make. there's a ⅙ chance of winning this way as well. (½ on the first guess, ⅔ that the number it reveals is a 1, and ½ for the subsequent next guess.) so what makes this way better? well, what if we saw this instead?

- - - 1 0 1 - - 1 0 -
* * *       * *     _

holy wow! there's a ⅙ chance again of this scenario occurring that immediately solves the board without having to make another guess. adding those probabilities together, we end up with a ⅓ chance of winning the game if we reveal the right option, twice that of revealing the left option. so there is in fact only 1 correct solution to the problem: we should reveal this tile.

- - - 1 0 1 - - 1 - -
                  ^

or at least there would be only 1 correct solution if it wasn't for trick #4. it's not actually necessary to reveal one of the safest tiles. in this case, we do effectively the exact same thing if we reveal the rightmost tile, so we can do that as well:

- - - 1 0 1 - - 1 - -
                  ^ ^

more complicated than you expected, right? your challenge, given a board and mine count, is to find one of the tiles to reveal for the best chance to clear the board. as any language is allowed, there is no fixed API.

some more examples of boards and correct solutions:

2 | - - - -
    ^ ^ ^ ^

1 | 0 1 - -
          ^

4 | - - - 1 - - -
      ^ ^   ^ ^

2 | - - - 1 - - -
    ^           ^

3 | - - 1 - - -
    ^ ^   ^ ^

3 | - - - 1 - 2 -
        ^

4 | - - 2 - - 1 1 - 1 0
    ^

results

  1. Ⓜ️ kimapr +3 -0 = 3
    1. oleander
    2. ponydork
    3. Indigo
  2. Indigo +1 -1 = 0
    1. kimapr (was oleander)
    2. ponydork
    3. oleander (was kimapr)
  3. oleander +0 -1 = -1
    1. Indigo (was ponydork)
    2. ponydork (was kimapr)
    3. kimapr (was Indigo)
  4. ponydork +0 -2 = -2
    1. Indigo (was oleander)
    2. oleander (was kimapr)
    3. kimapr (was Indigo)

entries

you can download all the entries

entry #1

written by oleander
submitted at
0 likes

guesses
comments 0

post a comment


main.cs ASCII text
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
using System;
namespace minesweeper{
	class Program{
		static void Main(string[] args){
			string input = Console.ReadLine();
			string[] data = input.Split(' ');
			int mines = int.Parse(data[0]);
			bool flipcheck;
			string[] solution = new string[data.Length];
			for (int i = 0; i< data.Length; i++){
				if (solution[i] == null){
					solution[i]=" ";
				}
				if (i>1){
					if (data[i] != "-"){
						flipcheck = (data[i]== "2" || i - 1 < 2 || i + 2 > data.Length);
						
						if (i - 1 > 1){
							if (data[i - 1] == "-"){
								solution[i - 1] = flipcheck ? "^" : "x";
							}
						}
						if (i + 1 < data.Length){
							if (data[i + 1] == "-"){
								solution[i + 1] = flipcheck ? "^" : "x";
							}
						}
					}
				}
			}
			if (Array.IndexOf(solution, "^") == -1){
				if (Array.IndexOf(solution, "x") == -1){
					for (int i = 2; i< data.Length; i++){
						if (data[i] == "-"){
							solution[i] = "^";
						}
					}
				}
				else{
					for (int i = 2; i< data.Length; i++){
						if (solution[i] == "x"){
							solution[i] = "^";
						}
					}
				}
			}
			else{
				for (int i = 2; i< data.Length; i++){
					if (solution[i] == "x"){
						solution[i] = " ";
					}
				}
			}
			Console.WriteLine(string.Join(" ", solution));
		}
	}
}

entry #2

written by ponydork
submitted at
0 likes

guesses
comments 0

post a comment


minesweeper.py ASCII text
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
from itertools import combinations

def is_valid(board, mine_positions):
    board_copy = board[:]
    for pos in mine_positions:
        board_copy[pos] = -2
    if board_copy.count(-2) != len(mine_positions):
        return False

    for i, spot in enumerate(board_copy):
        if spot == -2:
            continue

        left_neighbor = board_copy[i - 1] if i > 0 else None
        right_neighbor = board_copy[i + 1] if i < len(board_copy) - 1 else None

        neighbor_mines = 0
        if left_neighbor == -2:
            neighbor_mines += 1
        if right_neighbor == -2:
            neighbor_mines += 1

        if spot != -1 and spot != neighbor_mines:
            return False

    return True

def generate_variations(board, mine_count):
    hidden_positions = []
    for i, spot in enumerate(board):
        if spot == -1:
            hidden_positions += [i]

    possible_placements = combinations(hidden_positions, mine_count)

    valid_placements = []
    for placement in possible_placements:
        if is_valid(board, placement):
            valid_placements += [placement]

    return valid_placements
    
def board_to_array(board):
    board = board.replace(" ", "")
    minesweeper_board = []

    for spot in board:
        if spot == "-":
            minesweeper_board += [-1]
        else:
            minesweeper_board += [int(spot)]

    return minesweeper_board

def eval_board(mine_count,board):
    board_array = board_to_array(board)
    boards = []

    for placement in generate_variations(board_array, mine_count):
        result_board = [1 if x == -1 else 0 for x in board_array]
        for pos in placement:
            result_board[pos] = 0
        boards += [result_board]

    boards = [sum(x) for x in zip(*boards)]
    max_val = max(boards)
    answer = ["^" if x == max_val else " " for x in boards]

    return f"{mine_count} | {board}\n    {' '.join(answer)}"

def main():
    test_games = [
        [2,"- - - -"],
        [1,"0 1 - -"],
        [4,"- - - 1 - - -"],
        [2,"- - - 1 - - -"],
        [4,"- - 1 - - -"],
        [3,"- - - 1 - 2 -"],
        [4,"- - 2 - - 1 1 - 1 0"],
        [4,"- 1 - - - - 1 - - 1 - -"],
    ]

    for game in test_games:
        print(eval_board(*game))
        print()

if __name__ == "__main__":
    main()

entry #3

written by kimapr
submitted at
0 likes

guesses
comments 0

post a comment


cg83.lua ASCII text
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
for line in io.lines(...) do
	local mines, msep
	local orig_line = line
	mines, msep, line = line:match('^(%d+)( *|)(.*)$')
	mines = tonumber(mines) or -1
	msep = msep or ""
	line = line or ""
	local off = #(mines .. msep)
	local grid = {}
	for i = 1, #line do
		local c = line:sub(i,i)
		if c == '-' or (tonumber(c) and tonumber(c) <= 2) then
			grid[#grid+1] = {
				off = off + i - 1,
				val = c ~= '-' and tonumber(c),
				mine_hits = 0,
				total_hits = 0,
				local_mines = 0,
				local_hits = 0
			}
		end
	end
	grid.total_hits = 0
	grid.mine_hits = 0
	grid.mines = mines
	local mutagen = {}
	local function writer()
		local off = 0
		return function (x, c)
			c = tostring(c)
			assert(x >= off)
			io.write((' '):rep(x - off), c)
			off = x + #c
		end
	end
	local function postrecur()
		local sels = {}
		for i, v in ipairs(grid) do
			if grid[i].local_mines == 0 and grid[i].local_hits > 0 then
				sels[i] = true
			end
		end
		for i, v in ipairs(grid) do
			if grid[i].local_mines == grid[i].local_hits or (sels[i] and not sels[i]) then
				grid.total_hits = grid.total_hits - grid[i].total_hits
				grid.mine_hits = grid.mine_hits - grid[i].mine_hits
				grid[i].mine_hits = 0
				grid[i].total_hits = 0
			end
		end
	end
	local function recursor(len, mines)
		local function mutaget(i)
			if i > len or i < 1 then return 0 end
			return mutagen[i] and 1 or 0
		end
		local function mutacheck(i)
			if i > len or i < 1 then return true end
			if not (grid[i] or {}).val then return true end
			return mutaget(i - 1) + mutaget(i + 1) == grid[i].val
		end
		if mines < 0 or not mutacheck(len - 1) then
			return
		end
		if len == #grid then
			if mines > 0 or not mutacheck(len) then
				return
			end
			local unknown = 0
			for i = 1, len do
				if not grid[i].val then
					unknown = unknown + 1
				end
			end
			if unknown > grid.mines then
				for i = 1, len do
					grid[i].local_hits = grid[i].local_hits + 1
					grid[i].local_mines = grid[i].local_mines + (mutagen[i] and 1 or 0)
					if mutagen[i] then
						grid.total_hits = grid.total_hits + 1
						grid.mine_hits = grid.mine_hits + 1
						grid[i].mine_hits = grid[i].mine_hits + 1
						grid[i].total_hits = grid[i].total_hits + 1
					elseif not grid[i].val then
						local oldgrid = grid
						grid = {}
						for i, v in ipairs(oldgrid) do
							grid[i] = {
								val = v.val,
								off = v.off,
								mine_hits = 0,
								total_hits = 0,
								local_mines = 0,
								local_hits = 0
							}
						end
						grid.total_hits = 0
						grid.mine_hits = 0
						grid.mines = oldgrid.mines
						local function reveal(i)
							if i > len or i < 1 then return false end
							if mutaget(i) > 0 then return end
							if grid[i].val then return false end
							grid[i].val = mutaget(i - 1) + mutaget(i + 1)
							if grid[i].val == 0 then
								reveal(i - 1)
								reveal(i + 1)
							end
							return true
						end
						reveal(i)
						local oldmutagen = mutagen
						mutagen = {}
						recursor(0, grid.mines)
						postrecur()
						oldgrid[i].mine_hits = oldgrid[i].mine_hits + grid.mine_hits
						oldgrid[i].total_hits = oldgrid[i].total_hits + grid.total_hits
						oldgrid.mine_hits = oldgrid.mine_hits + grid.mine_hits
						oldgrid.total_hits = oldgrid.total_hits + grid.total_hits
						grid = oldgrid
						mutagen = oldmutagen
						unknown = unknown + 1
					end
				end
			else
				grid.total_hits = grid.total_hits + 1
			end
			return
		end
		local i = len + 1
		if not grid[i].val then
			mutagen[i] = true
			recursor(i, mines - 1)
		end
		mutagen[i] = false
		return recursor(i, mines)
	end
	recursor(0, mines)
	postrecur()
	if grid.total_hits == 0 then
		print('invalid board')
	else
		local minimum = math.huge
		for i = 1, #grid do
			if grid[i].mine_hits/grid[i].total_hits < minimum and not grid[i].val then
				minimum = grid[i].mine_hits / grid[i].total_hits
			end
		end
		local function stty(isterm, term)
			if isterm ~= nil then return isterm end
			isterm = os.execute('stty <&'..(term or 0)..' >/dev/null 2>&1')
			if tonumber(isterm) then isterm = tonumber(isterm) == 0 end
			return isterm
		end
		isterm_in = stty(isterm_in, 0)
		isterm_out = stty(isterm_out, 1)
		if isterm_out and not isterm_in then
			io.stderr:write(orig_line .. "\n")
			io.stderr:flush()
		end
		local write = writer()
		for i = 1, #grid do
			if grid[i].mine_hits/grid[i].total_hits == minimum and not grid[i].val then
				write(grid[i].off, '^')
			end
		end
		print(('  %.1f%%'):format(math.floor((1-minimum)*1000+.5)/10))
	end
end

entry #4

written by Indigo
submitted at
0 likes

guesses
comments 0

post a comment


main.rs ASCII text
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
use std::{io::Write, iter::zip};

use rand::{rngs::ThreadRng, seq::IteratorRandom};

#[derive(PartialEq, Clone, Copy, Debug)]
enum State {
    Number(i8),
    Unknown,
    Bomb,
}

fn is_compatible(minefield: &[State], truth: &[State]) -> bool {
    zip(minefield, truth).all(|pair| match pair {
        (State::Number(a), State::Number(b)) if a == b => true,
        (State::Bomb, State::Bomb) => true,
        (State::Unknown, _) => true,
        _ => false,
    })
}

fn explore_l(minefield: &mut [State], truth: &[State], idx: usize) {
    for idx in (0..=idx).rev() {
        minefield[idx] = truth[idx];
        if !(truth[idx] == State::Number(0)) {
            minefield[idx - 1] = State::Bomb;
            break;
        }
    }
}
fn explore_r(minefield: &mut [State], truth: &[State], idx: usize) {
    for idx in idx..minefield.len() {
        minefield[idx] = truth[idx];
        if !(truth[idx] == State::Number(0)) {
            minefield[idx + 1] = State::Bomb;
            break;
        }
    }
}

fn explore(minefield: &mut [State], truth: &[State], idx: usize) {
    match truth[idx] {
        State::Number(0) => {
            explore_l(minefield, truth, idx);
            explore_r(minefield, truth, idx);
        }
        State::Number(1) => {
            minefield[idx] = State::Number(1);
        }
        State::Number(2) => {
            minefield[idx] = State::Number(2);
            minefield[idx - 1] = State::Bomb;
            minefield[idx + 1] = State::Bomb;
        }
        _ => unreachable!(),
    }
}

fn evaluate<'a>(
    rng: &mut ThreadRng,
    minefield: &[State],
    truths: Vec<Vec<State>>,
    num_mines: usize,
    depth: i64,
    max_depth: i64,
) -> (usize, i64) {
    assert!(truths.iter().all(|truth| truth.len() == minefield.len()));
    assert!(truths.len() > 0);
    if minefield
        .iter()
        .filter(|cell| matches!(cell, State::Bomb | State::Unknown))
        .count()
        == num_mines
    {
        return (0, 100000);
    }
    if depth >= max_depth {
        return (0, 100000);
    } else {
        let options = minefield
            .iter()
            .enumerate()
            .filter(|(_, cell)| **cell == State::Unknown)
            .choose_multiple(rng, 10);

        assert!(options.len() > 0);

        if options.len() == 1 {
            return (options[0].0, 100000);
        }

        let mut best_option = 0;
        let mut best_score = i64::MIN;

        for (idx, _) in options {
            let mut score = 0;
            for truth in &truths {
                if truth[idx] != State::Bomb {
                    let mut next = Vec::from(minefield);
                    explore(&mut next, truth, idx);
                    let next_truths: Vec<Vec<State>> = truths
                        .iter()
                        .filter(|truth| is_compatible(&next, truth))
                        .cloned()
                        .collect();
                    score +=
                        evaluate(rng, &mut next, next_truths, num_mines, depth + 1, max_depth).1;
                }
            }
            score /= truths.len() as i64;
            if score > best_score {
                best_score = score;
                best_option = idx;
            }
        }
        return (best_option, best_score);
    }
}

fn generate(rng: &mut ThreadRng, len: usize, num_mines: usize) -> Vec<State> {
    // choose_multiple_mut doesn't exist and idk a better way
    let mut minefield = vec![State::Number(0); len];
    let idxs: Vec<usize> = minefield
        .iter()
        .enumerate()
        .choose_multiple(rng, num_mines)
        .iter()
        .map(|(idx, _)| *idx)
        .collect();

    for idx in idxs {
        minefield[idx] = State::Bomb;
        if idx > 0
            && let State::Number(bombs) = minefield[idx - 1]
        {
            minefield[idx - 1] = State::Number(bombs + 1);
        }

        if idx < minefield.len() - 1
            && let State::Number(bombs) = minefield[idx + 1]
        {
            minefield[idx + 1] = State::Number(bombs + 1);
        }
    }
    return minefield;
}

fn solve(minefield: &[State], num_mines: usize) -> usize {
    let mut rng = rand::rng();
    let mut truths = vec![Vec::new(); 100];

    let mut idx = 0;
    while idx < truths.len() {
        let truth = generate(&mut rng, minefield.len(), num_mines);
        if is_compatible(minefield, &truth) {
            truths[idx] = truth;
            idx += 1;
        }
    }

    truths.dedup();

    return evaluate(&mut rng, minefield, truths, num_mines, 0, 10).0;
}

fn main() {
    loop {
        let mut buf = String::new();
        print!("> ");
        std::io::stdout().flush().unwrap();
        std::io::stdin().read_line(&mut buf).unwrap();

        let mut split = buf.trim().split_whitespace();
        let num_mines = str::parse(split.next().unwrap()).unwrap();
        split.next();
        let minefield: Vec<State> = split
            .map(|c| match c {
                "-" => State::Unknown,
                n => State::Number(str::parse(n).unwrap()),
            })
            .collect();

        println!("      {:>1$}", '^', solve(&minefield, num_mines) * 2 + 1);
    }
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn explore_explores_all_cells() {
        let mut minefield = vec![
            State::Unknown,
            State::Unknown,
            State::Unknown,
            State::Unknown,
            State::Unknown,
        ];

        let truth = vec![
            State::Number(0),
            State::Number(0),
            State::Number(0),
            State::Number(0),
            State::Number(0),
        ];

        explore(&mut minefield, &truth, 2);

        assert_eq!(
            minefield,
            vec![
                State::Number(0),
                State::Number(0),
                State::Number(0),
                State::Number(0),
                State::Number(0),
            ]
        );
    }

    #[test]
    fn explore_reveals_until_first_number() {
        let mut minefield = vec![
            State::Unknown,
            State::Unknown,
            State::Unknown,
            State::Unknown,
            State::Unknown,
        ];

        let truth = vec![
            State::Number(0),
            State::Bomb,
            State::Number(1),
            State::Number(0),
            State::Number(0),
        ];

        explore(&mut minefield, &truth, 3);

        assert_eq!(
            minefield,
            vec![
                State::Unknown,
                State::Bomb,
                State::Number(1),
                State::Number(0),
                State::Number(0),
            ]
        );
    }

    #[test]
    fn explore_has_unknown() {
        let mut minefield = vec![
            State::Unknown,
            State::Unknown,
            State::Unknown,
            State::Unknown,
            State::Unknown,
        ];

        let truth = vec![
            State::Number(0),
            State::Bomb,
            State::Number(1),
            State::Number(0),
            State::Number(0),
        ];

        explore(&mut minefield, &truth, 2);

        assert_eq!(
            minefield,
            vec![
                State::Unknown,
                State::Unknown,
                State::Number(1),
                State::Unknown,
                State::Unknown,
            ]
        );
    }

    #[test]
    fn test_case_2() {
        let minefield = vec![
            State::Number(0),
            State::Number(1),
            State::Unknown,
            State::Unknown,
        ];

        assert_eq!(solve(&minefield, 1), 3);
    }

    #[test]
    fn test_case_6() {
        let minefield = vec![
            State::Unknown,
            State::Unknown,
            State::Unknown,
            State::Number(1),
            State::Unknown,
            State::Number(2),
            State::Unknown,
        ];
        assert_eq!(solve(&minefield, 3), 2);
    }

    #[test]
    fn test_case_7() {
        let minefield = vec![
            State::Unknown,
            State::Unknown,
            State::Number(2),
            State::Unknown,
            State::Unknown,
            State::Number(1),
            State::Number(1),
            State::Unknown,
            State::Number(1),
            State::Number(0),
        ];
        assert_eq!(solve(&minefield, 4), 0);
    }
}