Generating Minesweeper grids

Question

Minesweeper is a logic game found on most OS's. The goal of the game is to determine where the mines are on a grid, given numbers indicating the number of mines around that spot.

Given a grid size, and a set of mines, generate the Minesweeper grid for that set of mines.

Input: Two integers indicating the grid size, and an undefined number of integers indicating the mine positions. Positions will be given as (column position, row position), and the indexes will start at row 1.

Output: The Minesweeper grid. If there are no mines around a block, print an x. For each new row, print a newline. Please output all mines as an asterisk *. Do not leave any whitespace between the values in the row when printing.

Test Cases:

Input "5 5 1 3 3 5 2 4":

xxxxx
11xxx
*21xx
2*21x
12*1x

Input "3 4 3 1 1 4 2 3 3 2":

x2*
13*
2*2
*21

Shortest code wins.

Answer 1

GolfScript 122 98 94 93 91 88 87 85 82 81 80 71

~]2/(\:m;~\:w*,{[.w%)\w/)]:^m\?)42{m{^*~-.*@@-.*+3<},,72or 48+}if}%w/n*

Online demos:

Test Case 1: link

Test Case 2: link

Answer 2

J, 124 116 112 101 87 86 85 84 83 82 79 76 75 72 68 characters

'0x'charsub|:1":3 3(+/@,+9*4&{@,);._3[1(}.x)}0$~2+>{.x=._2<\".1!:1[1

