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`
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++;
}