Approach to solve Minesweeper Master

This problem(Minesweeper Master) has been asked in Google Codejam qualification round 2014. You can view the problem statement here Minesweeper Master.

The problem in short could be explained as, for a given number of rows(r) and columns(c) in a minesweeper grid, we need to prepare a layout that consists of (m) number of mines. The mines are to be represented by ‘*’, empty spaces are to be denoted by ‘.’.

Our layout should be such that we need to win in one click(Hoping you played the game before. Else it is described in the question). We denote the position that is to be clicked on the layout as ‘c’.

An approach to crack this problem:

Remember there may be number of layouts possible for a given set of number of rows(r), number of columns(c) and number of mines(m).

A prologue for our approach to this problem..

The positions on the layout where a mines can be placed or can be clicked are referred as blocks.
Keep in mind the constraint on number of mines is always atleast one less that r*c(total number of blocks).
In all the cases the block that is clicked at the end of making of layout would be the bottom most-right most block.

Here lets start..

Considering different cases,

1)
If either number of rows or number of columns(or both) is 1.

This case has a solution for whatever might the other attribute is. Remember that number of mines that would be in the layout are always less than r*c(that would be atleast one less than total number of blocks.)

Few cases for sample :

	1 4 3  
	4 1 2  
	1 1 0

Solutions for above :

	Case #1:
	***c
	Case #2:
	*
	*
	*
	c
	Case #3:
	c

2) If number of columns are two and number of mines are not one less than total number of blocks.

There are few subcases in this.

i) If number of mines are odd, it is never possible to get a solution.
ex:

	      5 2 3

lets say solution is

	      **
	      *.
	      ..
	      ..
	      .c

But this is wrong. Because on clicking at a position ‘c'(which is most optimal) we get it like

	      **
	      *.
	      11
	      00
	      00

Which is obviously not a solution since we are unable to win in one click.
ii) If number of mines is 2 less than total number of blocks, it is also not possible
ex:

	      5 2 8

lets say solution is

	      **
	      **
	      **
	      **
	      .c

On clicking at position marked ‘c’ we get

	      **
	      **
	      **
	      **
	      .2

So even this condition fails.

iii) In any other case a solution is possible.
ex:

	      5 2 4

Solution is

	      **
	      **
	      ..
	      ..
	      .c

on clicking at position marked ‘c’ we get

	      **
	      **
	      22
	      00
	      00

Which is a perfect solution as we can win in one click.

3) A similar cases are possible for if number of rows are two.

There are few subcases in this.

i) If number of mines are odd, it is never possible to get a solution.
ex:

 	      2 5 3

lets say solution is

	      **...
	      *...c

But this is wrong. Because on clicking at a position ‘c'(which is most optimal) we get it like

	      **100
	      *.100

Which is obviously not a solution since we are unable to complete the game in one click.

ii) If number of mines is 2 less than total number of blocks, it is also not possible
ex:

	      2 5 8

lets say solution is

	      ****.
	      ****c

On clicking at position marked ‘c’ we get

	      ****.
	      ****2

So even this condition fails.

iii) In any other case a solution is possible.
ex:

	       2 5 4

Solution is

	       **...
	       **..c

on clicking at position marked ‘c’ we get

	       **200
	       **200

Which is a perfect solution as we can win in one click.

4) If number of mines given is one less than total number of blocks.

Marking all the blocks leaving one as containing mines(‘*’), and the remaining with ‘c’ so that it is to be clicked. We are considering bottom-right block is clicked and so mark all other as ‘c’.

sample cases:

		input
	
		2 5 9
		4 4 15
	
		output
	
		Case #1:
		*****
		****c
		Case #2:
		****
		****
		****
		***c

5) Rest all cases.

Here for a better approach, mines are arranged in first r-3 rows in horizontal manner starting from left in every row. For the last 3 rows, they are arranged in vertical manner starting from top to bottom filling from left most column first and moving towards right.

