DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
  1. DZone
  2. Data Engineering
  3. AI/ML
  4. Algorithms Explained: Minesweeper

Algorithms Explained: Minesweeper

Cagdas Basaraner user avatar by
Cagdas Basaraner
·
Feb. 09, 15 · Interview
Like (0)
Save
Tweet
Share
30.46K Views

Join the DZone community and get the full member experience.

Join For Free

This blog post explains the essential algorithms for the well-known Windows game "Minesweeper."

Game Rules

  1. The board is a two-dimensional space, which has a predetermined number of mines.
  2. Cells have two states, opened and closed.
  3. If you left-click on a closed cell:
    1. Cell is empty and opened. 
      1. If neighbor cell(s) have mine(s), this opened cell shows neighbor mine count.
      2. If neighbor cells have no mines, all neighbor cells are opened automatically.
    2. Cell has a mine, game ends with FAIL.
  4. If you right-click on a closed cell, you put a flag which shows that "I know this cell has a mine".
  5. If you multi-click (both right and left click) on a cell which is opened and has at least one mine on its neighbors:
    1. If neighbor cells' total flag count equals to this multi-clicked cell's count and predicted mine locations are true, all closed and unflagged neighbor cells are opened automatically.
    2. If neighbor cells' total flag count equals to this multi-clicked cell's count and at least one predicted mine location is wrong, game ends with FAIL.
  6. If all cells (without mines) are opened using left clicks and/or multi-clicks, game ends with SUCCESS.

Data Structures

We may think of each cell as a UI structure (e.g. button), which has the following attributes:

  • colCoord = 0 to colCount
  • rowCoord = 0 to rowCount
  • isOpened = true / false   (default false)
  • hasFlag    = true / false    (default false)
  • hasMine  = true / false    (default false)
  • neighborMineCount  0 to 8  (default 0, total count of mines on neighbor cells)

So, we have a two-dimensional "Button[][] cells" data structure to handle game actions.

Algorithms

Before Start:

  1. Assign mines to cells randomly (set hasMine=true) .
  2. Calculate neighborMineCount values for each cell, which have hasMine=false. (This step may be done for each clicked cell while game continues but it may be inefficient.)

Note 1: Neighbor cells should be accessed with the coordinates:

{(colCoord-1, rowCoord-1),(colCoord-1, rowCoord),(colCoord-1, rowCoord+1),(colCoord, rowCoord-1),(colCoord, rowCoord+1),(colCoord+1, rowCoord-1),(colCoord+1, rowCoord),(colCoord+1, rowCoord+1)}

And don't forget that neighbor cell counts may be 3 (for corner cells), 5 (for edge cells) or 8 (for middle cells).

Note 2: It's recommended to handle mouse clicks with "mouse release" actions instead of "mouse pressed/click" actions, otherwise a left or right click may be understood as a multi-click or vice versa.

Right Click on a Cell:

  • If cell isOpened=true, do nothing.
  • If cell isOpened=false, set cell hasFlag=true and show a flag on the cell. 

Left Click on a Cell:

  • If cell isOpened=true, do nothing.
  • If cell isOpened=false:
    • If cell hasMine=true, game over.
    • If cell hasMine=false:
      • If cell has neighborMineCount > 0, set isOpened=true, show neighborMineCount on the cell. If all cells which hasMine=false are opened, end game with SUCCESS.
      • If cell has neighborMineCount == 0, set isOpened=true, call Left Click on a Cell for all neighbor cells, which hasFlag=false and isOpened=false.

Note: The last step may be implemented with a recursive call or by using a stacked data structure.

Multi Click (both Left and Right Click) on a Cell:

  • If cell isOpened=false, do nothing.
  • If cell isOpened=true:
    • If cell neighborMineCount == 0, no nothing.
    • If cell neighborMineCount > 0:
      • If cell neighborMineCount != "neighbor hasFlag=true cell count", do nothing.
      • If cell neighborMineCount == "neighbor hasFlag=true cell count":
        • If all neighbor hasFlag=true cells are not hasMine=true, game over.
        • If all neighbor hasFlag=true cells are hasMine=true (every flag is put on correct cell), call Left Click on a Cell for all neighbor cells, which hasFlag=false and isOpened=false.

Note: The last step may be implemented with a recursive call or by using a stacked data structure.

Neighbors (app) Algorithm

Published at DZone with permission of Cagdas Basaraner, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • Unleashing the Power of JavaScript Modules: A Beginner’s Guide
  • Core Machine Learning Metrics
  • Exploring the Benefits of Cloud Computing: From IaaS, PaaS, SaaS to Google Cloud, AWS, and Microsoft
  • Public Cloud-to-Cloud Repatriation Trend

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends: