Click here to Skip to main content
13,702,125 members
Rate this:
 
Please Sign up or sign in to vote.
See more:
I have a task of implementing recursion in a simulated minesweeper game in C. It should basically call itself to clear neighboring cells, provided it is possible to do so. I would appreciate any help in pointing out the error in my algorithm. And please bear in mind that I have only learnt programming for 6 weeks so I may not understand advanced explanations. Thank you!

(PS: I would like to post the actual question but it seems like it is not possible to do so here)

What I have tried:

#include <stdio.h>
#include <stdbool.h>
#define ROW 16 //max number of rows 
#define COL 30 //max number of columns

void readBoard(int board[][COL], int m, int n);
void printBoard(int board[][COL], int m, int n);
int countNeighbour(int board[][COL], int r, int c, int m, int n);
bool isValid(int r, int c, int m, int n);
bool allCleared(int board[][COL], int m, int n);
void clearNeighbours(int board[][COL], int r, int c, int m, int n); 

int main(void) {
   int r, c, m, n, board[ROW][COL]={{0}}; //initializes all values to 0

   scanf("%d%d", &m, &n);
   readBoard(board, m, n); // reads the board.
   do {
      scanf("%d%d", &r, &c);     
      if(board[r][c] < 9  && isValid(r,c,m,n) == true) { // checks for mines presence and location validity
         if(countNeighbour(board, r, c, m, n) == 0) {
            clearNeighbours(board, r, c, m, n);
         }
      } else break; // escape the loop if the conditions are not fulfilled
   } while (allCleared(board,m,n) == false); // checks if all safe locations are cleared

   printBoard(board, m, n);
   return 0;
}

/* 
  allCleared checks the board and returns true if all safe locations
  have been cleared, false otherwise.
*/
bool allCleared(int board[][COL], int m, int n) {
   int i,j;
   for(i=0; i<m; i++) {
      for(j=0; j<n; j++) {
         if(board[i][j] == -1) {
            return false;
         }
      }
   }
   return true;
}

/* 
  isValid checks if the input location is valid or not.
*/
bool isValid(int r, int c, int m, int n) {
   if(r>=0 && r<=m && c>=0 && c<=n) {
      return true;
   }
   return false;
}   

/* 
 readBoard reads the input of the location of the mines and safe locations
 and stores the values inside an array.
 Precondition: the input values must be either -1 or 9.
*/
void readBoard(int board[][COL], int m, int n) {
   int i,j;
   for(i=0; i<m; i++) {
      for(j=0; j<n; j++) {
         scanf("%d", &board[i][j]);
      }
   }
}

/* 
 printBoard prints the minesweeper board. "*" represents mines 
 and "." represents safe locations. Numbers from 0 to 8 represents
 the number of mines present in the neighbouring cells.
*/
void printBoard(int board[][COL], int m, int n) {
   int i, j;
   for(i=0; i<m; i++) {
      for(j=0; j<n; j++) {
         if(board[i][j] == -1) {
            printf(".");
         }
         else if( board[i][j] >= 9) {
            printf("*");
         } else {
            printf("%d", board[i][j]);
         }
      }
      printf("\n");
   }
}

/* 
  countNeighbour checks the specified location for neighbouring mines,
  returns the number of mines present. P.S: I hard coded this part during the lab
  so I had no choice but to leave it as it is.
  Precondition: the specified location is inside the board
*/
int countNeighbour(int board[][COL], int r, int c, int m, int n) {
   if(board[r][c]!=-1) return board[r][c]; //returns if the location contains a mine or it has been checked
   
   if(isValid(r-1,c,m,n) && board[r-1][c] == 9) {
      board[r][c]++;
   }  
   if(isValid(r-1,c-1,m,n) && board[r-1][c-1] == 9) {
      board[r][c]++;
   }
   if(isValid(r,c-1,m,n) && board[r][c-1] == 9) {
      board[r][c]++;
   }
   if(isValid(r+1,c+1,m,n) && board[r+1][c+1] == 9) {
      board[r][c]++;
   }
   if(isValid(r,c+1,m,n) && board[r][c+1] == 9) {
      board[r][c]++;
   }
   if(isValid(r+1,c,m,n) && board[r+1][c] == 9) {
      board[r][c]++;
   }
   if(isValid(r+1,c-1,m,n) && board[r+1][c-1] == 9) {
      board[r][c]++;
   }
   if(isValid(r-1,c+1,m,n) && board[r-1][c+1] == 9) {
      board[r][c]++;
   }

   board[r][c]++; //since safe locations are denoted by -1, increments regardless of mines' presence.
   return board[r][c];
}

/* 
 clearNeighbours clear neighbouring cells, while making sure
 that they are inside the board. Calls itself repeatedly until
 all possible neighboring cells are cleared
 Precondition: the input location must be a safe location.
*/
void clearNeighbours(int board[][COL], int r, int c, int m, int n) {
   int row[] = {1,0,-1,0,1,1,-1,-1}; //temp array to check all 8 neighbouring cells row
   int col[] = {0,1,0,-1,1,-1,1,-1}; //temp array to check the column
   int i;

   countNeighbour(board,r,c,m,n);
   if(board[r][c] != 8) return;  
   for(i = 0;i<8;i++) { //loop terminates if all neighboring safe cells are cleared 
      int nextRow =  r + row[i], nextCol = c + col[i];
      if(isValid(nextRow,nextCol,m,n) && board[r][c] == -1) {
         clearNeighbours(board,nextRow,nextCol,m,n); //clears the safe cells repeatedly
      }
   }
} 
Posted 17-Nov-17 7:14am
Updated 17-Nov-17 7:18am
v2
Comments
Graeme_Grant 17-Nov-17 21:12pm
   
This brings me back ... I have the code to do this somewhere... I'll see if I can find it and will post it as an article... If I remember correctly it was far easier to do with a single dimension array...
17-Nov-17 23:41pm
   
single dimension array as in to clear the neighboring cells repeatedly? Sure I would appreciate any help

1 solution

Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 1

You need to understand that C arrays are zero based
This means that in an array of size 30, valid indexes are from 0 to 29.
Because you did not understood this, you are counting neighbors outside of the board.
You can not tell if recursive part is working or not as long as it use buggy subroutines.

Using the debugger should be great help to check what is going on.

There is a tool that allow you to see what your code is doing, its name is debugger. It is also a great learning tool because it show you reality and you can see which expectation match reality.
When you don't understand what your code is doing or why it does what it does, the answer is debugger.
Use the debugger to see what your code is doing. Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.

Debugger - Wikipedia, the free encyclopedia[^]

Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Basic Debugging with Visual Studio 2010 - YouTube[^]
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't find bugs, it just help you to. When the code don't do what is expected, you are close to a bug.
[Update]
Quote:
I don't think that's true as I have implemented the isValid function to check whether the array is out of bounds or not. I believe there is an error in my implementation of the recursion

Don't think, don't believe, use the debugger and make sure.
  Permalink  
v2
Comments
17-Nov-17 23:50pm
   
I don't think that's true as I have implemented the isValid function to check whether the array is out of bounds or not. I believe there is an error in my implementation of the recursion

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
Top Experts
Last 24hrsThis month


Advertise | Privacy | Cookies | Terms of Service
Web05-2016 | 2.8.180906.1 | Last Updated 18 Nov 2017
Copyright © CodeProject, 1999-2018
All Rights Reserved.
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100