algorithm termination
Marzio De Biasi
• 22.2k
• 2
• 52
• 122

A quick informal algorithm to prove that the problem is decidable:

• suppose that there are $$n$$ Input/Outputs $$I_1,...I_n$$;
• build a graph $$G$$ where each $$I_i$$, the $$MINUS$$ and the $$PLUS$$ are nodes, and replace each nested maze $$Mj$$ with a $$K_n$$ subgraph (complete graph); add the edges between $$I_i, MINUS, PLUS, Mj_{I_k}$$ according to the maze; keep "extern" $$Mj_{I_i} \rightarrow Mj_{I_k}$$ edges distinct from the corresponding "internal" edges $$I_i \rightarrow I_k$$ of $$Mj$$ as a complete subgraph;
• enumerate all paths from MINUS to PLUS in $$G$$ (avoiding cycles);
• if you find a path that doesn't traverse a nested copy, then it is a solution; otherwise expand each "internal" traversals of the nested mazes $$Mj$$ of each path:

Suppose that a path in the first enumeration is $$MINUS \rightarrow A_{I_i} \rightarrow A_{I_j} \rightarrow B_{I_k} \rightarrow B_{I_h} \rightarrow PLUS$$, then the path is a valid solution iif there is a path from $$I_i \rightarrow I_j$$ and from $$I_k \rightarrow I_h$$ in the original maze (graph $$G$$).

So we must expand the $$A_{I_i} \rightarrow A_{I_j}$$ and $$B_{I_k} \rightarrow B_{I_h}$$ traversals enumerating all the paths from $$I_i$$ to $$I_k$$ and from $$I_k$$ to $$I_h$$ in $$G$$.

Infinite loops are detected when we are enumerating all paths from $$I_i$$ to $$I_k$$ in an expansion of a path that in a previous stage already contained $$... \rightarrow M_{I_i} \rightarrow M_{I_k} \rightarrow ...$$ for some submaze $$M$$ (there are only $$n^2$$ possible expansionexpansions).

A solution is found if we find a path expansion that contains only inputs/outputs $$I_i$$; the maze has no solution if we cannot further expand the paths without loops.

distinct internal/external edges for nested copies
Marzio De Biasi
• 22.2k
• 2
• 52
• 122

A quick informal algorithm to prove that the problem is decidable:

• suppose tahtthat there are $$n$$ Input/Outputs $$I_1,...I_n$$;
• build a graph $$G$$ where each $$I_i$$, the $$MINUS$$ and the $$PLUS$$ are nodes, and replace each nested maze $$Mj$$ with a $$K_n$$ subgraph (complete graph); add the edges between $$I_i, MINUS, PLUS, Mj_{I_k}$$ according to the maze; keep "extern" $$Mj_{I_i} \rightarrow Mj_{I_k}$$ edges distinct from the corresponding "internal" edges $$I_i \rightarrow I_k$$ of $$Mj$$ as a complete subgraph;
• enumerate all paths from MINUS to PLUS in $$G$$ (avoiding cycles);
• if you find a path that doesn't traverse a nested copy, then it is a solution; otherwise "expand"expand each "internal" traversals of the nested mazes $$Mj$$ of each path:

Suppose that a path in the first enumeration is $$MINUS \rightarrow A_{I_i} \rightarrow A_{I_j} \rightarrow B_{I_k} \rightarrow B_{I_h} \rightarrow PLUS$$, then the path is a valid solution iif there is a path from $$I_i \rightarrow I_j$$ and from $$I_k \rightarrow I_h$$ in the original maze (graph $$G$$).

So we must expand the $$A_{I_i} \rightarrow A_{I_j}$$ and $$B_{I_k} \rightarrow B_{I_h}$$ traversals enumerating all the paths from $$I_i$$ to $$I_k$$ and from $$I_k$$ to $$I_h$$ in $$G$$.

Infinite loops are detected when we are enumerating all paths from $$I_i$$ to $$I_k$$ in an expansion of a path that in a previous stage already contained $$... \rightarrow M_{I_i} \rightarrow M_{I_k} \rightarrow ...$$ for some submaze $$M$$ (there are only $$n^2$$ possible expansion).

A solution is found if we find a path expansion that contains only inputs/outputs $$I_i$$.

Marzio De Biasi
• 22.2k
• 2
• 52
• 122

A quick informal algorithm to prove that the problem is decidable:

• suppose taht there are $$n$$ Input/Outputs $$I_1,...I_n$$;
• build a graph $$G$$ where each $$I_i$$, the $$MINUS$$ and the $$PLUS$$ are nodes, and replace each nested maze $$Mj$$ with a $$K_n$$ subgraph (complete graph); add the edges between $$I_i, MINUS, PLUS, Mj_{I_k}$$ according to the maze;
• enumerate all paths from MINUS to PLUS in $$G$$ (avoiding cycles);
• if you find a path that doesn't traverse a nested copy, then it is a solution; otherwise "expand" each traversals of the nested mazes $$Mj$$ of each path:

Suppose that a path in the first enumeration is $$MINUS \rightarrow A_{I_i} \rightarrow A_{I_j} \rightarrow B_{I_k} \rightarrow B_{I_h} \rightarrow PLUS$$, then the path is a valid solution iif there is a path from $$I_i \rightarrow I_j$$ and from $$I_k \rightarrow I_h$$ in the original maze (graph $$G$$).

So we must expand the $$A_{I_i} \rightarrow A_{I_j}$$ and $$B_{I_k} \rightarrow B_{I_h}$$ traversals enumerating all the paths from $$I_i$$ to $$I_k$$ and from $$I_k$$ to $$I_h$$ in $$G$$.

Infinite loops are detected when we are enumerating all paths from $$I_i$$ to $$I_k$$ in an expansion of a path that in a previous stage already contained $$... \rightarrow M_{I_i} \rightarrow M_{I_k} \rightarrow ...$$ for some submaze $$M$$ (there are only $$n^2$$ possible expansion).

A solution is found if we find a path expansion that contains only inputs/outputs $$I_i$$.