Longest mathematical expression in a grid Given a grid which contains these signs: 0..9, x, =, write the fastest code that outputs the longest string of connected (horizontally, vertically, and diagonally adjacent), distinct cells which is a mathematically valid expression formed on this grammar:

E := T '=' T
T := F 'x' T | F
F -&gt; {0..9}+ 


More formally, a solution will have this form: an equality between a product of terms:

S = F0 x .. x Fp = Fp+1 x .. x Fn

I define N(S) = Max_i(F_i)

If two strings of the same length need to be compared, then I will compare their largest multiplicand. i.e.  30x3=90 &lt; 33x3=99 because  90 &lt; 99

 The grids 

Grid 0: 3 x 3

13x
=73
481


which contains: 13x37=481

Grid 1: 7 x 9

6996640
1127=39
186=940
8329706
3683980
6349307
75x19x0
5065350
0051900


which contains:

a=611333
b=599999
c=494687
d=531337
and a*b=366799188667
and c*d=262845506519


Grid 2: 8 x 8

1851x412
40081737
72330964
14461858
17604=67
89653745
13612200
14433193


Grid 3:  16 x 16

0951x71=7=41659x
958525855332=25x
8462=1x119191x76
993928209055089x
1523060251420490
=883152021094970
0146645532106152
87x96=294=x80675
7960948222x0440x
x577x987x0993241
29564563x=x5=800
03508x17050=6565


OK so after a short discussion in the comment sections, I am adding a few restrictions to allow me to do a fair comparison of solutions:

I will run the solution on my Macbook Pro which is 2,4 GHz Core 2 Duo running Mavericks. The language you are going to propose needs to be running natively on my computer, but fortunately, a lot of languages are available on OS X.

I will measure the quality of a program by comparing the time taken to find my hidden solution. Your program will probably find strings that are even longer that the one I hid in the first place, but this can not be avoided as I would need a program that enumerates all the solution of the grids I'm going to submit.. and this is the reason of this code golf..
C, checks about 7,500,000 paths per second

So here is my first pass over this. It's quite horrible code because it's all in one huge main and the two (nested) loops over the left-hand side and right-hand-side of the equation are pretty much exactly the same, but well, it works.

#include &lt;stdlib.h&gt;
#include &lt;stdio.h&gt;
#include &lt;string.h&gt;
#include &lt;time.h&gt;

#define MAX_SIZE 32

typedef struct {
    char symbol;
    int visited;
} cell;

typedef struct {
    int x;
    int y;
} coord;

static cell grid[MAX_SIZE][MAX_SIZE];
static int nEquals = 0;
static coord equals[MAX_SIZE*MAX_SIZE];

static coord dirs[8] = {
    { .x = -1, .y = -1 },
    { .x =  0, .y = -1 },
    { .x =  1, .y = -1 },
    { .x =  1, .y =  0 },
    { .x =  1, .y =  1 },
    { .x =  0, .y =  1 },
    { .x = -1, .y =  1 },
    { .x = -1, .y =  0 },
};

static char best_string[2*MAX_SIZE*MAX_SIZE+1];
static int best_length = 0;
static unsigned long long best_factor;

