Backtracking — Word Search in a Grid

board is a grid of single letters (an array of rows, each row an array of
one-character strings). Return true if word can be spelled by a path of
horizontally or vertically adjacent cells, using each cell at most once.

Start a depth-first search from every cell matching the first letter. Before
going deeper, mark the current cell as used; when the search comes back,
restore it. That restore is the backtracking: without it, a dead-end path
would block cells that another path needs.

Examples

board = [['A','B','C','E'],
         ['S','F','C','S'],
         ['A','D','E','E']]
solve(board, 'ABCCED')  → true
solve(board, 'SEE')     → true
solve(board, 'ABCB')    → false   // would reuse the B

Constraints

• 1 <= rows, columns <= 6, 1 <= word.length <= 15
• Letters are case-sensitive. The board must be left unchanged.