Solution

Answer: 4350069824940

Let the grid points be lattice points $(x,y)$ with $0 \le x,y < n$.

A password is the actual sequence of touched spots after the screen interprets skipped intermediate points.

The key subtlety is this:

If a move from $A$ to $B$ passes through unused intermediate spots, those spots are automatically inserted into the sequence.
Therefore, in the final interpreted password, every consecutive pair of spots must be “visible” to each other: there must be no unused lattice point strictly between them on the segment.

So we should count interpreted sequences directly.

1. Mathematical analysis

Suppose we are currently at point $P$, and the set of already-used points is $S$.

We may move next to an unused point $Q$ iff every lattice point strictly between $P$ and $Q$ is already in $S$.

Intermediate lattice points on a segment

Let

$$P=(x_1,y_1), \qquad Q=(x_2,y_2)$$

and define

$$dx=x_2-x_1,\qquad dy=y_2-y_1.$$

The number of equal subsegments along the line is

$$g=\gcd(|dx|,|dy|).$$

If $g=1$, there are no intermediate lattice points.
If $g>1$, the intermediate lattice points are

$$P + k\left(\frac{dx}{g},\frac{dy}{g}\right), \qquad k=1,2,\dots,g-1.$$

These are exactly the points that must already be used before we may jump from $P$ to $Q$.

2. Dynamic programming

We use DFS + memoization.

State:

$$(\text{mask},\text{last})$$

where

mask = bitmask of used points,
last = current endpoint.

Define:

$$f(\text{mask},\text{last})$$

= number of valid continuations, including the option to stop immediately.

Transition:

For every unused point $q$,

if all intermediate points between last and q are already used,
then we may extend to

$$f(\text{mask}\cup{q},q).$$

Thus

$$f(mask,last) = 1 + \sum_{\text{valid } q} f(mask\cup{q},q).$$

The 1 counts stopping at the current sequence.

Finally, start from every single starting point and subtract the length-1 passwords.

3. Python implementation

from functools import lru_cache
from math import gcd

def count_passwords(n):
    # Enumerate grid points
    points = [(x, y) for x in range(n) for y in range(n)]
    index = {p: i for i, p in enumerate(points)}

    N = n * n

    # between[a][b] = bitmask of lattice points strictly
    # between point a and point b
    between = [[0] * N for _ in range(N)]

    for a, (x1, y1) in enumerate(points):
        for b, (x2, y2) in enumerate(points):

            if a == b:
                continue

            dx = x2 - x1
            dy = y2 - y1

            g = gcd(abs(dx), abs(dy))

            # If g > 1, there are intermediate lattice points
            if g > 1:
                step_x = dx // g
                step_y = dy // g

                mask = 0

                for k in range(1, g):
                    p = (x1 + k * step_x,
                         y1 + k * step_y)
                    mask |= 1 << index[p]

                between[a][b] = mask

    FULL = (1 << N) - 1

    @lru_cache(None)
    def dfs(mask, last):
        """
        Number of valid continuations from this state,
        including the option to stop immediately.
        """
        total = 1

        unused = FULL ^ mask

        while unused:
            bit = unused & -unused
            q = bit.bit_length() - 1

            # Valid iff all intermediate points are already used
            if between[last][q] & ~mask == 0:
                total += dfs(mask | bit, q)

            unused ^= bit

        return total

    ans = 0

    # Start from every initial point
    for s in range(N):
        ans += dfs(1 << s, s) - 1   # remove length-1 password

    return ans

# Verification against the problem statement
print(count_passwords(3))   # 389488

# Required answer
print(count_passwords(4))

4. Code walkthrough

Building the grid

points = [(x, y) for x in range(n) for y in range(n)]

Creates all lattice points.

Computing intermediate points

For every ordered pair $(A,B)$, we compute:

g = gcd(abs(dx), abs(dy))

If $g>1$, there are lattice points on the segment.

We store all such intermediate points as a bitmask in:

between[a][b]

DFS state

dfs(mask, last)

means:

we have already used the points in mask,
the current finger position is last.

Valid move test

if between[last][q] & ~mask == 0:

This checks that every intermediate point is already used.

That exactly matches the touchscreen rule.

Verification

The program reproduces the example:

count_passwords(3) = 389488

which matches the problem statement.

Then it computes the $4\times4$ value.

5. Final verification

The answer is:

positive,
much larger than the $3\times3$ case (as expected),
still computationally feasible because there are only $2^{16}\cdot16$ memoized states.

The computation is exact integer arithmetic throughout.

Answer: 4350069824940

Project Euler Problem 879