0

I'm preparing KOI 2022, so, I'm solving KOI 2021, 2020 problems. KOI 2020 contest 1 1st period problem 5(See problem 5 in here)

I want to make <vector<vector<int>> minesweeper(vector<vector<int>> &v) function that works on 5*5 minesweeper.

argument

vector<vector<int>> &v

Numbers in minesweeper that converted to vector. -1 if it is blank.

e.g. {{0, 0, 1, -1, 1}, {-1, 3, 3, -1, 1}, {-1, -1, -1, -1, 0}, {2, 5, -1, 3, -1}, {-1, -1, -1, -1, -1}}

return value

A vector. Size is same with argument. Mine is 1, default is 0.

English translation of KOI 2020 contest 1 1st period problem 5

There is a 5*5 minesweeper puzzle.

There are 11 numbers, and the others are blank.

0 0 1 가 1
나 3 3 1
다 0
2 5 3
라 마

Where is the mine?

A. 가

B. 나

C. 다

D. 라

E. 마

How can I make minesweeper function? I want algorithm description, too.

cout Hello world endl
  • 63
  • 2
  • 11
  • The minefield is broken. C must be a mine but can't be a mine because it's next to 0. A must be a mine, E must be a mine (unless C is a mine), D must be a mine. B can't be a mine. – Goswin von Brederlow May 08 '22 at 13:34
  • @GoswinvonBrederlow According to answer in [here](https://koi.or.kr/assets/koi/2020/1/solutions/e1-answers.pdf), answer is A. – cout Hello world endl May 09 '22 at 07:18
  • @GoswinvonBrederlow Sorry, there was an typo. I found it and I fixed -1, -1, 다, 0, -1 to -1, -1, -1, 다, 0. – cout Hello world endl May 09 '22 at 07:22
  • 1
    see these: [understanding the minesweeper programming p.roblem](https://stackoverflow.com/a/40070891/2521214) and [Mouse program in Turbo CPP](https://stackoverflow.com/a/45561564/2521214) I know its in ancient Turbo (it was written ages ago) but still it might inspire you for some ideas and how the program solver and game itself architecture can look like ... – Spektre May 09 '22 at 07:27

1 Answers1

3

There two some simple rules to solving Minesweeper:

  1. If a field sees all it's mines then all blank fields don't have mines and can be uncovered.

  2. If a field has as many blank fields as it is missing mines then they all contain mines.

Keep applying those rules over and over till nothing changes.

Now it gets complex because you have to look at combinations of fields. Instead of figuring out lots of special cases for 2, 3, 4 known fields I suggest going straight to a brute force algorithm:

For every blank field next to a know field:

  • create copies of the map with a mine present and not present
  • go back to the top to solve each map
  • if one of the maps results in any known field to not see enough mines then the other case must be the actual solution, apply it and go back to the start

If no progress was made then you have to guess. The above loop can give you probabilities for where mines are and if you know the number of mines total you have a probability for other blank fields. Pick one least likely to have a mine.

Goswin von Brederlow
  • 11,875
  • 2
  • 24
  • 42
  • I am not sure the last part of this approach is valid: If you try out mines, you uncover fields you otherwise would not see – Sebastian May 09 '22 at 07:31
  • You don't uncover the mine. You assume there is a mine and then check if that violates any of the counts in uncovered fields. – Goswin von Brederlow May 09 '22 at 07:36
  • Okay, but do you uncover new fields with numbers? If you would create a ambiguous field on purpose, your algorithm could solve it, although it is unsolvable. – Sebastian May 09 '22 at 07:48
  • Only when you excluded the possibility that the field can hold a mine. When you enter the brute force phase it all becomes speculative and you only flag fields as "maybe a mine" or "maybe not a mine" and see where that leads. Only when you can exclude one or the other as impossible you actually set the field to "mine" or uncover it. – Goswin von Brederlow May 09 '22 at 07:59
  • Okay, I read 'go back to the start' and have not understood from it that it is still the speculative phase. Then it is good :-) – Sebastian May 09 '22 at 09:07