Non-exponential solution to maze problem?

Question

Given a n*n-sized multi-headed acyclic graph where each node has at most three children and three parents, is there an non-exponential algorithm to identify whether a n-length path exists where no two nodes share the same value, and every value of a set is accounted for?

Basically, I have an n*n maze where each space has a random value (1..n). I need to find a path (from the top to the bottom) of n nodes that includes every value.

Right now I'm using a depth-first search, but that is T(n) = 3T(n-1) + O(1), which is O(3^n), a non-ideal solution.

Either confirming my fears, or pointing me in the right direction would be much appreciated.

Edit: to make this a little bit more concrete, here is a maze with solutions (solved using the depth-first solution).

 1 2 5 5 4
 1 5 1 3 5
 4 1 2 3 2
 5 5 4 4 3
 4 2 1 2 4
S3, 5, 1, 3, 4, 2, F4
S3, 5, 1, 3, 4, 2, F2
S3, 5, 1, 3, 4, 2, F4
S3, 5, 3, 2, 4, 1, F3
S3, 5, 3, 2, 4, 1, F3
S3, 5, 3, 2, 4, 1, F3
S4, 5, 3, 2, 4, 1, F3
S4, 5, 3, 2, 4, 1, F3
S4, 5, 3, 2, 4, 1, F3
S4, 5, 1, 3, 4, 2, F4
S4, 5, 1, 3, 4, 2, F2
S4, 5, 1, 3, 4, 2, F4
S5, 4, 3, 2, 5, 1, F3
13 total paths`

Answer 1

This problem is NP-complete, and so it is not known whether or not there is a polynomial-time solution. (The standard provisos of possibly being easy in practice, etc., all apply.) One possible reduction is from 3SAT.

Suppose we have a 3SAT instance, such as (a ∨ b ∨ c) ∧ (¬a ∨ ¬b ∨ ¬c). I will show how to use "gadgets" to build an instance of your problem. Before we begin, rewrite the 3SAT problem as (a1 ∨ b1 ∨ c1) ∧ (¬a2 ∨ ¬b2 ∨ ¬c2) together with a1 = a2, b1 = b2, and c1 = c2; that is, make each occurrence of a variable unique, but then add the condition that different occurrences of the same variable must be equal.

First, we make sure that you must pick the number 0 in the first row, so that we can use it later as a "sentinel" that you must avoid.

 0   0   0 

Now, we build a gadget that enforces the a1 = a2 rule: (The underscore _ here is a new unique number in every use of this gadget)

 0   _   0 
 a1  0  ¬a1
 a2  0  ¬a2

Because of the first row, you must avoid the 0s. This means you either take the path "a1, a2" or the path "¬a1, ¬a2"; the former will correspond to (slightly confusingly) setting a to false, while the latter will correspond to a setting a to true. This is because our clause gadget is really easy then, because we simply write down the clause, e.g. (again _ here is a new variable each time):

 0   _   0 
 a1  b1  b2

or

 0   _   0 
¬a1 ¬b1 ¬b2

Finally, since you've only used one of a1 and ¬a1, etc., we let you take the ones you haven't used freely:

 0   _   0 
 a1 ¬a1  0 

Now, this doesn't quite work, because one of a1 and ¬a1 might have been used in the variable choice gadget, while the other could have been used in a clause. So, we include a new variable @i for each clause that you can take instead of one of the variables. So if variable a1 appears in clause 1, we have

 0   _   0 
 a1 ¬a1  @1 

Here's the complete output of a translation of the original 3SAT clause (highlighting the path corresponding to setting a and b to true, c to false, and picking a from the first clause), with numbers on the left and gloss on the right. The gadgets are re-ordered (first clause gadgets, then for each variable, the equality gadget and then unused gadget), but this doesn't matter since they're independent anyway.

0       0  <    0               .       .  <    .       
0       8  <    0               .       _  <    .       
2  <    4       6               a1 <    b1      c1      
0       16 <    0               .       _       .       
11      13      15 <            -a2     -b2     -c2<    
0       17 <    0               .       _  <    .       
2       0       3  <            a1      .       -a1<    
10      0       11 <            a2      .       -a2<    
0       18 <    0               .       _  <    .       
2       3       1  <            a1      -a1     @1 <    
0       19 <    0               .       _       .       
10 <    11      9               a2 <    -a2     @2      
0       20 <    0               .       _  <    .       
4       0       5  <            b1      .       -b1<    
12      0       13 <            b2      .       -b2<    
0       21 <    0               .       _  <    .       
4  <    5       1               b1 <    -b1     @1      
0       22 <    0               .       _  <    .       
12 <    13      9               b2 <    -b2     @2      
0       23 <    0               .       _  <    .       
6  <    0       7               c1 <    .       -c1     
14 <    0       15              c2 <    .       -c2     
0       24 <    0               .       _  <    .       
6       7  <    1               c1      -c1<    @1      
0       25 <    0               .       _  <    .       
14      15      9  <            c2      -c2     @2 <    

(If you want the whole thing to be square, just include a bunch of zeros at the end of each line.) It's fun to see that no matter how you solve this, at heart, you're solving that 3SAT problem.

At the end of my post is a hastily-written Perl program that generates one of your problems from an input of the form

a b c
-a -b -c

The number of variables in the resulting instance of your problem is 11C + V + 1. Give the program the -r switch to produce gloss instead of numbers.

# Set useful output defaults
$, = "\t"; $\ = "\n";

# Process readability option and force sentinel
my $r = "0";
if( $ARGV[0] =~ /-r/ ) { shift; $r = "."; }
print $r, $r, $r;

# Clause gadgets
my( %v, %c, $m, $c );
$m = 1;
while( <> ) {
    my( @v, @m );
    $c = $m++;
    chomp; @v = split;
    for my $v ( @v ) {
        push @{$v{strip($v)}}, -1; # hack, argh!
        push @m, ($r ? $v.@{$v{strip($v)}} : $m + neg($v));
        $c{($r ? (strip($v).@{$v{strip($v)}}) : $m)} = $c;
        $v{strip($v)}->[-1] = ($r ? (strip($v).@{$v{strip($v)}}) : $m);
        $m += 2 unless $r;
    }
    print $r, newv(), $r;
    print @m;
}

# Variable gadget
for my $v ( sort keys %v ) {
    # Force equal
    print $r, newv(), $r;
    for my $n ( @{$v{$v}} ) {
        print $n, $r, ($r ? "-".$n : $n+1);
    }

    # Unused
    for my $n ( @{$v{$v}} ) {
        print $r, newv(), $r;
        print $n, ($r ? "-".$n : $n+1), ($r ? "\@".$c{$n} : $c{$n});
    }
}

# Strip leading -
sub strip {
    my( $v ) = @_;
    return substr $v, neg($v);
}

# Is this variable negative?
sub neg {
    my( $v ) = @_;
    return "-" eq substr( $v, 0, 1 );
}

# New, unused variable
sub newv {
    return "_" if $r;
    return $m++;
}

Answer 2

I'm pretty sure this can be done in polynomial time. I would start with a an empty set and then loop through the rows top to bottom. I'm going to skip any kind of code and show you what the state would look like at each step you should be able to put together an algorithm from there. I'm pretty sure the best case is slightly worse than O(n^2) using a variation of breadth first search and keeping track of the current good paths in a table.

EDIT: If this still isn't fast enough you can improve it by applying Harlequin's optimization.

For Example:

1 2 3
3 2 1
1 2 1

State 0: R = 0 // Row P = {} // Path Set

// {{Path so far}, Column}

P' = {
    {{1}, 0}
    {{2}, 1}
    {{3}, 2}
}

P = P'

State 1: R = 1 // ROW P = { {{1}, 0} {{2}, 1} {{3}, 2} }

P' = {
    {{1 3}, 0}
    {{1 2}, 1}
    {{2 3}, 0}
    {{2 1}, 2}
    {{3 2}, 1}
    {{3 1}, 2}
}

State 2: R = 2 P = { {{1 3}, 0} {{1 2}, 1} {{2 3}, 0} {{2 1}, 2} {{3 2}, 1} {{3 1}, 2} }

P' = {
    {{1 3 2}, 1}
    {{2 3 1}, 0}
    {{3 2 1}, 0}
    {{3 2 1}, 2}
    {{3 1 2}, 1}
}

Result:
Path Count: 5
S1 1 3 2 F2
S2 2 3 1 F1
S3 3 2 1 F1
S3 3 2 1 F3
S3 3 1 2 F2

Answer 3

You can try the ant colony optimization. It quickly yields very good results that are very close to the perfect solution.

Answer 4

One optimization for Kevin Loney's solution might be to merge partial paths that contain the same elements at the same column. You would have to note the number of merges with the path if you want to know the number of solutions at the end.

Example: In your 5x5 example, when you arrive at the third row, the third column has three paths leading to it that contain (1 2 5) in some order. You don't have to follow these separately from this point, but can merge them. If you want to know the number of solutions at the end, you just have to adjust your path data structure, e.g. three (1 (1 2 5)) would merge to (3 (1 2 5)).