Café Letter Board
A café has a wall board of wooden letter tiles in a grid. On quiz night, teams answer by tracing their word on the board: they start on any tile and slide a finger to a tile directly above, below, left or right for each next letter. Diagonals are not allowed, and no tile may be used twice in the same word.
The quiz host wants a quick way to check whether a team's answer can really be traced on tonight's board.
Your task
Write canTrace(board, word). board is a list of equal-length strings, one per row, so board[r][c] is the letter in row r, column c. Return true if word can be traced as described, and false otherwise.
Consecutive letters must be on tiles that share a side, and each tile can be used at most once per word.
canTrace(board: string[], word: string) → bool
Examples
board = ["CAT", "ORE", "WEB"] word = "CORE"
true
The board isC A TO R EW E B
Start on C (top left), go down to O, right to R, right to E. Every step moves to a side neighbour.
board = ["CAT", "ORE", "WEB"] word = "BEER"
false
B touches both Es, but the two Es (row 1, column 2 and row 2, column 1) touch each other only diagonally. Diagonal steps are not allowed, so you can never step from one E to the other.
board = ["CAT", "ORE", "WEB"] word = "RARE"
false
R, A, R would need the R tile twice: there is only one R, and a tile cannot be used twice in the same word.
Constraints
- 1 ≤ number of rows, number of columns ≤ 6
- 1 ≤ word.length ≤ 15
- board and word contain only uppercase letters A to Z.
Start with brute force
From every tile, follow every possible walk of the word's length (up to four choices per step) and compare the letters only at the end. On a 6 × 6 board with a 15-letter word that is 36 × 414, around 9.7 billion walks.
Almost all of them go wrong on the second or third letter. Checking each letter the moment you step on it, and turning back right away when it does not match, removes nearly all of that work.
Hints
0 of 4 shown- Hint 1
On the example board, the word CORE can only start on the C. Once you are standing on C, where can the O be?
- Hint 2
The next letter must be on one of at most four side neighbours, and the one after that must neighbour that tile. A path either keeps matching or fails the moment a letter is wrong, and when it fails you go back and try another neighbour.
- Hint 3
Write
trace(r, c, k): can the rest of the word, from letterk, be traced starting at tile (r, c)? It fails if the tile is off the board, already used, or holds the wrong letter. It succeeds ifkis the last letter. Otherwise ask the four neighbours withk + 1. - Hint 4
Mark the tile as used before asking the neighbours, and unmark it afterwards, whether they succeeded or not. Then call
trace(r, c, 0)from every tile and returntrueif any call does.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Tracing a word is a walk where each step must land on the right letter. Depth-first search with backtracking follows one path as far as it matches, and steps back to try another neighbour the moment it fails.
Trace CORE on the example board:
- Tiles other than C fail at once on the first letter. At C (row 0, column 0), mark it and look for O among its neighbours.
- Right is A: wrong letter. Down is O: match. Mark it and look for R.
- From O: up is C, already used. Down is W: wrong. Right is R: match. Mark it and look for E.
- From R: up is A, wrong. Down is E (row 2, column 1): it is the last letter, so return
trueall the way up.
The unmark step matters. On a board like SEA / ETT / ESA with the word TASTE, a first attempt can mark a T, an A and an S and then fail. If those stay marked, the correct path, which needs one of them, is blocked and you wrongly return false.
function canTrace(board, word) {
const rows = board.length, cols = board[0].length;
const used = board.map(() => new Array(cols).fill(false));
// can word[k..] be traced starting at tile (r, c)?
function trace(r, c, k) {
if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
if (used[r][c] || board[r][c] !== word[k]) return false;
if (k === word.length - 1) return true; // last letter matched
used[r][c] = true;
const found = trace(r - 1, c, k + 1) || trace(r + 1, c, k + 1) ||
trace(r, c - 1, k + 1) || trace(r, c + 1, k + 1);
used[r][c] = false; // free the tile for other paths
return found;
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (trace(r, c, 0)) return true;
}
}
return false;
}def can_trace(board, word):
rows, cols = len(board), len(board[0])
used = [[False] * cols for _ in range(rows)]
def trace(r, c, k):
# can word[k:] be traced starting at tile (r, c)?
if r < 0 or c < 0 or r >= rows or c >= cols:
return False
if used[r][c] or board[r][c] != word[k]:
return False
if k == len(word) - 1:
return True # last letter matched
used[r][c] = True
found = (trace(r - 1, c, k + 1) or trace(r + 1, c, k + 1) or
trace(r, c - 1, k + 1) or trace(r, c + 1, k + 1))
used[r][c] = False # free the tile for other paths
return found
return any(trace(r, c, 0) for r in range(rows) for c in range(cols))Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.