int main(int argc, char *argv[])
{
    FILE *fp = fopen("grid.txt", "r");
    if (!fp) perror("Memory allocation failed"), exit(1);

    fseek(fp, 0L, SEEK_END);
    long lSize = ftell(fp);
    rewind(fp);

    char *buffer = calloc(1, lSize+1);
    if (!buffer)
    {
        fclose(fp);
        perror("Memory allocation failed");
        exit(1);
    }

    if (1 != fread(buffer, lSize, 1, fp))
    {
        fclose(fp);
        free(buffer);
        perror("Reading file failed");
        exit(1);
    }

    fclose(fp);

    char *cp;
    cp = buffer;
    int width = (int)strtol(cp, &amp;cp, 10);
    int height = (int)strtol(cp, &amp;cp, 10);

    ++cp;
    int i, j;
    for (j = 0; j &lt; height; ++j)
    {
        for (i = 0; i &lt; width; ++i)
        {
            grid[j][i].symbol = *cp;
            grid[j][i].visited = 0;

            if (*cp == '=')
            {
                equals[nEquals].x = i;
                equals[nEquals].y = j;
                ++nEquals;
            }
            ++cp;
        }
        ++cp;
    }

    printf("Analysing %d x %d grid...\n", width, height);

    unsigned long long strings_checked = 0;

    clock_t start = clock();

    for (j = 0; j &lt; nEquals; ++j)
    {
        char expression[2*MAX_SIZE*MAX_SIZE+1];
        coord lpos = equals[j];
        coord rpos = equals[j];

        // Set to spaces to ease parsing
        for (i = 0; i &lt; 2*MAX_SIZE*MAX_SIZE+1; ++i)
            expression[i] = ' ';

        int center = MAX_SIZE*MAX_SIZE;
        expression[center] = '=';

        int lhs_size = 0;
        int lhs_n_factors = 0;


        int lhs_dirs[MAX_SIZE*MAX_SIZE];
        for (i = 0; i &lt; MAX_SIZE*MAX_SIZE; ++i)
            lhs_dirs[i] = -2;
        int rhs_dirs[MAX_SIZE*MAX_SIZE];
        for (i = 0; i &lt; MAX_SIZE*MAX_SIZE; ++i)
            rhs_dirs[i] = -2;

        unsigned long long lhs_factors[MAX_SIZE*MAX_SIZE];
        unsigned long long lhs_max_factors[MAX_SIZE*MAX_SIZE];
        unsigned long long lhs_products[MAX_SIZE*MAX_SIZE];
        lhs_max_factors[0] = 0;
        lhs_products[0] = 1;

        while (lhs_size &gt;= 0)
        {
            int dir = ++lhs_dirs[lhs_size];
            char lmost_char = expression[center-lhs_size];

            if (dir == -1)
            {
                grid[lpos.y][lpos.x].visited = 1;

                if (lmost_char == 'x')
                {
                    unsigned long long factor = strtoll(expression+center-lhs_size + 1, NULL, 10);
                    lhs_factors[lhs_n_factors] = factor;
                    ++lhs_n_factors;
                    if (factor &gt; lhs_max_factors[lhs_n_factors-1])
                        lhs_max_factors[lhs_n_factors] = factor;
                    else
                        lhs_max_factors[lhs_n_factors] = lhs_max_factors[lhs_n_factors-1];
                    lhs_products[lhs_n_factors] = lhs_products[lhs_n_factors-1] * factor;
                    continue;
                }
                else if (lmost_char == '=')
                    continue;
                else
                {
                    unsigned long long factor = strtoll(expression+center-lhs_size, NULL, 10);
                    unsigned long long max_lhs_factor;
                    if (factor &gt; lhs_max_factors[lhs_n_factors])
                        max_lhs_factor = factor;
                    else
                        max_lhs_factor = lhs_max_factors[lhs_n_factors];

                    unsigned long long lhs_product = lhs_products[lhs_n_factors] * factor;

                    int rhs_size = 0;

                    int rhs_n_factors = 0;
                    unsigned long long max_rhs_factor = 0;

                    unsigned long long rhs_factors[MAX_SIZE*MAX_SIZE];
                    unsigned long long max_factors[MAX_SIZE*MAX_SIZE];
                    unsigned long long rhs_products[MAX_SIZE*MAX_SIZE];
                    max_factors[0] = max_lhs_factor;
                    rhs_products[0] = 1;

                    char *rhs_factor_pointers[MAX_SIZE*MAX_SIZE];
                    rhs_factor_pointers[0] = expression+center+1;

                    while (rhs_size &gt;= 0)
                    {
                        int dir = ++rhs_dirs[rhs_size];
                        char rmost_char = expression[center+rhs_size];

                        if (dir == -1)
                        {
                            grid[rpos.y][rpos.x].visited = 1;

                            if (rmost_char == 'x')
                            {
                                factor = strtoll(rhs_factor_pointers[rhs_n_factors], NULL, 10);
                                rhs_factors[rhs_n_factors] = factor;
                                ++rhs_n_factors;
                                rhs_factor_pointers[rhs_n_factors] = expression + center + rhs_size + 1;
                                if (factor &gt; max_factors[rhs_n_factors-1])
                                    max_factors[rhs_n_factors] = factor;
                                else
                                    max_factors[rhs_n_factors] = max_factors[rhs_n_factors-1];
                                rhs_products[rhs_n_factors] = rhs_products[rhs_n_factors-1] * factor;
                                continue;
                            }
                            else if (rmost_char == '=')
                                continue;
                            else
                            {
                                // check for solution
                                ++strings_checked;

                                factor = strtoll(rhs_factor_pointers[rhs_n_factors], NULL, 10);
                                unsigned long long max_factor;
                                if (factor &gt; max_factors[rhs_n_factors])
                                    max_factor = factor;
                                else
                                    max_factor = max_factors[rhs_n_factors];

                                unsigned long long rhs_product = rhs_products[rhs_n_factors] * factor;

                                //printf("%.19s = %d\n", expression + center - 9, rhs_product);
                                //  printf("%.51s\n", expression + center - 25);
                                int length = rhs_size + lhs_size + 1;

                                if (lhs_product == rhs_product &amp;&amp;
                                    (length &gt; best_length ||
                                     length == best_length &amp;&amp; max_factor &gt; best_factor))
                                {
                                    best_length = length;
                                    best_factor = max_factor;
                                    memcpy(best_string, expression + center - lhs_size, length);
                                    best_string[length] = 0;
                                }

                            }
                        }
                        else if (dir &lt; 8)
                        {
                            coord step = dirs[dir];
                            int new_x = rpos.x + step.x;
                            int new_y = rpos.y + step.y;
                            char new_char;

                            if (new_x &lt; 0 || new_x &gt;= width ||
                                new_y &lt; 0 || new_y &gt;= height ||
                                grid[new_y][new_x].visited ||
                                (new_char = grid[new_y][new_x].symbol) == '=' ||
                                new_char == 'x' &amp;&amp; (rmost_char == 'x' || rmost_char == '=')) continue;

                            // TODO: Should diagonally crossing paths be disallowed, too?

                            ++rhs_size;

                            rpos.x = new_x;
                            rpos.y = new_y;
                            expression[center+rhs_size] = new_char;
                        }
                        else
                        {
                            if (rmost_char == 'x')
                                --rhs_n_factors;

                            rhs_dirs[rhs_size] = -2;
                            if (rmost_char != '=') expression[center+rhs_size] = ' ';
                            grid[rpos.y][rpos.x].visited = 0;

                            --rhs_size;
                            coord step = dirs[rhs_dirs[rhs_size]];
                            rpos.x -= step.x;
                            rpos.y -= step.y;
                        }
                    }
                }
            }
            else if (dir &lt; 8)
            {
                coord step = dirs[dir];
                int new_x = lpos.x + step.x;
                int new_y = lpos.y + step.y;
                char new_char;

                if (new_x &lt; 0 || new_x &gt;= width ||
                    new_y &lt; 0 || new_y &gt;= height ||
                    grid[new_y][new_x].visited ||
                    (new_char = grid[new_y][new_x].symbol) == '=' ||
                    new_char == 'x' &amp;&amp; (lmost_char == 'x' || lmost_char == '=')) continue;

                // TODO: Should diagonally crossing paths be disallowed, too?

                ++lhs_size;

                lpos.x = new_x;
                lpos.y = new_y;
                expression[center-lhs_size] = new_char;
            }
            else
            {
                if (lmost_char == 'x')
                    --lhs_n_factors;

                lhs_dirs[lhs_size] = -2;
                expression[center-lhs_size] = ' ';
                grid[lpos.y][lpos.x].visited = 0;

                --lhs_size;
                coord step = dirs[lhs_dirs[lhs_size]];
                lpos.x -= step.x;
                lpos.y -= step.y;
            }
        }
    }

    clock_t end = clock();
    float seconds = (float)(end - start) / CLOCKS_PER_SEC;

    printf("Checked %llu paths.\n", strings_checked);

    printf("Took %f seconds.\n", seconds);

    printf("Result: %s\n", best_string);
}


