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);
}

/**
* 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;
}

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

XO