{"id":983,"date":"2010-09-02T00:00:00","date_gmt":"2010-09-02T00:00:00","guid":{"rendered":"https:\/\/test.simple-talk.com\/uncategorized\/minesweeper-in-t-sql\/"},"modified":"2021-09-29T16:21:57","modified_gmt":"2021-09-29T16:21:57","slug":"minesweeper-in-t-sql","status":"publish","type":"post","link":"https:\/\/www.red-gate.com\/simple-talk\/databases\/sql-server\/t-sql-programming-sql-server\/minesweeper-in-t-sql\/","title":{"rendered":"Minesweeper in T-SQL"},"content":{"rendered":"
\n

Whatever happened to the idea that programming in TSQL can be fun? A Simple-Talk reader contributes an article to remind us all that there is more to TSQL than wrestling with DMVs and pummelling recalcitrant correlated subqueries. <\/p>\n

\/* As a fun exercise I decided to program Minesweeper in T-SQL. I think it worked out quite nicely, so I’d like to share it with the world. But first, for anyone who doesn’t know what minesweeper is, a description is available here<\/a>. <\/p>\n<\/p>\n

\"1132-img20.gif\"<\/p>\n

I’ve used SQL Server Management Studio 2008 Express, but other versions should work as well (although the layout of the resultgrid might require some work).<\/p>\n

I wanted a minefield that was variable in length and width, so I created three tables: *\/<\/p>\n

CREATE TABLE Grid <\/p>\n

    (<\/p>\n

     X INT NOT NULL,          — X coordinate<\/p>\n

     Y INT NOT NULL,          — Y coordinate<\/p>\n

     S INT NULL,              — Status, see the user defined function udf_S<\/p>\n

     CONSTRAINT PK_Grid PRIMARY KEY (X ASC, Y ASC)<\/p>\n

    )<\/p>\n<\/p>\n

CREATE TABLE Mine<\/p>\n

    (<\/p>\n

     X INT NOT NULL,          — X coordinate<\/p>\n

     Y INT NOT NULL,          — Y coordinate<\/p>\n

     CONSTRAINT PK_Mine PRIMARY KEY (X ASC, Y ASC)<\/p>\n

    )<\/p>\n<\/p>\n

\/* The setting table will only ever hold one record *\/<\/p>\n

CREATE TABLE Settings <\/p>\n

    (<\/p>\n

     MaxX INT NOT NULL,       — Number of rows<\/p>\n

     MaxY INT NOT NULL,       — Number of columns<\/p>\n

     NumberOfMines INT NOT NULL<\/p>\n

    )<\/p>\n<\/p>\n

\/* Inserting some default values *\/<\/p>\n

INSERT  INTO Settings <\/div>\n

VALUES  (10, 10, 10)<\/p>\n<\/p>\n

GO<\/p>\n<\/p>\n

CREATE FUNCTION udf_S (@S INT)<\/p>\n

RETURNS CHAR(1)<\/p>\n

\/* A user defined function for the visual representation of the status *\/AS <\/div>\n

    BEGIN<\/p>\n

        RETURN (CASE<\/p>\n

                  WHEN @S = -100 THEN ‘F’       –Flagged<\/p>\n

                  WHEN @S = -10 THEN ‘S’        –Safe<\/p>\n

                  WHEN @S = -1 THEN ‘?’         –Unknown<\/p>\n

                  WHEN @S = 0 THEN ”           –No mines in the vicinity<\/p>\n

                  WHEN @S = 9 THEN ‘M’          –Exploded mine<\/p>\n

                  ELSE CONVERT(CHAR(1),@S)      <\/p>\n

–Number of mines in the vicinity <\/div>\n

            END<\/p>\n

                  )<\/p>\n

    END<\/p>\n<\/p>\n

GO    <\/p>\n<\/p>\n

CREATE PROCEDURE p_Initialize<\/p>\n

    (<\/p>\n

     @MaxX INT = NULL,<\/p>\n

     @MaxY INT = NULL,<\/p>\n

     @NumberOfMines INT = NULL,<\/p>\n

     @Seed INT = NULL<\/p>\n

    )<\/p>\n

\/* Initializing the game by creating the grid and randomly dropping the mines. I included a @seed parameter to be able to create the same map multiple times. If you call the procedure without any parameters he’ll use the same as last game, except the seed naturally *\/ <\/div>\n

AS <\/p>\n

    BEGIN<\/p>\n

        UPDATE  Settings<\/p>\n

        SET     MaxX = ISNULL(@MaxX, MaxX),<\/p>\n

                MaxY = ISNULL(@MaxY, MaxY),<\/p>\n

                NumberOfMines = ISNULL(@NumberOfMines, NumberOfMines)<\/p>\n

            <\/p>\n

        SELECT  @MaxX = MaxX,<\/p>\n

                @MaxY = MaxY,<\/p>\n

                @NumberOfMines = NumberOfMines<\/p>\n

        FROM    Settings<\/p>\n<\/p>\n

        TRUNCATE TABLE Mine<\/p>\n

        TRUNCATE TABLE Grid<\/p>\n

  <\/p>\n

        DECLARE @x INT<\/p>\n

        DECLARE @y INT<\/p>\n

<\/div>\n

\/* Creating records to represent the squares of the grid *\/        <\/p>\n

        SET @x = 1 <\/div>\n

        WHILE @x <= @MaxX <\/p>\n

            BEGIN<\/p>\n

                SET @y = 1<\/p>\n

                WHILE @y <= @MaxY <\/p>\n

                    BEGIN<\/p>\n

                        INSERT  INTO grid<\/p>\n

                        VALUES  (@x, @y, -1)<\/p>\n

                        SET @y = @y + 1<\/p>\n

                    END<\/p>\n

                SET @x = @x + 1<\/p>\n

            END<\/p>\n

\/* Setting the seed if necessary *\/
        IF @seed IS NOT NULL <\/div>\n

            SET @x = RAND(@seed)<\/p>\n<\/p>\n

\/* Dropping mines, but never on the same square *\/<\/p>\n

        WHILE @NumberOfMines > 0 <\/p>\n

            BEGIN<\/p>\n

                SET @x = FLOOR(RAND() * @MaxX) + 1<\/p>\n

                SET @y = FLOOR(RAND() * @MaxY) + 1<\/p>\n

            <\/p>\n

                IF (SELECT  COUNT(*)<\/p>\n

                    FROM    mine<\/p>\n

                    WHERE   x = @x<\/p>\n

                            AND y = @y<\/p>\n

                   ) = 0 <\/p>\n

                    BEGIN<\/p>\n

                        INSERT  INTO Mine<\/p>\n

                        VALUES  (@x, @y)<\/p>\n

                        SET @NumberOfMines = @NumberOfMines – 1<\/p>\n

                    END<\/p>\n

            END   <\/p>\n

    END<\/p>\n

    <\/p>\n

 GO<\/p>\n

  <\/p>\n

CREATE PROCEDURE p_Draw<\/p>\n

\/* Using a bit of dynamic SQL to draw the grid *\/ <\/div>\n

AS <\/p>\n

    BEGIN<\/p>\n

        DECLARE @sql VARCHAR(MAX)<\/p>\n<\/p>\n

        SELECT  @sql = ISNULL(@sql + ‘, ‘ + CHAR(13) + CHAR(9), ‘SELECT ‘)<\/p>\n

                + ‘MAX(CASE WHEN Y = ‘ + CONVERT(VARCHAR(3), y)<\/p>\n

                + ‘ THEN dbo.udf_S(S) END) as [‘ + CONVERT(VARCHAR(3), y)<\/p>\n

                + ‘]’<\/p>\n

        FROM    grid<\/p>\n

        GROUP BY y<\/p>\n

        ORDER BY y<\/p>\n<\/p>\n

        SET @sql = @sql + CHAR(13) + ‘FROM GRID<\/p>\n

      GROUP BY X<\/p>\n

      ORDER BY X’<\/p>\n

      <\/p>\n

        –PRINT @sql  –Uncomment this to see the SQL statement generated<\/p>\n

        EXEC (@sql)<\/p>\n

    END<\/p>\n

GO<\/p>\n<\/p>\n

CREATE PROCEDURE p_MarkSafeSquares<\/p>\n

\/* Mark all unexplored squares next to a square with no mines in the vicinity (a blank square) See procedure p_Explore *\/ <\/div>\n

AS <\/p>\n

    UPDATE  grid<\/p>\n

    SET     S = -10<\/p>\n

    FROM    (SELECT g2.x,<\/p>\n

                    g2.y<\/p>\n

             FROM   grid g1<\/p>\n

                    INNER JOIN grid g2 ON g1.x – g2.x BETWEEN -1 AND 1<\/p>\n

                                          AND g1.y – g2.y BETWEEN -1 AND 1<\/p>\n

             WHERE  g1.S = 0<\/p>\n

                    AND g2.S = -1<\/p>\n

            ) subset<\/p>\n

    WHERE   subset.x = grid.X<\/p>\n

            AND subset.y = grid.y<\/p>\n<\/p>\n

GO<\/p>\n<\/p>\n

CREATE PROCEDURE p_ExploreSafeSquares (@count INT OUTPUT)<\/p>\n

\/* Explore all squares marked as safe. See procedure p_Explore *\/ <\/div>\n

AS –First update all safe squares with mines in the vicinity<\/p>\n

    UPDATE  Grid<\/p>\n

    SET     S = MinesDetected<\/p>\n

    FROM    (SELECT g.x,<\/p>\n

                    g.y,<\/p>\n

                    COUNT(*) AS MinesDetected<\/p>\n

             FROM   Grid g<\/p>\n

                    INNER JOIN Mine m ON g.x – m.x BETWEEN -1 AND 1<\/p>\n

                                         AND g.y – m.y BETWEEN -1 AND 1<\/p>\n

             WHERE  S = -10<\/p>\n

             GROUP BY g.x,<\/p>\n

                    g.y<\/p>\n

            ) s1<\/p>\n

    WHERE   s1.x = grid.x<\/p>\n

            AND s1.y = grid.y<\/p>\n

      <\/p>\n

      –Determine if the procedure should be run again <\/p>\n

    SELECT  @count = COUNT(*)<\/p>\n

    FROM    grid<\/p>\n

    WHERE   s = -10<\/p>\n

    <\/p>\n

      –Second, update all other safe squares to blank squares    <\/p>\n

    UPDATE  Grid<\/p>\n

    SET     S = 0<\/p>\n

    WHERE   S = -10<\/p>\n

      <\/p>\n

GO<\/p>\n<\/p>\n

CREATE PROCEDURE p_Explore (@x INT, @y INT)<\/p>\n

\/* Expore an unknown square *\/ <\/div>\n

AS <\/p>\n

    BEGIN<\/p>\n

        IF (SELECT  COUNT(*)<\/p>\n

            FROM    Grid<\/p>\n

            WHERE   @x = x<\/p>\n

                    AND @y = y<\/p>\n

                    AND S = -100<\/p>\n

           ) = 0 –Check if a square is flagged<\/p>\n

            IF (SELECT  COUNT(*)<\/p>\n

                FROM    Mine<\/p>\n

                WHERE   @x = x<\/p>\n

                        AND @y = y<\/p>\n

               ) = 0 –Check if there’s a mine<\/p>\n

                BEGIN<\/p>\n

                    DECLARE @count INT<\/p>\n<\/p>\n

                    SET @count = (SELECT    COUNT(*)<\/p>\n

                                  FROM      (SELECT x,<\/p>\n

                                                    y<\/p>\n

                                             FROM   Mine<\/p>\n

                                             WHERE  x – @x BETWEEN -1 AND 1<\/p>\n

                                                    AND y – @y BETWEEN -1 AND 1<\/p>\n

                                             GROUP BY x,<\/p>\n

                                                    y<\/p>\n

                                            ) subset<\/p>\n

                                 ) <\/p>\n

–Count the number of mines in the vicinity<\/p>\n<\/p>\n

–Update the square to the number of mines in the vicinity<\/p>\n

                    UPDATE  Grid<\/p>\n

                    SET     S = @count<\/p>\n

                    WHERE   x = @x<\/p>\n

                            AND y = @y<\/p>\n

                        <\/div>\n

\/* Here’s where the fun starts! In another language you would probably use recursion to solve this square by square, but with a single update you can explore multiple squares that you know are safe. It’s probably possible to do this in a single update instead of the 3 sequential updates, but I’ll leave that up to someone else. *\/<\/p>\n

                    DECLARE @BlankSquares INT<\/p>\n

                    IF @count = 0 <\/p>\n

                        SET @BlankSquares = 1<\/p>\n

                              <\/p>\n

                    WHILE @BlankSquares > 0 <\/p>\n

                        BEGIN<\/p>\n

                            EXEC p_MarkSafeSquares<\/p>\n

                            EXEC p_ExploreSafeSquares @BlankSquares OUTPUT<\/p>\n

                        END<\/p>\n

                END<\/p>\n

            ELSE <\/p>\n

                        –A mine was hit!<\/p>\n

                UPDATE  Grid<\/p>\n

                SET     S = 9<\/p>\n

                WHERE   x = @x<\/p>\n

                        AND y = @y<\/p>\n

    END<\/p>\n<\/p>\n

GO<\/p>\n<\/p>\n

CREATE PROCEDURE p_GameState<\/p>\n

\/* Showing the gamestate *\/ <\/div>\n

AS <\/p>\n

    BEGIN<\/p>\n

        DECLARE @NumberOfMines INT<\/p>\n

        DECLARE @MaxX INT<\/p>\n

        DECLARE @MaxY INT<\/p>\n

      <\/p>\n

        SELECT  @NumberOfMines = NumberOfMines,<\/p>\n

                @MaxX = MaxX,<\/p>\n

                @MaxY = MaxY<\/p>\n

        FROM    Settings<\/p>\n

      <\/p>\n

        DECLARE @SquaresExplored INT,<\/p>\n

            @MinesExploded INT,<\/p>\n

            @SquaresFlagged INT<\/p>\n

      <\/p>\n

        SELECT  @SquaresExplored = SUM(CASE WHEN S BETWEEN 0 AND 8 THEN 1<\/p>\n

                                            ELSE 0<\/p>\n

                                       END),<\/p>\n

                @MinesExploded = SUM(CASE WHEN S = 9 THEN 1<\/p>\n

                                          ELSE 0<\/p>\n

                                     END),<\/p>\n

                @SquaresFlagged = SUM(CASE WHEN S = -100 THEN 1<\/p>\n

                                           ELSE 0<\/p>\n

                                      END)<\/p>\n

        FROM    Grid<\/p>\n

        <\/p>\n

        SELECT  @SquaresExplored AS SquaresExplored,<\/p>\n

                @MinesExploded AS MinesExploded,<\/p>\n

                @SquaresFlagged AS SquaresFlagged,<\/p>\n

                @NumberOfMines AS NumberOfMines,<\/p>\n

                @MaxX * @MaxY AS TotalSquares,<\/p>\n

                CASE WHEN @MinesExploded > 0 THEN ‘You lost!’<\/p>\n

                     WHEN @SquaresExplored + @NumberOfMines = @MaxX * @MaxY<\/p>\n

                     THEN ‘You won!’<\/p>\n

                     ELSE ‘Keep on playing!’<\/p>\n

                END AS GameState      <\/p>\n

    END<\/p>\n<\/p>\n

GO<\/p>\n<\/p>\n

CREATE PROCEDURE p_flag (@X INT, @Y INT)<\/p>\n

\/* A procedure to flag\/unflag an unknown square as suspect *\/ <\/div>\n

AS <\/p>\n

    BEGIN<\/p>\n

        UPDATE  Grid<\/p>\n

        SET     S = CASE WHEN S = -1 THEN -100  –Flag when unknown<\/p>\n

                         WHEN S = -100 THEN -1  –Unflag when flagged<\/p>\n

                         ELSE S                             –Otherwise no change<\/p>\n

                    END<\/p>\n

        WHERE   @x = X<\/p>\n

                AND @y = y<\/p>\n

                  <\/p>\n

    END<\/p>\n<\/p>\n

GO<\/p>\n<\/p>\n

CREATE PROCEDURE E (@X INT, @Y INT)<\/p>\n

\/* A procedure with a very short name to play the game. E for Explore *\/ <\/div>\n

AS <\/p>\n

    BEGIN<\/p>\n

        EXEC p_Explore @X, @Y<\/p>\n

        EXEC p_Draw<\/p>\n

        EXEC p_GameState<\/p>\n

    END<\/p>\n<\/p>\n

GO<\/p>\n<\/p>\n

CREATE PROCEDURE F (@X INT, @Y INT)<\/p>\n

\/* A procedure with a very short name to play the game. F for Flag *\/ <\/div>\n

AS <\/p>\n

    BEGIN<\/p>\n

        EXEC p_Flag @X, @Y<\/p>\n

        EXEC p_Draw<\/p>\n

        EXEC p_GameState<\/p>\n

    END<\/p>\n<\/p>\n

GO<\/p>\n<\/p>\n

CREATE PROCEDURE p_Solve1<\/p>\n

\/* It’s quite easy to write SQL statements to help clear the minefield. This one flags the only non-explored square next to a 1. *\/ <\/div>\n

AS <\/p>\n

    UPDATE  Grid<\/p>\n

    SET     S = -100<\/p>\n

    FROM    (SELECT<\/p>\n

      DISTINCT      x2,<\/p>\n

                    y2<\/p>\n

             FROM   (SELECT x1,<\/p>\n

                            y1,<\/p>\n

                            MAX(x2) x2,<\/p>\n

                            MAX(y2) y2<\/p>\n

                     FROM   (SELECT g1.x AS x1,<\/p>\n

                                    g1.y AS y1,<\/p>\n

                                    g2.x AS x2,<\/p>\n

                                    g2.y AS y2<\/p>\n

                             FROM   grid g1<\/p>\n

                                    INNER JOIN grid g2 ON g1.x – g2.X BETWEEN -1 AND 1<\/p>\n

                                                          AND g1.y – g2.y BETWEEN -1 AND 1<\/p>\n

                             WHERE  g1.S = 1<\/p>\n

                                    AND g2.S IN (-1, -100)<\/p>\n

                            ) s1<\/p>\n

                     GROUP BY x1,<\/p>\n

                            y1<\/p>\n

                     HAVING COUNT(*) = 1<\/p>\n

                    ) s2<\/p>\n

            ) s3<\/p>\n

    WHERE   grid.x = s3.x2<\/p>\n

            AND grid.y = s3.y2<\/p>\n

            AND grid.s = -1<\/p>\n

GO<\/p>\n<\/p>\n

EXEC p_Initialize 10, 10, 10, 10<\/p>\n

EXEC e 1, 1<\/p>\n

\"1132-Minesweeper1.jpg\"<\/p>\n

–the rest of the solution to ‘p_Initialize 10, 10, 10, 10’ <\/p><\/div>\n

\/*
EXEC e 7, 6 <\/div>\n

EXEC f 8, 3 <\/p>\n

EXEC e 8, 4 <\/p>\n

EXEC e 9, 3<\/p>\n

\"1132-img1C.gif\"
                    \/* “You lost” *\/<\/div>\n

EXEC f 10, 1 <\/p>\n

EXEC e 10, 2<\/p>\n

EXEC e 10, 3<\/p>\n

EXEC f 7, 5<\/p>\n

EXEC e 8, 5<\/p>\n

EXEC f 9, 5<\/p>\n

EXEC e 5, 6<\/p>\n

EXEC e 6, 6<\/p>\n

EXEC f 4, 6<\/p>\n

EXEC e 3, 6<\/p>\n

EXEC f 2, 6<\/p>\n

EXEC e 1, 6<\/p>\n

EXEC e 6, 7<\/p>\n

EXEC e 5, 7<\/p>\n

EXEC e 4, 7<\/p>\n

EXEC e 3, 7<\/p>\n

EXEC e 3, 8<\/p>\n

EXEC e 4, 8<\/p>\n

EXEC f 2, 7<\/p>\n

EXEC e 1, 7<\/p>\n

EXEC f 10, 8<\/p>\n

EXEC e 8, 7<\/p>\n

EXEC e 9, 7<\/p>\n

EXEC e 10, 7<\/p>\n

EXEC f 7, 7<\/p>\n

EXEC f 8, 6<\/p>\n

EXEC e 10, 5<\/p>\n

EXEC e 10, 6<\/p>\n

EXEC e 9, 6<\/p>\n

*\/<\/p>\n<\/p>\n

–A bigger one<\/p>\n

\/*<\/p>\n

EXEC p_Initialize 30, 30, 60, 10<\/p>\n

exec e 1,1<\/p>\n

*\/<\/p>\n<\/p>\n

–A really big one, with only a few mines, to see how long it takes the ‘auto explore’ to clear the field. (about 32 sec on my PC)<\/p>\n

\/*<\/p>\n

EXEC p_Initialize 50, 50, 10, 10<\/p>\n

EXEC e 1,1<\/p>\n

*\/<\/p>\n

\/* Although there are situations where the field can’t be cleared without guessing a lot can probably solved with procedures like p_Solve1. It might even be possible to have a procedure make an educated guess.<\/p>\n

Competition:<\/strong> <\/div>\n<\/p>\n

Create a series of procedures that can solve a multitude of grids. Submit them as comments to this article. (forget the pretty formatting, this happens later)  They will be judged on effectiveness, creativity and style!  The winner will get a license for SQL Prompt Pro, or SQL Data Generator, whichever they prefer *\/<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

Whatever happened to the idea that programming in TSQL can be fun? A Simple-Talk reader contributes an article to remind us all that there is more to TSQL than wrestling with DMVs and pumelling recalcitrant correlated subqueries.…<\/p>\n","protected":false},"author":14783,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[143531],"tags":[4150,4183,4252,4190],"coauthors":[],"class_list":["post-983","post","type-post","status-publish","format-standard","hentry","category-t-sql-programming-sql-server","tag-sql","tag-t-sql","tag-t-sql-programming","tag-tsql"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/983","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/users\/14783"}],"replies":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/comments?post=983"}],"version-history":[{"count":5,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/983\/revisions"}],"predecessor-version":[{"id":92546,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/983\/revisions\/92546"}],"wp:attachment":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/media?parent=983"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/categories?post=983"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/tags?post=983"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/coauthors?post=983"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}