Analysis: Wormholes, by Brian Dean

The process of solving this problem is described in the video above; the final code is shown below.

```#include <iostream>
#include <fstream>
using namespace std;
#define MAX_N 12

int N, X[MAX_N+1], Y[MAX_N+1];
int partner[MAX_N+1];
int next_on_right[MAX_N+1];

bool cycle_exists(void)
{
for (int start=1; start<=N; start++) {
// does there exist a cylce starting from start
int pos = start;
for (int count=0; count<N; count++)
pos = next_on_right[partner[pos]];
if (pos != 0) return true;
}
return false;
}

// count all solutions
int solve(void)
{
// find first unpaired wormhole
int i, total=0;
for (i=1; i<=N; i++)
if (partner[i] == 0) break;

// everyone paired?
if (i > N) {
if (cycle_exists()) return 1;
else return 0;
}

// try pairing i with all possible other wormholes j
for (int j=i+1; j<=N; j++)
if (partner[j] == 0) {
// try pairing i & j, let recursion continue to
// generate the rest of the solution
partner[i] = j;
partner[j] = i;
total += solve();
partner[i] = partner[j] = 0;
}
}

int main(void)
{
ifstream fin("wormhole.in");
fin >> N;
for (int i=1; i<=N; i++) fin >> X[i] >> Y[i];
fin.close();

for (int i=1; i<=N; i++) // set next_on_right[i]...
for (int j=1; j<=N; j++)
if (X[j] > X[i] && Y[i] == Y[j]) // j right of i...
if (next_on_right[i] == 0 ||
X[j]-X[i] < X[next_on_right[i]]-X[i])
next_on_right[i] = j;

ofstream fout("wormhole.out");
fout << solve() << "\n";
fout.close();
return 0;
}
```