Minesweeper Solver
Given a 2D array arr[][] of dimensions N*M, representing a minesweeper matrix, where each cell contains an integer from the range [0, 9], representing the number of mines in itself and all the eight cells adjacent to it, the task is to solve the minesweeper and uncover all the mines in the matrix. Print ‘X’ for the cell containing a mine and ‘_’ for all the other empty cells. If it is not possible to solve the minesweeper, then print “-1”.
Examples:
Input:
arr[][] = {{1, 1, 0, 0, 1, 1, 1},
{2, 3, 2, 1, 1, 2, 2},
{3, 5, 3, 2, 1, 2, 2},
{3, 6, 5, 3, 0, 2, 2},
{2, 4, 3, 2, 0, 1, 1},
{2, 3, 3, 2, 1, 2, 1},
{1, 1, 1, 1, 1, 1, 0}}.
Output:
_ _ _ _ _ _ _
x _ _ _ _ x _
_ x x _ _ _ x
x _ x _ _ _ _
_ x x _ _ _ x
_ _ _ _ _ _ _
_ x _ _ x _ _Input:
arr[][] = {{0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 1},
{0, 0, 0, 0, 0, 1, 1},
{0, 0, 1, 1, 1, 1, 1},
{0, 0, 2, 2, 2, 0, 0},
{0, 0, 2, 2, 2, 0, 0},
{0, 0, 1, 1, 1, 0, 0}}
Output:
_ _ _ _ _ _ _
_ _ _ _ _ _ _
_ _ _ _ _ _ x
_ _ _ _ _ _ _
_ _ _ x _ _ _
_ _ _ x _ _ _
_ _ _ _ _ _ _
Input Generation: To solve the given minesweeper matrix arr[][], it must be a valid input i.e., the minesweeper matrix must be solvable. Therefore, the input matrix is generated in generateMineField() function. Follow the below steps to generate the input minesweeper matrix:
- The inputs for the generation of input are the size of the minefield N and M and also probability P (or density) of the minefield.
- A probability P is equal to 0 if there are no mines in the minefield and P is equal to 100 if all the cells are mines in the minefield.
- A random number is chosen for each cell and if the random number is less than P, a mine is assigned to the grid and a boolean array mines[][] is generated.
- The input to the constraint solver is the status of each grid which counts the mines of itself and the eight cells around it.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Stores the number of rows // and columns of the matrix int N, M; // Stores the final generated input int arr[100][100]; // Direction arrays int dx[9] = { -1, 0, 1, -1, 0, 1, -1, 0, 1 }; int dy[9] = { 0, 0, 0, -1, -1, -1, 1, 1, 1 }; // Function to check if the // cell location is valid bool isValid( int x, int y) { // Returns true if valid return (x >= 0 && y >= 0 && x < N && y < M); } // Function to generate a valid minesweeper // matrix of size ROW * COL with P being // the probability of a cell being a mine void generateMineField( int ROW, int COL, int P) { // Generates the random // number every time srand ( time (NULL)); int rand_val; // Stores whether a cell // contains a mine or not int mines[ROW][COL]; // Iterate through each cell // of the matrix mine for ( int x = 0; x < ROW; x++) { for ( int y = 0; y < COL; y++) { // Generate a random value // from the range [0, 100] rand_val = rand () % 100; // If rand_val is less than P if (rand_val < P) // MArk mines[x][y] as True mines[x][y] = true ; // Otherwise, mark // mines[x][y] as False else mines[x][y] = false ; } } cout << "Generated Input:\n" ; // Iterate through each cell (x, y) for ( int x = 0; x < ROW; x++) { for ( int y = 0; y < COL; y++) { arr[x][y] = 0; // Count the number of mines // around the cell (x, y) // and store in arr[x][y] for ( int k = 0; k < 9; k++) { // If current adjacent cell is valid if (isValid(x + dx[k], y + dy[k]) && (mines[x + dx[k]][y + dy[k]])) arr[x][y]++; } // Print the value at // the current cell cout << arr[x][y] << " " ; } cout << endl; } } // Driver Code int main() { N = 7, M = 7; int P = 20; // Function call to generate // a valid minesweeper matrix generateMineField(N, M, 15); } |
Java
import java.util.Random; public class Main { // Stores the number of rows // and columns of the matrix static int N, M; // Stores the final generated input static int arr[][] = new int [ 100 ][ 100 ]; // Direction arrays static int dx[] = { - 1 , 0 , 1 , - 1 , 0 , 1 , - 1 , 0 , 1 }; static int dy[] = { 0 , 0 , 0 , - 1 , - 1 , - 1 , 1 , 1 , 1 }; // Function to check if the // cell location is valid static boolean isValid( int x, int y) { // Returns true if valid return (x >= 0 && y >= 0 && x < N && y < M); } // Function to generate a valid minesweeper // matrix of size ROW * COL with P being // the probability of a cell being a mine static void generateMineField( int ROW, int COL, int P) { // Generates the random // number every time Random random = new Random(); int rand_val; // Stores whether a cell // contains a mine or not boolean mines[][] = new boolean [ROW][COL]; // Iterate through each cell // of the matrix mine for ( int x = 0 ; x < ROW; x++) { for ( int y = 0 ; y < COL; y++) { // Generate a random value // from the range [0, 100] rand_val = random.nextInt( 100 ); // If rand_val is less than P if (rand_val < P) // MArk mines[x][y] as True mines[x][y] = true ; // Otherwise, mark // mines[x][y] as False else mines[x][y] = false ; } } System.out.println( "Generated Input:" ); // Iterate through each cell (x, y) for ( int x = 0 ; x < ROW; x++) { for ( int y = 0 ; y < COL; y++) { arr[x][y] = 0 ; // Count the number of mines // around the cell (x, y) // and store in arr[x][y] for ( int k = 0 ; k < 9 ; k++) { // If current adjacent cell is valid if (isValid(x + dx[k], y + dy[k]) && (mines[x + dx[k]][y + dy[k]])) arr[x][y]++; } // Print the value at // the current cell System.out.print(arr[x][y] + " " ); } System.out.println(); } } // Driver Code public static void main(String[] args) { N = 7 ; M = 7 ; int P = 20 ; // Function call to generate // a valid minesweeper matrix generateMineField(N, M, 15 ); } } |
Python3
# Python Equivalent import random import time # Stores the number of rows # and columns of the matrix N, M = 7 , 7 # Stores the final generated input arr = [[ 0 for _ in range (M)] for _ in range (N)] # Direction arrays dx = [ - 1 , 0 , 1 , - 1 , 0 , 1 , - 1 , 0 , 1 ] dy = [ 0 , 0 , 0 , - 1 , - 1 , - 1 , 1 , 1 , 1 ] # Function to check if the # cell location is valid def isValid(x, y): # Returns true if valid return (x > = 0 and y > = 0 and x < N and y < M) # Function to generate a valid minesweeper # matrix of size ROW * COL with P being # the probability of a cell being a mine def generateMineField(ROW, COL, P): # Generates the random # number every time random.seed(time.time()) # Stores whether a cell # contains a mine or not mines = [[ False for _ in range (COL)] for _ in range (ROW)] # Iterate through each cell # of the matrix mine for x in range (ROW): for y in range (COL): # Generate a random value # from the range [0, 100] rand_val = random.randint( 0 , 100 ) # If rand_val is less than P if rand_val < P: # MArk mines[x][y] as True mines[x][y] = True # Otherwise, mark # mines[x][y] as False else : mines[x][y] = False print ( "Generated Input:" ) # Iterate through each cell (x, y) for x in range (ROW): for y in range (COL): arr[x][y] = 0 # Count the number of mines # around the cell (x, y) # and store in arr[x][y] for k in range ( 9 ): # If current adjacent cell is valid if isValid(x + dx[k], y + dy[k]) and mines[x + dx[k]][y + dy[k]]: arr[x][y] + = 1 # Print the value at # the current cell print (arr[x][y], end = " " ) print () # Driver Code if __name__ = = "__main__" : P = 20 # Function call to generate # a valid minesweeper matrix generateMineField(N, M, 15 ) |
C#
using System; class MainClass { // Stores the number of rows // and columns of the matrix static int N, M; // Stores the final generated input static int [,] arr = new int [100,100]; // Direction arrays static int [] dx = { -1, 0, 1, -1, 0, 1, -1, 0, 1 }; static int [] dy = { 0, 0, 0, -1, -1, -1, 1, 1, 1 }; // Function to check if the // cell location is valid static bool IsValid( int x, int y) { // Returns true if valid return (x >= 0 && y >= 0 && x < N && y < M); } // Function to generate a valid minesweeper // matrix of size ROW * COL with P being // the probability of a cell being a mine static void GenerateMineField( int ROW, int COL, int P) { // Generates the random // number every time Random random = new Random(); int rand_val; // Stores whether a cell // contains a mine or not bool [,] mines = new bool [ROW, COL]; // Iterate through each cell // of the matrix mine for ( int x = 0; x < ROW; x++) { for ( int y = 0; y < COL; y++) { // Generate a random value // from the range [0, 100] rand_val = random.Next(100); // If rand_val is less than P if (rand_val < P) // Mark mines[x,y] as true mines[x, y] = true ; // Otherwise, mark // mines[x,y] as false else mines[x, y] = false ; } } Console.WriteLine( "Generated Input:" ); // Iterate through each cell (x, y) for ( int x = 0; x < ROW; x++) { for ( int y = 0; y < COL; y++) { arr[x, y] = 0; // Count the number of mines // around the cell (x, y) // and store in arr[x,y] for ( int k = 0; k < 9; k++) { // If current adjacent cell is valid if (IsValid(x + dx[k], y + dy[k]) && (mines[x + dx[k], y + dy[k]])) arr[x, y]++; } // Print the value at // the current cell Console.Write(arr[x, y] + " " ); } Console.WriteLine(); } } // Driver Code public static void Main( string [] args) { N = 7; M = 7; int P = 20; // Function call to generate // a valid minesweeper matrix GenerateMineField(N, M, 15); } } |
Javascript
// JS Equivalent // Stores the number of rows // and columns of the matrix const N = 7, M = 7; // Stores the final generated input let arr = []; for (let i = 0; i < N; i++) { arr.push([]); for (let j = 0; j < M; j++) { arr[i].push(0); } } // Direction arrays const dx = [-1, 0, 1, -1, 0, 1, -1, 0, 1]; const dy = [0, 0, 0, -1, -1, -1, 1, 1, 1]; // Function to check if the // cell location is valid function isValid(x, y) { // Returns true if valid return (x >= 0 && y >= 0 && x < N && y < M); } // Function to generate a valid minesweeper // matrix of size ROW * COL with P being // the probability of a cell being a mine function generateMineField(ROW, COL, P) { // Generates the random // number every time Math.random(); // Stores whether a cell // contains a mine or not let mines = []; for (let i = 0; i < ROW; i++) { mines.push([]); for (let j = 0; j < COL; j++) { mines[i].push( false ); } } // Iterate through each cell // of the matrix mine for (let x = 0; x < ROW; x++) { for (let y = 0; y < COL; y++) { // Generate a random value // from the range [0, 100] let rand_val = Math.floor(Math.random() * 100); // If rand_val is less than P if (rand_val < P) { // MArk mines[x][y] as True mines[x][y] = true ; // Otherwise, mark // mines[x][y] as False } else { mines[x][y] = false ; } } } console.log( "Generated Input:" ); // Iterate through each cell (x, y) for (let x = 0; x < ROW; x++) { ans = "" ; for (let y = 0; y < COL; y++) { arr[x][y] = 0; // Count the number of mines // around the cell (x, y) // and store in arr[x][y] for (let k = 0; k < 9; k++) { // If current adjacent cell is valid if (isValid(x + dx[k], y + dy[k]) && mines[x + dx[k]][y + dy[k]]) { arr[x][y] += 1; } } // Print the value at // the current cell ans = ans + arr[x][y]+ " " ; } console.log(ans); } } // Driver Code const P = 20; // Function call to generate // a valid minesweeper matrix generateMineField(N, M, 15); |
Generated Input: 0 1 1 1 1 1 1 1 3 3 3 2 2 1 1 2 2 2 2 2 1 1 2 2 2 1 1 0 1 2 1 1 1 1 1 1 3 2 2 1 1 1 1 3 2 2 1 1 1
Time Complexity: O(ROW*COL)
Auxiliary Space: O(ROW*COL)
Approach: The given problem can be solved using Backtracking. The idea is to iterate over each cell of a matrix, based on the information available from the neighboring cells, assign a mine to that cell or not.
Follow the below steps to solve the given problem:
- Initialize a matrix, say grid[][], and visited[][] to store the resultant grid and keep the track of visited cells while traversing the grid. Initialize all grid values as false.
- Declare a recursive function solveMineSweeper() to accept arrays arr[][], grid[][], and visited[][] as a parameter.
- If all the cells are visited and a mine is assigned to the cells satisfying the given input grid[][], then return true for the current recursive call.
- If all the cells are visited but the solution is not satisfying the input grid[], return false for the current recursive call.
- If the above two conditions are found to be false, then find an unvisited cell (x, y) and mark (x, y) as visited.
- If a mine can be assigned to the position (x, y), then perform the following steps:
- Mark grid[x][y] as true.
- Decrease the number of mine of the neighboring cells of (x, y) in the matrix arr[][] by 1.
- Recursively call for solveMineSweeper() with (x, y) having a mine and if it returns true, then a solution exists. Return true for the current recursive call.
- Otherwise, reset the position (x, y) i.e., mark grid[x][y] as false and increase the number of mines of the neighboring cells of (x, y) in the matrix arr[][] by 1.
- If the function solveMineSweeper() with (x, y) having no mine, returns true, then it means a solution exists. Return true from the current recursive call.
- If the recursive call in the above step returns false, that means the solution doesn’t exist. Therefore, return false from the current recursive calls.
- If the value returned by the function solveMineSweeper(grid, arr, visited) is true, then a solution exists. Print the matrix grid[][] as the required solution. Otherwise, print “-1”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Stores the number of rows // and columns in given matrix int N, M; // Maximum number of rows // and columns possible #define MAXM 100 #define MAXN 100 // Directional Arrays int dx[9] = { -1, 0, 1, -1, 0, 1, -1, 0, 1 }; int dy[9] = { 0, 0, 0, -1, -1, -1, 1, 1, 1 }; // Function to check if the // cell (x, y) is valid or not bool isValid( int x, int y) { return (x >= 0 && y >= 0 && x < N && y < M); } // Function to print the matrix grid[][] void printGrid( bool grid[MAXN][MAXM]) { for ( int row = 0; row < N; row++) { for ( int col = 0; col < M; col++) { if (grid[row][col]) cout << "x " ; else cout << "_ " ; } cout << endl; } } // Function to check if the cell (x, y) // is valid to have a mine or not bool isSafe( int arr[MAXN][MAXM], int x, int y) { // Check if the cell (x, y) is a // valid cell or not if (!isValid(x, y)) return false ; // Check if any of the neighbouring cell // of (x, y) supports (x, y) to have a mine for ( int i = 0; i < 9; i++) { if (isValid(x + dx[i], y + dy[i]) && (arr[x + dx[i]][y + dy[i]] - 1 < 0)) return ( false ); } // If (x, y) is valid to have a mine for ( int i = 0; i < 9; i++) { if (isValid(x + dx[i], y + dy[i])) // Reduce count of mines in // the neighboring cells arr[x + dx[i]][y + dy[i]]--; } return true ; } // Function to check if there // exists any unvisited cell or not bool findUnvisited( bool visited[MAXN][MAXM], int & x, int & y) { for (x = 0; x < N; x++) for (y = 0; y < M; y++) if (!visited[x][y]) return ( true ); return ( false ); } // Function to check if all the cells // are visited or not and the input array // is satisfied with the mine assignments bool isDone( int arr[MAXN][MAXM], bool visited[MAXN][MAXM]) { bool done = true ; for ( int i = 0; i < N; i++) { for ( int j = 0; j < M; j++) { done = done && (arr[i][j] == 0) && visited[i][j]; } } return (done); } // Function to solve the minesweeper matrix bool SolveMinesweeper( bool grid[MAXN][MAXM], int arr[MAXN][MAXM], bool visited[MAXN][MAXM]) { // Function call to check if each cell // is visited and the solved grid is // satisfying the given input matrix bool done = isDone(arr, visited); // If the solution exists and // and all cells are visited if (done) return true ; int x, y; // Function call to check if all // the cells are visited or not if (!findUnvisited(visited, x, y)) return false ; // Mark cell (x, y) as visited visited[x][y] = true ; // Function call to check if it is // safe to assign a mine at (x, y) if (isSafe(arr, x, y)) { // Mark the position with a mine grid[x][y] = true ; // Recursive call with (x, y) having a mine if (SolveMinesweeper(grid, arr, visited)) // If solution exists, then return true return true ; // Reset the position x, y grid[x][y] = false ; for ( int i = 0; i < 9; i++) { if (isValid(x + dx[i], y + dy[i])) arr[x + dx[i]][y + dy[i]]++; } } // Recursive call without (x, y) having a mine if (SolveMinesweeper(grid, arr, visited)) // If solution exists then return true return true ; // Mark the position as unvisited again visited[x][y] = false ; // If no solution exists return false ; } void minesweeperOperations( int arr[MAXN][MAXN], int N, int M) { // Stores the final result bool grid[MAXN][MAXM]; // Stores whether the position // (x, y) is visited or not bool visited[MAXN][MAXM]; // Initialize grid[][] and // visited[][] to false memset (grid, false , sizeof (grid)); memset (visited, false , sizeof (visited)); // If the solution to the input // minesweeper matrix exists if (SolveMinesweeper(grid, arr, visited)) { // Function call to print the grid[][] printGrid(grid); } // No solution exists else printf ( "No solution exists\n" ); } // Driver Code int main() { // Given input N = 7; M = 7; int arr[MAXN][MAXN] = { { 1, 1, 0, 0, 1, 1, 1 }, { 2, 3, 2, 1, 1, 2, 2 }, { 3, 5, 3, 2, 1, 2, 2 }, { 3, 6, 5, 3, 0, 2, 2 }, { 2, 4, 3, 2, 0, 1, 1 }, { 2, 3, 3, 2, 1, 2, 1 }, { 1, 1, 1, 1, 1, 1, 0 } }; // Function call to perform // generate and solve a minesweeper minesweeperOperations(arr, N, M); return 0; } |
Java
import java.util.*; public class Main { static int N, M; static final int MAXM = 100 ; static final int MAXN = 100 ; // Directional Arrays static int [] dx = { - 1 , 0 , 1 , - 1 , 0 , 1 , - 1 , 0 , 1 }; static int [] dy = { 0 , 0 , 0 , - 1 , - 1 , - 1 , 1 , 1 , 1 }; // Function to check if the // cell (x, y) is valid or not static boolean isValid( int x, int y) { return (x >= 0 && y >= 0 && x < N && y < M); } // Function to print the matrix grid[][] static void printGrid( boolean [][] grid) { for ( int row = 0 ; row < N; row++) { for ( int col = 0 ; col < M; col++) { if (grid[row][col]) System.out.print( "x " ); else System.out.print( "_ " ); } System.out.println(); } } // Function to check if the cell (x, y) // is valid to have a mine or not static boolean isSafe( int [][] arr, int x, int y) { // Check if the cell (x, y) is a // valid cell or not if (!isValid(x, y)) return false ; // Check if any of the neighbouring cell // of (x, y) supports (x, y) to have a mine for ( int i = 0 ; i < 9 ; i++) { if (isValid(x + dx[i], y + dy[i]) && (arr[x + dx[i]][y + dy[i]] - 1 < 0 )) return false ; } // If (x, y) is valid to have a mine for ( int i = 0 ; i < 9 ; i++) { if (isValid(x + dx[i], y + dy[i])) // Reduce count of mines in // the neighboring cells arr[x + dx[i]][y + dy[i]]--; } return true ; } // Function to check if there // exists any unvisited cell or not static boolean findUnvisited( boolean [][] visited, int [] x, int [] y) { for (x[ 0 ] = 0 ; x[ 0 ] < N; x[ 0 ]++) for (y[ 0 ] = 0 ; y[ 0 ] < M; y[ 0 ]++) if (!visited[x[ 0 ]][y[ 0 ]]) return true ; return false ; } // Function to check if all the cells // are visited or not and the input array // is satisfied with the mine assignments static boolean isDone( int [][] arr, boolean [][] visited) { boolean done = true ; for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < M; j++) { done = done && (arr[i][j] == 0 ) && visited[i][j]; } } return done; } // Function to solve the minesweeper matrix static boolean SolveMinesweeper( boolean [][] grid, int [][] arr, boolean [][] visited) { // Function call to check if each cell // is visited and the solved grid is // satisfying the given input matrix boolean done = isDone(arr, visited); // If the solution exists and // and all cells are visited if (done) return true ; int [] x = { 0 }; int [] y = { 0 }; // Function call to check if all // the cells are visited or not if (!findUnvisited(visited, x, y)) return false ; // Mark cell (x, y) as visited visited[x[ 0 ]][y[ 0 ]] = true ; // Function call to check if it is // safe to assign a mine at (x, y) if (isSafe(arr, x[ 0 ], y[ 0 ])) { // Mark the position with a mine grid[x[ 0 ]][y[ 0 ]] = true ; // Recursive call with (x, y) having a mine if (SolveMinesweeper(grid, arr, visited)) return true ; // Reset the position x, y grid[x[ 0 ]][y[ 0 ]] = false ; for ( int i = 0 ; i < 9 ; i++) { if (isValid(x[ 0 ] + dx[i], y[ 0 ] + dy[i])) arr[x[ 0 ] + dx[i]][y[ 0 ] + dy[i]]++; } } // Recursive call without (x, y) having a mine if (SolveMinesweeper(grid, arr, visited)) return true ; // If solution exists then return // true // Mark the position as unvisited again visited[x[ 0 ]][y[ 0 ]] = false ; // If no solution exists return false ; } public static void minesweeperOperations( int [][] arr, int N, int M) { // Stores the final result boolean [][] visited = new boolean [N][M]; // Stores whether the position // (x, y) is visited or not boolean [][] grid = new boolean [N][M]; // If the solution to the input // minesweeper matrix exists if (SolveMinesweeper(grid, arr, visited)) // Function call to print the grid[][] printGrid(grid); // No solution exists else System.out.println( "No solution exists" ); } public static void main(String[] args) { // Given input N = 7 ; M = 7 ; int [][] arr = { { 1 , 1 , 0 , 0 , 1 , 1 , 1 }, { 2 , 3 , 2 , 1 , 1 , 2 , 2 }, { 3 , 5 , 3 , 2 , 1 , 2 , 2 }, { 3 , 6 , 5 , 3 , 0 , 2 , 2 }, { 2 , 4 , 3 , 2 , 0 , 1 , 1 }, { 2 , 3 , 3 , 2 , 1 , 2 , 1 }, { 1 , 1 , 1 , 1 , 1 , 1 , 0 } }; minesweeperOperations(arr, N, M); } } |
Python3
# Import required modules import numpy as np # Directional Arrays dx = [ - 1 , 0 , 1 , - 1 , 0 , 1 , - 1 , 0 , 1 ] dy = [ 0 , 0 , 0 , - 1 , - 1 , - 1 , 1 , 1 , 1 ] # Function to check if the cell (x, y) is valid or not def isValid(x, y, N, M): return (x > = 0 and y > = 0 and x < N and y < M) # Function to print the matrix grid[][] def printGrid(grid): for row in grid: for cell in row: if cell: print ( "x" , end = " " ) else : print ( "_" , end = " " ) print () # Function to check if the cell (x, y) is valid to have a mine or not def isSafe(arr, x, y, N, M): # Check if the cell (x, y) is a valid cell or not if not isValid(x, y, N, M): return False # Check if any of the neighbouring cell of (x, y) supports (x, y) to have a mine for i in range ( 9 ): if isValid(x + dx[i], y + dy[i], N, M) and (arr[x + dx[i]][y + dy[i]] - 1 < 0 ): return False # If (x, y) is valid to have a mine for i in range ( 9 ): if isValid(x + dx[i], y + dy[i], N, M): # Reduce count of mines in the neighboring cells arr[x + dx[i]][y + dy[i]] - = 1 return True # Function to check if there exists any unvisited cell or not def findUnvisited(visited): for x in range ( len (visited)): for y in range ( len (visited[ 0 ])): if not visited[x][y]: return x, y return - 1 , - 1 # Function to check if all the cells are visited or not and the input array is satisfied with the mine assignments def isDone(arr, visited): done = True for i in range ( len (arr)): for j in range ( len (arr[ 0 ])): done = done and (arr[i][j] = = 0 ) and visited[i][j] return done # Function to solve the minesweeper matrix def SolveMinesweeper(grid, arr, visited, N, M): # Function call to check if each cell is visited and the solved grid is satisfying the given input matrix done = isDone(arr, visited) # If the solution exists and all cells are visited if done: return True x, y = findUnvisited(visited) # Function call to check if all the cells are visited or not if x = = - 1 and y = = - 1 : return False # Mark cell (x, y) as visited visited[x][y] = True # Function call to check if it is safe to assign a mine at (x, y) if isSafe(arr, x, y, N, M): # Mark the position with a mine grid[x][y] = True # Recursive call with (x, y) having a mine if SolveMinesweeper(grid, arr, visited, N, M): # If solution exists, then return true return True # Reset the position x, y grid[x][y] = False for i in range ( 9 ): if isValid(x + dx[i], y + dy[i], N, M): arr[x + dx[i]][y + dy[i]] + = 1 # Recursive call without (x, y) having a mine if SolveMinesweeper(grid, arr, visited, N, M): # If solution exists then return true return True # Mark the position as unvisited again visited[x][y] = False # If no solution exists return False # Function to perform generate and solve a minesweeper def minesweeperOperations(arr, N, M): # Stores the final result grid = np.zeros((N, M), dtype = bool ) # Stores whether the position (x, y) is visited or not visited = np.zeros((N, M), dtype = bool ) # If the solution to the input minesweeper matrix exists if SolveMinesweeper(grid, arr, visited, N, M): # Function call to print the grid[][] printGrid(grid) # No solution exists else : print ( "No solution exists" ) # Driver Code if __name__ = = "__main__" : # Given input N = 7 M = 7 arr = [ [ 1 , 1 , 0 , 0 , 1 , 1 , 1 ], [ 2 , 3 , 2 , 1 , 1 , 2 , 2 ], [ 3 , 5 , 3 , 2 , 1 , 2 , 2 ], [ 3 , 6 , 5 , 3 , 0 , 2 , 2 ], [ 2 , 4 , 3 , 2 , 0 , 1 , 1 ], [ 2 , 3 , 3 , 2 , 1 , 2 , 1 ], [ 1 , 1 , 1 , 1 , 1 , 1 , 0 ] ] # Function call to perform generate and solve a minesweeper minesweeperOperations(arr, N, M) |
C#
using System; public class Program { static int N, M; // Directional Arrays static int [] dx = { -1, 0, 1, -1, 0, 1, -1, 0, 1 }; static int [] dy = { 0, 0, 0, -1, -1, -1, 1, 1, 1 }; static bool IsValid( int x, int y) { return (x >= 0 && y >= 0 && x < N && y < M); } // Function to print the matrix grid[][] static void PrintGrid( bool [][] grid) { for ( int row = 0; row < N; row++) { for ( int col = 0; col < M; col++) { if (grid[row][col]) Console.Write( "x " ); else Console.Write( "_ " ); } Console.WriteLine(); } } // Function to check if the cell (x, y) // is valid to have a mine or not static bool IsSafe( int [][] arr, int x, int y) { if (!IsValid(x, y)) return false ; for ( int i = 0; i < 9; i++) { if (IsValid(x + dx[i], y + dy[i]) && (arr[x + dx[i]][y + dy[i]] - 1 < 0)) return false ; } // Check if any of the neighbouring cell // of (x, y) supports (x, y) to have a mine for ( int i = 0; i < 9; i++) { if (IsValid(x + dx[i], y + dy[i])) arr[x + dx[i]][y + dy[i]]--; } return true ; } // Function to check if there // exists any unvisited cell or not static bool FindUnvisited( bool [][] visited, int [] x, int [] y) { for (x[0] = 0; x[0] < N; x[0]++) for (y[0] = 0; y[0] < M; y[0]++) if (!visited[x[0]][y[0]]) return true ; return false ; } // Function to check if all the cells // are visited or not and the input array // is satisfied with the mine assignments static bool IsDone( int [][] arr, bool [][] visited) { bool done = true ; for ( int i = 0; i < N; i++) { for ( int j = 0; j < M; j++) { done = done && (arr[i][j] == 0) && visited[i][j]; } } return done; } // Function to solve the minesweeper matrix static bool SolveMinesweeper( bool [][] grid, int [][] arr, bool [][] visited) { // Function call to check if each cell // is visited and the solved grid is // satisfying the given input matrix bool done = IsDone(arr, visited); // If the solution exists and // and all cells are visited if (done) return true ; int [] x = { 0 }; int [] y = { 0 }; // Function call to check if all // the cells are visited or not if (!FindUnvisited(visited, x, y)) return false ; // Mark cell (x, y) as visited visited[x[0]][y[0]] = true ; // Function call to check if it is // safe to assign a mine at (x, y) if (IsSafe(arr, x[0], y[0])) { // Mark the position with a mine grid[x[0]][y[0]] = true ; // Recursive call with (x, y) having a mine if (SolveMinesweeper(grid, arr, visited)) return true ; // Reset the position x, y grid[x[0]][y[0]] = false ; for ( int i = 0; i < 9; i++) { if (IsValid(x[0] + dx[i], y[0] + dy[i])) arr[x[0] + dx[i]][y[0] + dy[i]]++; } } // Recursive call without (x, y) having a mine if (SolveMinesweeper(grid, arr, visited)) return true ; visited[x[0]][y[0]] = false ; // If solution exists then return true // Mark the position as unvisited again // If no solution exists return false ; } static void minesweeperOperations( int [][] arr, int N, int M) { // Stores the final result bool [][] visited = new bool [N][]; for ( int i = 0; i < N; i++) { visited[i] = new bool [M]; } // Stores whether the position (x, y) is visited or not bool [][] grid = new bool [N][]; for ( int i = 0; i < N; i++) { grid[i] = new bool [M]; } // If the solution to the input minesweeper matrix exists if (SolveMinesweeper(grid, arr, visited)) { // Function call to print the grid[][] PrintGrid(grid); } // No solution exists else { Console.WriteLine( "No solution exists" ); } } // Driver code static void Main( string [] args) { // Given input N = 7; M = 7; int [][] arr = { new int [] { 1, 1, 0, 0, 1, 1, 1 }, new int [] { 2, 3, 2, 1, 1, 2, 2 }, new int [] { 3, 5, 3, 2, 1, 2, 2 }, new int [] { 3, 6, 5, 3, 0, 2, 2 }, new int [] { 2, 4, 3, 2, 0, 1, 1 }, new int [] { 2, 3, 3, 2, 1, 2, 1 }, new int [] { 1, 1, 1, 1, 1, 1, 0 } }; minesweeperOperations(arr, N, M); } } |
Javascript
// Constants for maximum dimensions const MAXM = 100; const MAXN = 100; // Global variables for dimensions let N, M; // Directional Arrays for neighboring cells let dx = [-1, 0, 1, -1, 0, 1, -1, 0, 1]; let dy = [0, 0, 0, -1, -1, -1, 1, 1, 1]; // Function to check if the cell (x, y) is valid or not function isValid(x, y) { return x >= 0 && y >= 0 && x < N && y < M; } // Function to print the matrix grid[][] function printGrid(grid) { for (let row = 0; row < N; row++) { let rowString = '' ; for (let col = 0; col < M; col++) { rowString += grid[row][col] ? 'x ' : '_ ' ; } console.log(rowString); } } // Function to check if the cell (x, y) is safe to have a mine or not function isSafe(arr, x, y) { if (!isValid(x, y)) return false ; for (let i = 0; i < 9; i++) { if (isValid(x + dx[i], y + dy[i]) && arr[x + dx[i]][y + dy[i]] - 1 < 0) { return false ; } } for (let i = 0; i < 9; i++) { if (isValid(x + dx[i], y + dy[i])) { arr[x + dx[i]][y + dy[i]]--; } } return true ; } // Function to check if there exists any unvisited cell or not function findUnvisited(visited, x, y) { for (x[0] = 0; x[0] < N; x[0]++) { for (y[0] = 0; y[0] < M; y[0]++) { if (!visited[x[0]][y[0]]) { return true ; } } } return false ; } // Function to check if all the cells are visited and the input array is satisfied with the mine assignments function isDone(arr, visited) { let done = true ; for (let i = 0; i < N; i++) { for (let j = 0; j < M; j++) { done = done && arr[i][j] === 0 && visited[i][j]; } } return done; } // Function to solve the minesweeper matrix function solveMinesweeper(grid, arr, visited) { let done = isDone(arr, visited); if (done) return true ; let x = [0]; let y = [0]; if (!findUnvisited(visited, x, y)) return false ; visited[x[0]][y[0]] = true ; if (isSafe(arr, x[0], y[0])) { grid[x[0]][y[0]] = true ; if (solveMinesweeper(grid, arr, visited)) return true ; grid[x[0]][y[0]] = false ; for (let i = 0; i < 9; i++) { if (isValid(x[0] + dx[i], y[0] + dy[i])) { arr[x[0] + dx[i]][y[0] + dy[i]]++; } } } if (solveMinesweeper(grid, arr, visited)) return true ; visited[x[0]][y[0]] = false ; return false ; } // Function to perform minesweeper operations function minesweeperOperations(arr, N, M) { let visited = Array.from({ length: N }, () => Array(M).fill( false )); let grid = Array.from({ length: N }, () => Array(M).fill( false )); if (solveMinesweeper(grid, arr, visited)) { // If solution exists, print the grid printGrid(grid); } else { // If no solution exists console.log( "No solution exists" ); } } // Given input N = 7; M = 7; let arr = [ [1, 1, 0, 0, 1, 1, 1], [2, 3, 2, 1, 1, 2, 2], [3, 5, 3, 2, 1, 2, 2], [3, 6, 5, 3, 0, 2, 2], [2, 4, 3, 2, 0, 1, 1], [2, 3, 3, 2, 1, 2, 1], [1, 1, 1, 1, 1, 1, 0] ]; // Execute minesweeper operations minesweeperOperations(arr, N, M); |
_ _ _ _ _ _ _ x _ _ _ _ x _ _ x x _ _ _ x x _ x _ _ _ _ _ x x _ _ _ x _ _ _ _ _ _ _ _ x _ _ x _ _
Time Complexity: O(2N * M * N * M)
Auxiliary Space: O(N * M)
Contact Us