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 <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

#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, &cp, 10);
    int height = (int)strtol(cp, &cp, 10);

    ++cp;
    int i, j;
    for (j = 0; j < height; ++j)
    {
        for (i = 0; i < 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 < 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 < 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 < MAX_SIZE*MAX_SIZE; ++i)
            lhs_dirs[i] = -2;
        int rhs_dirs[MAX_SIZE*MAX_SIZE];
        for (i = 0; i < 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 >= 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 > 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 > 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 >= 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 > 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 > 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 &&
                                    (length > best_length ||
                                     length == best_length && max_factor > best_factor))
                                {
                                    best_length = length;
                                    best_factor = max_factor;
                                    memcpy(best_string, expression + center - lhs_size, length);
                                    best_string[length] = 0;
                                }

                            }
                        }
                        else if (dir < 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 < 0 || new_x >= width ||
                                new_y < 0 || new_y >= height ||
                                grid[new_y][new_x].visited ||
                                (new_char = grid[new_y][new_x].symbol) == '=' ||
                                new_char == 'x' && (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 < 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 < 0 || new_x >= width ||
                    new_y < 0 || new_y >= height ||
                    grid[new_y][new_x].visited ||
                    (new_char = grid[new_y][new_x].symbol) == '=' ||
                    new_char == 'x' && (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.

Python + networkx (Bruteforce, checks about 10000 paths per second on my machine)

It's not fast, but it works at least. Checks literally every path.

Amount of cycles necessary can be found here. This program solved a 5*6 in half an hour.

TODO: replace eval by something less terrible. Done.

__author__ = 'Synthetica'

import networkx as nx
import itertools as it
import time as tm


def main():
    longest = 0
    data = ['6996640', '1127=39', '186=940', '8329706', '3683980', '6349307',
            '75x19x0', '5065350', '0051900']

    hor = len(data[0])
    vert = len(data)

    threads = 8
    G = nx.grid_2d_graph(vert, hor)
    # Q = qu.LifoQueue(maxsize=1000)
    #W = mp.Pool(threads)
    #W.map_async(evalexpr, [Q]*threads)
    printevery = 10**4
    tested = 0
    t = tm.time()
    for node in it.product(G.nodes(), repeat=2):
        if node[0]==node[1]:
            continue
        for path in nx.all_simple_paths(G, source=node[0], target=node[1]):
            tested += 1
            path = "".join(data[x][y] for x, y in path)
            if tested > printevery:
                ot = t
                t = tm.time()
                tested = 0
                print printevery, "tested. Speed:", printevery/(t-ot), "s**-1"
            if not all((path.count('=')==1, 'x' in path, len(path) >= longest)):
                continue
            #newpath = path.replace('=', '==').replace('x', '*')
            try:
                #print "Calling eval on", newpath
                parts = path.split("=")
                part0 = parts[0].split('x')
                part1 = parts[1].split('x')

                part0 = map(int,part0)
                part1 = map(int,part1)

                part0 = reduce(int.__mul__, part0)
                part1 = reduce(int.__mul__, part1)

                result = part0 == part1




            except:
                result = False
            if result:
                print 'Found new best:',path
                longest = len(path)


if __name__ == "__main__":
    main()