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
Please enter at least three characters to search
Refcards Trend Reports
Events Video Library
Refcards
Trend Reports

Events

View Events Video Library

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

Last call! Secure your stack and shape the future! Help dev teams across the globe navigate their software supply chain security challenges.

Modernize your data layer. Learn how to design cloud-native database architectures to meet the evolving demands of AI and GenAI workloads.

Releasing software shouldn't be stressful or risky. Learn how to leverage progressive delivery techniques to ensure safer deployments.

Avoid machine learning mistakes and boost model performance! Discover key ML patterns, anti-patterns, data strategies, and more.

Related

  • Predicting Ad Viewability With XGBoost Regressor Algorithm
  • Floyd's Cycle Algorithm for Fraud Detection in Java Systems
  • Metal and the Simulated Annealing Algorithm
  • Balancing Security and UX With Iterative Experimentation

Trending

  • A Guide to Developing Large Language Models Part 1: Pretraining
  • AWS to Azure Migration: A Cloudy Journey of Challenges and Triumphs
  • *You* Can Shape Trend Reports: Join DZone's Software Supply Chain Security Research
  • Microsoft Azure Synapse Analytics: Scaling Hurdles and Limitations
  1. DZone
  2. Data Engineering
  3. AI/ML
  4. Algorithms Explained: Minesweeper

Algorithms Explained: Minesweeper

By 
Cagdas Basaraner user avatar
Cagdas Basaraner
·
Feb. 09, 15 · Interview
Likes (0)
Comment
Save
Tweet
Share
32.7K 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.

Related

  • Predicting Ad Viewability With XGBoost Regressor Algorithm
  • Floyd's Cycle Algorithm for Fraud Detection in Java Systems
  • Metal and the Simulated Annealing Algorithm
  • Balancing Security and UX With Iterative Experimentation

Partner Resources

×

Comments
Oops! Something Went Wrong

The likes didn't load as expected. Please refresh the page and try again.

ABOUT US

  • About DZone
  • Support and feedback
  • Community research
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

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

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 3343 Perimeter Hill Drive
  • Suite 100
  • Nashville, TN 37211
  • support@dzone.com

Let's be friends:

Likes
There are no likes...yet! 👀
Be the first to like this post!
It looks like you're not logged in.
Sign in to see who liked this post!