0040MediumArrayStringBacktrackingDepth-First SearchMatrix

Tablet Glyph Trail

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A conservation lab photographs a stone tablet as a grid tablet of glyph marks, one mark per square: tablet[r][c] is a one-character string.

A restorer wants to know whether the inscription mark_run was cut into the stone as a single continuous trail. A trail begins on any square, and from the square it currently occupies it moves to a square sharing a side with it (up, down, left or right; a diagonal hop is never a cut). Reading the marks in the order the trail occupies them must reproduce mark_run from front to back, and one trail may not occupy the same square twice.

Marks are case sensitive, so "g" and "G" count as different glyphs.

Return true when at least one such trail exists, and false when none does.

Examples

Example 1

Input: tablet = [["s","n","e"],["t","o","r"],["a","d","k"]], mark_run = "stone"
Output: true

One trail runs (0,0) -> (1,0) -> (1,1) -> (0,1) -> (0,2), picking up s, t, o, n, e in that order.

Example 2

Input: tablet = [["s","n","e"],["t","o","r"],["a","d","k"]], mark_run = "stored"
Output: false

Every trail spelling s, t, o, r, e reaches the square holding e in the top right corner, and no square beside it carries d.

Example 3

Input: tablet = [["h","i"]], mark_run = "hih"
Output: false

Only two squares exist, so the third mark would have to reuse the square already occupied by the first, which a trail may not do.

Constraints

rows == tablet.length
cols == tablet[r].length
1 <= rows, cols <= 6
1 <= mark_run.length <= 15
Every entry of tablet and every character of mark_run is a single uppercase or lowercase English letter.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def trail_exists(tablet: list[list[str]], mark_run: str) -> bool:

Java

public boolean trailExists(char[][] tablet, String mark_run)

The intended approach

Time O(rows * cols * 3^L) where L is len(mark_run), since after the first step only three neighbours are ever worth tryingSpace O(L) for the recursion; the tablet is marked in place, so no copy is made

Start a depth-first trail from every square whose mark matches the first character. Before recursing into the neighbours, overwrite the current square with `#`, a mark the alphabet cannot hold, so deeper steps of that trail cannot land on it; restore the original mark once the branch is exhausted, which is what allows a later trail to pass through the same square. A branch stops as soon as the mark under it disagrees with the character it needs.

Pythonentry point: trail_exists

def trail_exists(tablet, mark_run):
    rows, cols = len(tablet), len(tablet[0])
    need = len(mark_run)

    def walk(r, c, k):
        if tablet[r][c] != mark_run[k]:
            return False
        if k == need - 1:
            return True
        keep = tablet[r][c]
        tablet[r][c] = "#"
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and tablet[nr][nc] != "#":
                if walk(nr, nc, k + 1):
                    tablet[r][c] = keep
                    return True
        tablet[r][c] = keep
        return False

    for r in range(rows):
        for c in range(cols):
            if walk(r, c, 0):
                return True
    return False

The obvious version

For each starting square, enumerate every sequence of L-1 orthogonal moves outright and check the resulting path: inside the grid, marks matching, no square repeated. O(rows * cols * 4^L) and no recursion or in-place marking involved.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_trail_exists(tablet, mark_run):
    from itertools import product
    rows, cols = len(tablet), len(tablet[0])
    steps = ((-1, 0), (1, 0), (0, -1), (0, 1))
    for r0 in range(rows):
        for c0 in range(cols):
            if tablet[r0][c0] != mark_run[0]:
                continue
            if len(mark_run) == 1:
                return True
            for moves in product(steps, repeat=len(mark_run) - 1):
                r, c = r0, c0
                path = [(r0, c0)]
                good = True
                for k, (dr, dc) in enumerate(moves, start=1):
                    r, c = r + dr, c + dc
                    if not (0 <= r < rows and 0 <= c < cols):
                        good = False
                        break
                    if (r, c) in path or tablet[r][c] != mark_run[k]:
                        good = False
                        break
                    path.append((r, c))
                if good:
                    return True
    return False

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in