Solving a machinarium puzzle using recursion

I was procrastinating studying for my exams about a month ago, so I started playing Machinarium on the Playstation. It’s a cool little point and click adventure where you play a robot when needs to beat some other robots and get his girl-robot friend back. For those who don’t play adventure games, they tend to have some really really frustrating puzzles. Machinarium was no exception. One I got particularly stuck on in the greenhouse. It involved a 5×5 grid which you have to completely light up. The catch is that you picked a starting square, which lights up, and then you can only pick a direction after that. The squares then light upĀ  in that direction until they hit a lit square or the edge of the grid. If you are surrounded by lit squares/edges and the grid isn’t lit, you have to start again. here is a video of someone playing it:

Well, I would have rather died playing this game before looking up a walk-through (the worst possible thing one can do while playing adventure games, such a slippery slope), so I decided screw it, that looks like it could be fairly easily implemented in a recursive algorithm. So I spent the next while doing it. At least it was good exam revision, I guess. I did it in C because that is what my exam was in. If you have thought of a better more efficient way to solve this puzzle (which I’m sure there is considering I’ve been only studying CS for a year), please tell me! I haven’t studied path solving type algorithms so far, but I plan to. This program can also solve bigger than 5×5 grids, but I haven’t really tested that yet – I would be interested to see how far this shoddy brute-force attempt will actually go as it gets exponentially more difficult. The code outputs the instructions back to front and at the bottom says the square you need to start at.

/**
* mach.h
*/
#define GRIDSIZE 5
void solveStart(int **array);
int gridFull(int **array);
int** solve(int **array, int position);
void freeA(int **a);
void aCopy(int **a1, int **a2);
int** iterate(int** array, int xDir, int yDir, int pos, char* direction);

 

/**
* mach.c
**/#include <stdlib.h>
#include <stdio.h>
#include "mach.h"

int main()
{
    /*declarations*/
    int **array;
    int ii, jj, input;

    /*allocate starting array*/
    array = (int**)calloc(GRIDSIZE, sizeof(int*));
    for (ii = 0; ii < GRIDSIZE; ii++) /*allocate array*/
    {
        array[ii] = (int*)calloc(GRIDSIZE,sizeof(int));
    }

    /*input the dead squares (grid is labeled starting at 0 going to GRIDSIZE moving across horizontally*/
    input = 0;
    while(input != 1234)
    {
        /*input the coordinate*/
        printf("\n input dead squres or enter 1234 to start solving: ");
        scanf("%4d", &input);

        /*if already dead, reverse, other wise make dead*/
        if ( (input < GRIDSIZE*GRIDSIZE) && (input >= 0) )
            if(array[input/GRIDSIZE][input%GRIDSIZE])
                array[input/GRIDSIZE][input%GRIDSIZE] = 0;
            else array[input/GRIDSIZE][input%GRIDSIZE] = 1;

        /*if out of bounds and not the exit key, dispaly error*/
        else if (input != 1234) 
        {
        printf("\n value entered is out of bounds, check your value or change #DEFINE GRIDSIZE value\n");
        }

        /*print the grid as it stands*/
        printf("\nCurrent grid (X for dead squares, O for live)\n");
        for(ii = 0; ii < GRIDSIZE; ii++)
        {
            for (jj = 0; jj < GRIDSIZE; jj++)
            {
                if(array[ii][jj] == 0)
                    printf("0");
                else printf("X");
            }
            printf("\n");
        }
    }

    /*start the algorithm*/
    solveStart(array);

    /*clean up*/
    freeA(array);
    return 0;
}

void solveStart(int **array)
{
    /*declarations*/
    int ii, exit;
    int **successArray, **tempArr;

    /*allocate array*/
    tempArr = (int**)calloc(GRIDSIZE, sizeof(int*));
    for (ii = 0; ii < GRIDSIZE; ii++)
    {
        tempArr[ii] = (int*)calloc(GRIDSIZE, sizeof(int));      
    }

    /*initialisations*/
    exit = 0;
    ii=0;

    /*main loop*/
    while (!exit)
    {
        /*can't start on dead squares*/
        while( (ii < GRIDSIZE*GRIDSIZE) && array[ii/GRIDSIZE][ii%GRIDSIZE] == 1)
            ii++;
        if (ii < GRIDSIZE*GRIDSIZE)
        {
            /*make a copy of starting array to attempt to solve starting at location ii*/
            aCopy(array, tempArr);
            /*turn the start square dead*/
            tempArr[ii/GRIDSIZE][ii%GRIDSIZE] = 1;
            /*start the algorithm*/
            successArray = solve(tempArr, ii);
            /*print the starting square if the puzzle can be solved by starting on it*/
            if( (exit = gridFull(successArray)) )
                    printf("%d\n", ii);
            /*go to the next square*/
            ii++;
            /*set exit variable to true if you've run out of spots to try*/
        }
        else 
        {
            exit = 1;
            printf("\n Grid not solvable\n");
        }
    }
    /*clean up*/
    freeA(successArray);
}

