Detailed mathematical approach

Problem Summary

We must count all valid touch-screen passwords on a \(4\times 4\) lattice of points. A password is an ordered sequence of distinct nodes with length at least \(2\). If the current node is \(a\) and the next node is \(b\), the move is allowed only when every lattice point strictly inside the segment from \(a\) to \(b\) has already appeared earlier in the password.

This makes the problem much subtler than counting paths in a fixed graph. Whether a long jump is legal depends on which points have already been visited, so the available moves change from state to state.

Mathematical Approach

Let \(V\) be the set of grid points, with \(|V|=n=wh\). In the actual problem \(w=h=4\), so \(n=16\). We want to count every valid sequence exactly once.

Step 1: Represent a Partial Password by a Set and an Endpoint

Suppose the current password prefix is

$P=(v_1,v_2,\dots,v_k),\qquad v_i\in V,\qquad v_i\ne v_j\quad(i\ne j).$

Define the visited set

$U=\{v_1,v_2,\dots,v_k\}.$

The key observation is that the future does not depend on the full order of the prefix. It depends only on:

$U,\qquad v_k.$

That is enough because a future move only asks two questions: is the destination still unused, and are all required interior points already in \(U\)? Since nodes are never revisited, the visited set grows monotonically.

Step 2: Characterize Interior Lattice Points on One Segment

Take two distinct nodes

$a=(x_a,y_a),\qquad b=(x_b,y_b).$

Set

$\Delta x=x_b-x_a,\qquad \Delta y=y_b-y_a,\qquad g=\gcd(|\Delta x|,|\Delta y|).$

A standard lattice-point fact says that the open segment from \(a\) to \(b\) contains exactly \(g-1\) lattice points. They are

$\left(x_a+t\frac{\Delta x}{g},\ y_a+t\frac{\Delta y}{g}\right),\qquad t=1,2,\dots,g-1.$

So if \(g=1\), the direction is primitive and there are no interior lattice points at all. If \(g>1\), those \(g-1\) intermediate points are precisely the nodes that must already have been used before the jump can be taken.

Step 3: Turn the Move Rule into a Set-Inclusion Test

For each ordered pair \((a,b)\) of distinct nodes, define \(R(a,b)\) as the set of interior lattice points on the open segment from \(a\) to \(b\).

Then a move from the current endpoint \(v\) to an unused node \(u\) is legal exactly when

$u\notin U,\qquad R(v,u)\subseteq U.$

This formulation separates geometry from search. All geometric information is contained in the precomputed sets \(R(a,b)\), and the dynamic part of the problem reduces to checking whether those required points are already present in the visited set.

Step 4: Derive the Memoized Recurrence

Let \(F(U,v)\) be the number of valid ways to extend the current state whose visited set is \(U\) and whose last node is \(v\).

If \(u\) is a legal next node, then appending \(u\) creates:

$1$

new password that stops immediately after \(u\), and also

$F(U\cup\{u\},u)$

longer passwords that continue from the new state. Therefore

$F(U,v)=\sum_{\substack{u\in V\setminus U\\ R(v,u)\subseteq U}}\left(1+F(U\cup\{u\},u)\right).$

If no legal destination exists, the sum is empty and \(F(U,v)=0\). Because every password has a unique last state before its final move, this recurrence counts every valid continuation exactly once.

Step 5: Worked Example on the \(4\times 4\) Grid

Consider the jump from \((0,3)\) to \((3,0)\). Here

$\Delta x=3,\qquad \Delta y=-3,\qquad g=\gcd(3,3)=3.$

So the interior lattice points are

$R\bigl((0,3),(3,0)\bigr)=\{(1,2),(2,1)\}.$

This means that a password prefix ending at \((0,3)\) may jump to \((3,0)\) only if both \((1,2)\) and \((2,1)\) have already been used. If either point is still unused, the jump is forbidden.

By contrast, the jump from \((0,0)\) to \((3,2)\) has

$g=\gcd(3,2)=1,$

so

$R\bigl((0,0),(3,2)\bigr)=\varnothing.$

That jump is immediately legal as soon as the destination itself is unused. This is exactly the distinction the recurrence exploits: some moves are always available, while others become available only after the right intermediate points have entered the visited set.

Step 6: Sum over All Starting Nodes

Each password has a unique starting node \(s\in V\). Once that first node is fixed, the remaining count is \(F(\{s\},s)\). Hence the total number of passwords is

$T=\sum_{s\in V} F(\{s\},s).$

Single-node prefixes are not counted as completed passwords here; every counted object arises from appending at least one further node, which matches the behavior of the implementations.

How the Code Works

The C++, Python, and Java implementations all follow the same plan. First they enumerate the \(16\) grid points by their Cartesian coordinates. Then, for every ordered pair of distinct nodes, they compute the gcd of the horizontal and vertical displacements, walk along the segment in primitive steps, and store the resulting set \(R(a,b)\) of required interior points.

Because the board has only \(16\) points, a visited set fits naturally into a bit mask. The same representation is used for each precomputed requirement set. This turns the legality test \(R(v,u)\subseteq U\) into a constant-time bit operation. The compiled implementations store memoized results in a flat table indexed by the visited mask and current endpoint, while the Python implementation stores the same state in a memo dictionary.

The search starts from every possible first node. At each state, the implementation scans all unused destinations, keeps only those whose required interior points are already present in the visited mask, and adds one for the password that ends immediately after the move plus the recursively computed number of longer continuations. Since each state is solved once, the algorithm avoids enumerating the enormous family of passwords explicitly.

Complexity Analysis

Let \(n=wh\) and let \(d=\max(w,h)\). Precomputing all segment requirements costs \(O(n^2 d)\), because for each ordered pair we may walk through up to \(g-1\le d-1\) intermediate lattice points. On the actual \(4\times 4\) board this cost is tiny.

The memoized search has at most \(n2^{n-1}\) reachable state descriptions \((U,v)\): for each endpoint \(v\), the visited set can be any subset containing \(v\). Each state tries up to \(n\) candidate next nodes, so the overall running time is \(O(n^2 2^n)\). The memory usage is \(O(n2^n+n^2)\), dominated by the memo table. For \(n=16\), this means at most \(16\cdot 2^{16}=1{,}048{,}576\) memo entries, which is easily manageable.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=879
2. Greatest common divisor: Wikipedia — Greatest common divisor
3. Lattice point: Wikipedia — Lattice point
4. Dynamic programming: Wikipedia — Dynamic programming
5. Bit array: Wikipedia — Bit array