This expects the input stored in a file grid.txt. The first line is the space-separated size of the grid, which is followed by the grid itself. Like:

3 3
13x
=73
481


The algorithm is currently checking all possible well-formed paths (brute force). By well-formed, I mean that paths containing xx or two = are skipped, and I only start looking for paths starting from a = in both directions. Basically, I check all possible LHSs and for each such path, I check all possible RHSs. Over the next few days, I plan to add several optimisations to skip more paths, since the runtime per path will only go up and not down from here.

This will run into some problems with grid sizes of more than some 20 cells, due to integer overflow. I'll have to use some bigint-library when I get to solving those in a reasonable amount of time (which, I'm afraid, will reduce the paths/second a bit).

Currently, the largest sizes that can be solved in a reasonable amount of time at the moment are 7x3 or 5x4 (both taking under two minutes). 8x3 would take about half an hour, and 9x3 or 6x4 or 5x5 would take a few hours (between 1 and 7 I think).

EDIT: Managed to speed it up by close to 20 percent, because now I'm parsing each multiplicand when it's "locked" (i.e. when an x next to it has been parsed) instead of parsing the entire right-hand side for each possible path. And I should add that I observed those 20% for a grid where there's only a single x to be found, so I expect the performance gain for grids with many x to actually be quite substantial. Next stop: bigints.