Found what I was looking for - a way to get rid of the spaces (1":) - and finally I'm competitive. Now I just need to figure out the empty set of mines problem.

Takes input from the keyboard.

Edit

New version makes use of a side effect of 1": - numbers larger than 9 are replaced by *.

Answer 3

Mathematica - 247 chars

s[q_] :=
  Module[{d, r},
    d = ToExpression@Partition[Cases[Characters@q, Except@" "], 2];
    r = Rest@d;
    StringJoin @@@ 
    ReplacePart[
    Table[ToString@
       Count[ChessboardDistance[{i, j}, #] & /@ Reverse /@ r, 1], {i,d[[1, 2]]}, 
       {j, d[[1, 1]]}] /. {"0" -> "x"}, # -> "*" & /@ Reverse /@ r] // TableForm]

Examples:

s@"5 5 1 3 3 5 2 4"
s@"3 4 3 1 1 4 2 3 3 2"

Output:

ChessboardDistance computes how far each cell is from a mine, where 1 corresponds to "next to a mine". The Count of 1's yields the cell's number. Then mines (*) are inserted into array.

Answer 4

Mathematica, 140 139 137

Grid[(ListConvolve[BoxMatrix@1,#,2,0]/. 0->x)(1-#)/. 0->"*"]&@Transpose@SparseArray[{##2}->1,#]&@@#~Partition~2&@@#~ImportString~"Table"&

Writing that in a more readable form:

"5 5 1 3 3 5 2 4"

ImportString[%, "Table"][[1]] ~Partition~ 2

Transpose @ SparseArray[{##2} -> 1, #]& @@ %

ListConvolve[BoxMatrix@1, %, 2, 0]

(% /. 0 -> x) (1 - %%) /. 0 -> "*" // Grid

Answer 5

VBA - 298 chars

Sub m(x,y,ParamArray a())
On Error Resume Next:ReDim b(x,y):For i=0 To (UBound(a)-1) Step 2:c=a(i):d=a(i+1):b(c,d)="*":For e=c-1 To c+1:For f=d-1 To d+1:v=b(e,f):If v<>"*" Then b(e,f)=v+1
Next:Next:Next:For f=1 To y:For e=1 To x:v=b(e,f):s=s & IIf(v<>"",v,"x")
Next:s=s & vbCr:Next:MsgBox s
End Sub

Skipping over errors with On Error Resume Next saved me some characters, but this still isn't nearly as good as some of the other answers. :-/

Answer 6

Python, 192 182 180 chars

I could save some if the input was comma-separated. Then the first line would be d=input() and the length 171 chars.
Having the mine coordinates 0-based rather than 1-based would also help. It cost me 8 chars to overcome.

d=map(int,raw_input().split())
m=zip(d[2::2],d[3::2])
for y in range(d[1]):print"".join((str(sum(abs(a-x-1)|abs(b-y-1)<2for a,b in m)or'x')+'*')[(x+1,y+1)in m]for x in range(d[0]))

Ungolfed version:

d=map(int,raw_input().split())          # Read whitespace terminated numbers into a list of numbers
xsize,ysize = d[:2]                     # The first two numbers are the board size
mines=zip(d[2::2],d[3::2])              # Convert items 3,4,5,6... to pairs (3,4),(5,6) representine mine coordinates

def dist(point,mine):                   # Distance between point (0-based coordinates) and mine (1-based coordinates)
    dx = abs(mine[0]-(point[0]+1))
    dy = abs(mine[1]-(point[1]+1))
    return dx | dy                      # Should be max(dx,dy), but this is close enough. Wrong for d>=2, but returns >=2 in this case.

for y in range(ysize):                  # Print lines one by one
    line_chars = [
        (str(
            sum(dist((x,y),(a,b))<2 for a,b in mines)   # Number of neighboring mines
            or 'x'                                  # 'x' instead of 0
        )
        +'*')                                       # For a single neighbor, we get "1*"
        [(x+1,y+1)in mines]                         # If a mine, get the '*', else the neighbor number
        for x in range(xsize)
    ]
    print "".join(line_chars)

Answer 7

Scala, 280 chars

val n=readLine split" "map{_.toInt}
val b=Array.fill(n(1),n(0))(0)
n drop 2 sliding(2,2)foreach{case Array(x,y)=>b(y-1)(x-1)=9
for{i<-(x-2 max 0)to(x min n(0)-1);j<-(y-2 max 0)to(y min n(1)-1)}b(j)(i)+=1}
b.map{r=>println(r.map{case 0=>"x"case x if x>8=>"*"case x=>""+x}mkString)}

Answer 8

ECMAScript 2019 (Modern Javascript) - 116 bytes

m.map((r,i)=>r.map((c,j)=>c=='X'?c:[,...m].splice(i,3).map(r=>[,...r].splice(j,3)).flat().filter(v=>v=='X').length))

ungolfed version

m.map(
  (r,i) => r.map(
    (c,j) => c=='X' ? c :
      [,...m].splice(i,3).map(r=>[,...r].splice(j,3)).flat().filter(v=>v=='X').length
  )
)

this solution doesn't strictly adhere to the input/output format but demonstrates a succinct algorithm.

example: https://gist.github.com/missinglink/ee02084cfb523665e8c9d34c24f01537

Answer 9

brainfuck, 1001 896 bytes

,[>,]-[<]>>++[<[<+<+>>-]<[>+<-]>[>]>[>>[>>>>]>]++[-<+]-[<]<++[>>[>]>[>>[>>>>]>]+<++[-<+]-[<]<-]>>>-]>[>]>[>>[>>>>]<<<->>>>]+[-<+]-[<]>>[[>]>--<<[<]>>[[>]+[->+]+>>[>>>>]>--<+[-<+]-[<]>>-]>[>]+[->+]+>>--<+[-<+]-[<]<[>>[>]+[->+]+>>>>--<+[-<+]-[<]<-]>>[>]+[->+]+>++[-<+]-[<]>>]>[+>>[>>>>]>]<<<<<[<<<<]>>-<+[-<+]>>>>[>>>>]>[-[--<<<<<[<<<<]>>>>--[>>>>]>>>[>>>>]>>>--<+[-<+]++>>>>>>[>[<--<<<[-[>>>>>>+<<<<<+<-]>+<]>[<+>-]>>>>+++[<<<+[-<+]->[-[+[->+]->>>+<<<<+[-<+]->>+<-]>+<]>[<+>-]+[->+]->>-[<<<+[-<+]+>>>>-->+[->+]->>[<<<+>>>-]]<<<[>>>+<<<-]>>>]<<<+[-<+]+<<<<-->+[->+]->>>>>[-[<<+>>>+<-]>+<]>[<+>-]<<<<+++[+[->+]->[-[<<+[-<+]->>>++[->+]->>+<-]>+<]>[<+>-]<<<+[-<+]->>-[+[->+]+>>>>--<+[-<+]->>[<<<+>>>-]]<<<[>>>+<<<-]>>>]+[->+]+<<<<--<+[-<+]->-[>>[-]<<++++++[>++++++<-]>.[-]+<<<]<[>>>[<++++++[>++++++++<-]>.[-]<]<<<[<++++++++[<+++++++++++>-]<.[-]>]<]>>>>+<<++>]>[<+>-]>>]->+[->+]++[-<+]++++++++++.[-]]>]

Try it online! or try the old version with integer input

One day of programming and three days of bugfixing ^^

This uses a few parts of my Game Of Life code. Instead of counting living cells, this counts bombs. Since input as codepoints is allowed by the general rules, this uses them instead of "readable" integers.

[
Data: colCount, rowCount, {BombCoordinates}, -1 (start of arrays/"soa"), 0, {RowData}
BombCoordinates: bombCol, bombRow
RowData: rowFlag, 0, {CellData}, 0
CellData: cellFlag, cellState, temp, bombCount

rowFlag: 0=EOF, 1=inactive (all cells inactive), 2=active
cellFlag: -1=marker for finding cell (cell to be counted or current cell), 0=EOF, 1=normal
cellState: 0=inactive, 1=normal, 2=bomb
temp: helper to exit if-statements
bombCount: count of neighbor cells that contain bombs
inactive cells or rows will not be printed. They are only used for an easier counting algorithm.
]

#### input values as codepoints ####
,[>,]

#### setup two dimensional array ####
-                   set soa
[<]>>               go to rowCount
++                  add two inactive rows
[                   for each row
  <[<+<+>>-]          copy colCount two times to the next left cells
  <[>+<-]             move one of the copies back to the original cell
  >[>]>[>>[>>>>]>]    go to new row position
  +                   set rowFlag (only 1 while initialization)
  +[-<+]-[<]<         go to copy of colCount
  ++                  add two inactive cells per row
  [                   for each col
    >>[>]>[>>[>>>>]>]   go to new cell position
    +<+                 set cellFlag and cellState = normal
    +[-<+]-[<]<         return to copy of colCount
    -                   decrement
  ]
  >>>-                decrement rowCount
]

#### setup active/inactive flags of cells ####
>[>]>[              for each row
  >>[>>>>]<<<-        set last cell inactive
  >>>>                go to next row
]

#### mark the bombs ####
+[-<+]-[<]>>        go to bombRow
[                   while there are bombRow values left
  [>]>--              set rowFlag of first row = neg 1 (as a marker)
  <<[<]>>             return to bombRow
  [                   for each bombRow
    [>]+[->+]           find first marker after soa
    +                   set rowFlag = 1
    >>[>>>>]>           go to next rowFlag
    --                  make a marker of it
    <+[-<+]-[<]>>       return to bombRow
    -                   decrement
  ]
  >[>]+[->+]          go to selected rowFlag
  +                   set rowFlag = 1
  >>--                set cellFlag of first cell = marker
  <+[-<+]-[<]<        go to bombCol
  [                   for each bombCol
    >>[>]+[->+]         find first marker after soa
    +                   set cellState = 1
    >>>>                go to next cellState
    --                  set it neg 1 (as a marker)
    <+[-<+]-[<]<        return to bombCol
    -                   decrement
  ]
  >>[>]+[->+]         find first marker after soa
  +                   set cellFlag = normal
  >+                  set cellState = bomb
  +[-<+]-[<]>>        go to next bombRow
]

#### setup active/inactive flags of rows ####
>[                  for each row
  +                   set rowFlag = 2 (active)
  >>[>>>>]>           go to next rowFlag
]
<<<<<[<<<<]>>-      set rowFlag of last row = 1 (inactive)

#### count bombs in neighborhood ####
<+[-<+]>>>>[>>>>]>  go to second row
[                   for each row
  -[                  if active
    --                  set it neg 1 (marker)
    <<<<<[<<<<]>>>>     go to cellFlag of first cell in previous row
    --                  set it neg 1 (marker)
    [>>>>]>>>[>>>>]>>>  go to cellFlag of first cell in next row
    --                  set it neg 1 (marker)
    <+[-<+]             return to rowFlag
    ++                  set rowFlag = 2 (active)

    >> >>>>[            for each cell (starting with second)
      >[                  if active
        <--                 set cellFlag = neg 1 (marker)

        # check if cell to the left is a bomb
        < <<                go to cellState of previous cell
        [                   if active
          -[                  if bomb
            >> >>>>+            increment bombCount
            <<<< <              go back to checked cell
            +                   set temp = 1
            <-                  set cellState = 0 to exit if
          ]
          >+<                 increment temp
        ]
        >[<+>-]             restore cellState

        # check if cells on top are bombs
        > >>>               go to temp of current cell
        +++[                do three times
          <<<+[-<+]-          go to next marker to the left
          >[                  if active
            -[                  if bomb
              +[->+]-             return to current cell
              >>>+                increment bombCount
              <<<<+[-<+]->        return to counted cell
              >+                  set temp = 1
              <-                  set cellState = 0 to exit if
            ]
            >+<                 increment temp
          ]
          >[<+>-]             restore cellState
          +[->+]-             go to current cell
          >>-                 decrement temp
          [                   if temp != 0
            <<<+[-<+]           go to marked cell
            +                   set cellFlag = normal
            >>>>--              set cellFlag of next cell = marker
            >+[->+]->>          return to currentCell temp
            [<<<+>>>-]          store value of temp in previous cell bombCount (to exit if)
          ]
          <<<[>>>+<<<-]>>>    restore temp value
        ]
        <<<+[-<+]           go to marked cell
        +                   set cellFlag = normal
        <<<<--              set previous cellFlag = marker
        >+[->+]-            return to current cell

        # check if cell to the right is a bomb
        >>> >>              go to cellState of next cell
        [                   if active
          -[                  if bomb
            <<+                 increment bombCount
            >>>                 go back to checked cell
            +                   set temp = 1
            <-                  set cellState = 0 to exit if
          ]
          >+<                 increment temp
        ]
        >[<+>-]             restore cellState

        # check if cells below are bombs
        <<< <               go to currentCell temp
        +++[                do three times
          +[->+]-         go to next marker to the right
          >[              if active
            -[              if bomb
              <<+[-<+]-       return to current cell
              >>>+            increment bombCount
              +[->+]->        return to counted cell
              >+              set temp = 1
              <-              set cellState = 0 to exit if
            ]
            >+<             increment temp
          ]
          >[<+>-]         restore cellState
          <<<+[-<+]-      go to current cell
          >>-             decrement temp
          [               if temp != 0
            +[->+]          go to marked cell
            +               set cellFlag = normal
            >>>>--          set cellFlag of next cell = marker
            <+[-<+]->>      return to currentCell temp
            [<<<+>>>-]      store value of temp in previous cell bombCount (to exit if)
          ]
          <<<[>>>+<<<-]>>>restore temp value
        ]
        +[->+]          go to marked cell
        +               set cellFlag = normal
        <<<<--          set previous cellFlag = marker
        <+[-<+]-        return to current cell

        # print
        >-[             if bomb
          >>[-]<<         delete bombCount
          ++++++[>++++++<-]>.print "*"
          [-]+            set temp = 1
          <<<             use previous cell bombCount as exitIf
        ]
        <[              else
          >>>[            if bombCount != 0
            <++++++[>++++++++<-]add 48 to get ascii number
            >.              print
            [-]             set number = 0 (for use as exitIf from next cell)
            <               go to temp for exit if
          ]
          <<<[            else
            <++++++++[<+++++++++++>-]<.print "X"
            [-]             delete value (for use as exitIf from next cell)
            >               go to exitIf
          ]
          <               go to exitElse
        ]
        > >>>+          increment temp
        <<++>           set cellFlag = normal
      ]
      >[<+>-]         restore cellState
      >>              go to cellFlag of next cell
    ]
    -               set marker
    >+[->+]         go to next marker
    +               set cellFlag = normal
    +[-<+]          return to marker
    +++++ +++++.[-] print newline
  ]
  >               go to next row
]

Answer 10

This is the beginning of a Brainfuck solution. It should be pretty readable with indention and stack comments (@ indicates the stack pointer):

>>,>,  |0|x|@y| Pop the first two characters
[>>+<<-]>>  |0|x|0|0|@y|
[<<+>+>-]<  |0|x|@y|y|0|
[  |0|x|y|@y|
  [>>+<<-]< |0|x|@y|0|0|y|
  [>>+<<-]< |0|@x|0|0|y|y|
  [>>+<<-]>> |0|0|0|@x|y|y|
  [<<+>+>-]<<  |0|@x|x|0|y|y|
  [>>+<<-]> |0|0|@x|x|y|y|
  [<< |@0|0|x|x|y|y|
    ++++++++[>+++++++++++<-]>>>>> |0|88|x|x|@y|y|
    [>+<-]< [>+<-]< [>+<-]< [>+<-]< |0|@88|0|x|x|y|y|
    [<+>-]>>-  |88|0|0|@x_1|x|y|y|
  ]<< |x x's|@0|0|0|x|y|y|
  ++++++++++>>> x's|\n|0|0|@x|y|y|
  [<+>-]>  x's|\n|0|x|0|@y|y|
  [<+>-]>  x's|\n|0|x|y|0|@y|
  [<+>-]<- |x 88s|0|x|@y_1|y|
] |@x 88s|0|x|y|

It is however far from complete and I am starting to doubt if my approach is optimal. So far it only considers the first two input characters and prints a table of Xs. For instance "43" would give you:

XXXX
XXXX
XXXX

I would love to see if somebody else has what it takes and is capable of solving this problem in Brainfuck.

Answer 11

C++ - 454 chars

This is worse than my VBA answer, which probably means I don't know what I'm doing in C++. However, I am trying to build on what I know of C++, so here it is. If anyone has any suggestions for improvement, I'd be grateful to hear them!

#define Z for(int i=
#define Y for(int j=
#define X d[i][j]
#define W Z 0;i<x;i++){
#define V Y 0;j<y;j++){
#define U cout<<
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
int main(){using namespace std;int x,y,a,b;cin>>y>>x;string c[x][y];int d[x][y];W V X=0;}}while(cin>>b>>a){c[--a][--b]="*";Z a-1;i<=a+1;i++){Y b-1;j<=b+1;j++){if(x>i&&i>=0&&y>j&&j>=0){X=X+1;}}}}W V if(c[i][j]!="*"){if(X>0){U X;}else{U"x";}}else{U"*";}}U endl;}return 0;}

Answer 12

C# (691 Chars)

using System;namespace M{class P{static char C(char[][] g,int r,int c){int n=0;for(int i=r-1;i<=r+1;i++){if(i<0||i>=g.Length)continue;for(int j=c-1;j<=c+1;j++){if((j<0||j>=g[0].Length)||(i==r&&j==c))continue;if(g[i][j]=='*')n++;}}return n==0?'x':(char)(n+48);}static char[][] G(int[] p){char[][] r=new char[p[1]][];for(int i=0;i<r.Length;i++)r[i]=new char[p[0]];for(int i=2;i<p.Length;){r[p[i+1]-1][p[i]-1]='*';i+=2;}for(int i=0;i<r.Length;i++)for(int j=0; j<r[0].Length;j++)if(r[i][j]!='*')r[i][j]=C(r,i,j);for(int i=0;i<r.Length;i++){for(int j=0;j<r[0].Length;j++)Console.Write(r[i][j]);Console.WriteLine();}return r;}static void Main(string[] args){G(new int[]{3,4,3,1,1,4,2,3,3,2});}}}

Non-golfed Version:

using System;
namespace M
{
    class P
    {
        static char C(char[][] g, int r, int c)
        {
            int n = 0;
            for (int i = r - 1; i <= r + 1; i++)
            {
                if (i < 0 || i >= g.Length) continue;
                for (int j = c - 1; j <= c + 1; j++)
                {
                    if ((j < 0 || j >= g[0].Length) || (i == r && j == c)) continue;
                    if (g[i][j] == '*') n++;
                }
            }
            return n == 0 ? 'x' : (char)(n + 48);
        }

        static char[][] G(int[] p)
        {
            char[][] r = new char[p[1]][];
            for (int i = 0; i < r.Length; i++)
                r[i] = new char[p[0]];
            for (int i = 2; i < p.Length; )
            {
                r[p[i + 1] - 1][p[i] - 1] = '*';
                i += 2;
            }
            for (int i = 0; i < r.Length; i++)
                for (int j = 0; j < r[0].Length; j++)
                    if (r[i][j] != '*') r[i][j] = C(r, i, j);
            for (int i = 0; i < r.Length; i++)
            {
                for (int j = 0; j < r[0].Length; j++)
                    Console.Write(r[i][j]);
                Console.WriteLine();
            } return r;
        } 
        static void Main(string[] args) 
        { 
            G(new int[] { 3, 4, 3, 1, 1, 4, 2, 3, 3, 2 }); 
        }
    }
}

Answer 13

K, 175

f:{g::(y;x)#(x*y)#"x";{.[`g;x;:;"*"]}@'-1+|:'(_(#z)%2;2)#z;{if[~"0"~z;$["x"=g .(x;y);.[`g;(x;y);:;z];]]}.'i,'$s:+/'{"*"=g . x}''{,/((x-1)+!3),\:/:(y-1)+!3}.'i:,/(!x),\:/:!y;g}

.

k)f[5;5;1 3 3 5 2 4]
"xxxxx"
"11xxx"
"*21xx"
"2*21x"
"12*1x"
k)f[3;4;3 1 1 4 2 3 3 2]
"x2*"
"13*"
"2*2"
"*21"