int** iterate(int** array, int xDir, int yDir, int pos, char* direction)
{
    /*declarations*/
    int newPos, ii; 
    int** returnVal, **tempArr;

    /*allocate temporary array to try the next iterations*/
    tempArr = (int**)calloc(GRIDSIZE, sizeof(int*));
    for (ii = 0; ii < GRIDSIZE; ii++) /*allocate array*/
    {
        tempArr[ii] = (int*)calloc(GRIDSIZE, sizeof(int));
    }
    returnVal = NULL;

    /*copy the imported array into the temp array */
    aCopy(array, tempArr);

    /*next square we're hoping to conquer*/
    newPos  = pos+yDir*GRIDSIZE+xDir;

    /*check to see if it is in the bounds, and that it is alive*/
    if  ( ( (newPos < GRIDSIZE*GRIDSIZE) && ( newPos >= 0 ) && (tempArr[newPos/GRIDSIZE][newPos%GRIDSIZE] == 0 ) ) && ( (xDir == 0) ||  ( (pos%GRIDSIZE-newPos%GRIDSIZE) == 1) || ( (pos%GRIDSIZE-newPos%GRIDSIZE) == -1) ) )
        {
            do
            {
                /*make the square dead and set the next square we hope to conquer*/
                tempArr[newPos/GRIDSIZE][newPos%GRIDSIZE] = 1;
                pos = newPos;
                newPos = newPos+yDir*GRIDSIZE+xDir;
            }

            /*check to see if next square is in the bounds, and that it is alive, if not exit*/
            while ( ( ( (newPos) < GRIDSIZE*GRIDSIZE ) && ( newPos >= 0 ) && ( tempArr[newPos/GRIDSIZE][newPos%GRIDSIZE] == 0 ) ) && ( (xDir == 0) ||  ( (pos%GRIDSIZE-newPos%GRIDSIZE) == 1) || ( (pos%GRIDSIZE-newPos%GRIDSIZE) == -1) ) );

            /*find the next direction*/
            tempArr = solve(tempArr,pos);
            /*you should only get here if your grid is filled or if you've exhausted all posibilities for this node (and its children*/
            if (gridFull(tempArr))
            {
                /*if you're here, the problem is solved and program is unwinding*/
                printf("%s\n", direction);
                freeA(array);
                returnVal = tempArr;
            }
            else
                freeA(tempArr);
        }
        else freeA(tempArr);
    /*NULL if unsolved, contains the solved array if it isn't*/
    return returnVal;
}

int** solve(int **array, int position)
{
    int **tempArr;

    /*base case: when the grid is full*/
    if (gridFull(array))
        tempArr = array;
    else
    {
        /*try going in each possible direction*/
        if ( (tempArr = iterate(array, 0, -1, position, "up") ) != NULL );
        else if ( (tempArr = iterate(array, 0, 1, position, "down") ) != NULL );
        else if ( (tempArr = iterate(array, 1, 0, position, "right") ) != NULL );
        else if ( (tempArr = iterate(array, -1, 0, position, "left") ) != NULL );
        else tempArr = array;
    }
    return tempArr;
}

/*helper function set the values in a2 to the values in a1*/
void aCopy(int **a1, int **a2)
{
    int ii;
    int jj;
    for (ii = 0; ii < GRIDSIZE; ii++)
    {
        for(jj=0;jj<GRIDSIZE; jj++)
            a2[ii][jj] = a1[ii][jj];
    }
}       

/*helper function to check if the grid is full (therefore complete), evil multi return to speed up false cases*/
int gridFull(int **array)
{
    int ii;
    int jj;
    for (ii=0;ii<GRIDSIZE;ii++)
    {
        for(jj = 0; jj<GRIDSIZE;jj++)
        {
            if (array[ii][jj] == 0)
                return 0;
        }
    }
    return 1;   
}

/*helper function to free a 2D malloc'd array of size [GRIDSIZE][GRIDSIZE]*/
void freeA(int **a)
{
    int ii;
    for (ii=0;ii<GRIDSIZE;ii++)
    {
        free(a[ii]);
    }
    free(a);
}
While making this little program, I wondered how many different solvable grids there were. So I decided to find out. It turns out the number of possible grids (but not necessarily solvable) you can get is equal to N = 2G2 where G is the height of the grid. I used this little piece of code as well as a slightly modified version of the above, shown here (I fixed up some memory errors too), piping the test program into the mach program to feed every possible grid for the specified gridsize and the program will tell me how many are solvable and save those to a file.
/**
* test.c
**
#include <stdlib.h>
#include <stdio.h>
#include "mach.h"

int plusOne(int *prev)
{
    int ii;
    ii = GRIDSIZE*GRIDSIZE-1;
    while(prev[ii] == 1)
    {
        if (ii == 0)
            return 0;
        prev[ii] = 0;
        ii--;
    }
    prev[ii] = 1;
    return 1; 
}
int main()
{
    int ii;
    int* array;
    array = (int*)calloc(GRIDSIZE*GRIDSIZE, sizeof(int));
    do
    {
        for(ii = 0; ii <GRIDSIZE*GRIDSIZE;ii++)
        {
            if (array[ii] == 1)
                printf("%d\r", ii);
        }
        printf("1234");
    }
    while (plusOne(array));
    free(array);
    return 0;
}
It turns out for the a 2×2 grid there are 16 possible but only 14 13 are solvable
For 3×3, there are 512 possible but only 171 are solvable

For 4×4, there are 65,536 possible but only 3503 are solvable

For a 5×5, there are 33,554,432 possible, but my computer so far has only calculated 4.7 million. It will probably take a couple of hours from now. After a couple of computing hours, it has 118481 solvable.
6×6 will probably take a very long time on my PC, 68,719,476,736 possibilities – likely more than a year, so thats where this algorithm’s usefulness wears out. I wonder how far it could be optimized.
Here are links to the outputted logs of every possible solvable grid:
2×2 This is lost now, sorry
Update: Looking through the 2×2 log, I notice that a grid that looks like this was in there

XO

OX
when it is clearly not solvable. I think the problem here is with how I detected whether you were at the edge of the grid by seeing if the difference between the next and current position mod the grid size was one. This is clearly a problem in a 2×2 grid, therefore the algorithm is definitely not suited to it.

Leave a Reply

Your email address will not be published. Required fields are marked *