i) A case in horizontal arranging
( If the last mine is to be placed in a block in the ‘c-1’th column.)

That would be a wrong approach. Lets see that case in a sample example for say

                6 5 9

Solution would be

	    	*****
	    	****.
	    	.....
	    	.....
	    	.....
	    	....c

But on clicking the block having ‘c’, we remain with

		*****
		****.
		23321
		00000
		00000
		00000

So on setting an offset for such a case, we can make place the last mine in first column of next row.( Note that there could be only two positions possible for such a case. First column – next row, or first column – last row, as we will be having c in last column- last row).

One of the correct approach is

		*****
		***..
		*....
		.....
		.....
		....c

On clicking on ‘c’ would turn

		*****
		***42
		*4210
		11000
		00000
		00000
		00000

ii) Now while placing mines in last 3 rows(placing them vertically as discussed above).
( A similar case just like above, that is if the last element has to be placed in second last row.)

It would be a wrong approach if we do not make an offset and correct that. Lets see a case

                6 5 20

Solution would be

	    	*****
	    	*****
	    	*****
	    	**...
	    	**...
	    	*...c

On clicking the block having ‘c’, we remain with

		*****
		*****
		*****
		**432
		**200
		*.100

A wrong solution indeed. So similar to previous we can make an offset and let the last mine appear in 3rd last row of next column.

		*****
		*****
		*****
		***..
		*....
		*...c

On clicking ‘c’,

		*****
		*****
		*****
		***42
		*5210
		*2000

A correct approach!!!

Here we can be sure that you will not cross the array boundary like you may not got to a[r-3][c] (‘0’ notation) position. Because that case implies you have (r*c)-1 number of mines to which solution has been already set.

iii) If any one block surrounding ‘c’ are having a mine.

Lets see this case with an example.

    		6 5 28

output is

	    	*****
	    	*****
	    	*****
	    	*****
	    	****.
	    	****c

So in this case on clicking on ‘c’ we are left with,

	    	*****
	    	*****
	    	*****
	    	*****
	    	****.
	    	****2

Game here could not be completed in one step, so there will be no solution. We can here again create an offset for searching if any of the three blocks and if true then print out ‘Impossible’.

Here again we may note that the case in which all three surrounding blocks having a mine is already cleared.

Here ends all the possible cases that may arise. Thus framing a perfect code from this algorithm we will be able to crack the problem.

 

Here is my code using above algorithm.

#include <stdio.h>

int main()
{
    int t;
    scanf("%d",&t);
    int turn =1;
    while(turn<=t)
    {
        int r,c,m;
        scanf("%d %d %d",&r,&c,&m);
        char a[60][60]={'.'};
        int i=0,j=0;
        for(i=0;i<r;i++) //initiating matrix with '.'
        {
            for(j=0;j<c;j++)
            {
                a[i][j]='.';
            }
        }
        int mines=m;
        int flag=0;  //at the end if flag is still zero, then the case is impossible.
        
        if(r==1 || c==1) // if either number of rows or number of columns is one. This case would always get accepted.
        {
            for(i=0;i<r;i++)
            {
                for(j=0;j<c;j++)
                {
                    if(mines>0)
                    {
                        a[i][j]='*';
                        mines--;
                    }
                    else break;
                }
            }
            a[r-1][c-1]='c';
            flag=1;
            printf("Case #%d:\n",turn);
            for(i=0;i<r;i++)
            {
                for(j=0;j<c;j++)
                {
                    printf("%c",a[i][j]);
                }
                printf("\n");
            }
            goto imp;
        }

        if(c==2 && !(m == (r*c)-1))  //If number of columns is 2, and m is not equal to one less than total number of blocks
        {
            if(m%2==1)  //If number of mines are odd in this case, it would never be possible.
            {
                goto imp;
            }
            
            if(m>(r*c)-4)  //If (r*c)-4 < number of mines < (r*c)-1
            {
                goto imp;
            }
            
            for(i=0;i<r;i++)  //all remaining cases here will be possible.
            {
                for(j=0;j<c;j++)
                {
                    if(mines>0)
                    {
                        a[i][j]='*';
                        mines--;
                    }
                    else break;
                }
            }
            a[r-1][c-1]='c';
            flag=1;
            printf("Case #%d:\n",turn);
            for(i=0;i<r;i++)
            {
                for(j=0;j<c;j++)
                {
                    printf("%c",a[i][j]);
                }
                printf("\n");
            }
            goto imp;
        }

        if(r==2 && !(m == (r*c)-1))  //If number of rows is 2, and m is not equal to one less than total number of blocks
        {
            if(m%2==1)  //If number of mines are odd in this case, it would never be possible.
            {
                goto imp;
            }
            
            if(m>(r*c)-4)  //If (r*c)-4 < number of mines < (r*c)-1
            {
                goto imp;
            }
            
            for(j=0;j<c;j++)  //all remaining cases here will be possible.
            {
                for(i=0;i<r;i++)
                {
                    if(mines>0)
                    {
                        a[i][j]='*';
                        mines--;
                    }
                    else break;
                }
            }
            a[r-1][c-1]='c';
            flag=1;
            printf("Case #%d:\n",turn);
            for(i=0;i<r;i++)
            {
                for(j=0;j<c;j++)
                {
                    printf("%c",a[i][j]);
                }
                printf("\n");
            }
            goto imp;
        }
        
        if(mines == (r*c)-1)  //if number of mines is one less than total number of blocks. Solution is always possible.
        {
            for(i=0;i<r;i++)
            {
                for(j=0;j<c;j++)
                {
                    a[i][j]='*';
                }
            }
            a[r-1][j-1]='c';
            flag=1;
            printf("Case #%d:\n",turn);
            for(i=0;i<r;i++)
            {
                for(j=0;j<c;j++)
                {
                    printf("%c",a[i][j]);
                }
                printf("\n");
            }
            goto imp;
        }

        int h1=0;
        for(i=0;i<r-3;i++)  //rest all cases
        {
            for(j=0;j<c;j++)
            {
                if(mines==1 && j==c-2)  //if last mine is to be filled in second last column, it would be wrong case. Setting offset.
                {
                    h1=1;
                    break;
                }
                if(mines>0)
                {
                    a[i][j]='*';
                    mines--;
                }
            }
            if(h1==1)
                break;
        }

        if(h1==1)  // if last mine is to be placed in second last column, making a correct apprach.
        {
            a[i+1][0]='*';
            mines--;
        }

        int h2=0;
        for(j=0;j<c;j++)
        {
            for(i=r-3;i<r;i++)
            {
                if(mines==1 && i==r-2)  ////if last mine is to be filled in second last row, it would be wrong case. Setting offset.
                {
                    h2=1;
                    break;
                }
                if(mines==1 && j==c-2)
                {
                    goto imp;
                }
                if(mines>0)
                {
                    a[i][j]='*';
                    mines--;
                }
                else break;
            }
            if(h2==1)
                break;
        }

        if(h2==1)  // if last mine is to be placed in second last row, making a correct apprach.
        {
            a[r-3][j+1]='*';
            mines--;
            if(j+1==c-2)
                goto imp;
        }

        a[r-1][c-1]='c';

        if(a[r-2][c-2]=='*' || a[r-1][c-2]=='*' || a[r-2][c-1]=='*') //If 'c' is surrounded by mine
            goto imp;

        flag=1;
        printf("Case #%d:\n",turn);  //printing out the solution
        for(i=0;i<r;i++)
        {
            for(j=0;j<c;j++)
            {
                printf("%c",a[i][j]);
            }
            printf("\n");
        }

        imp:
        if(flag==0)  //printing out impossible if flag=0
        {
            printf("Case #%d:\n",turn);
            printf("Impossible\n");
        }

        turn++;
    }


    return 0;
}

You could also download complete solution for this link. Download

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s