Constraint Pruning on Grids & Boards

Foundations

So far, every branch ran to full length before its result was kept or thrown away. Now, what if a rule decides early that a partial path can never succeed, so finishing it would only waste work?

Check the rule at every placement, not at the end. If the newest choice breaks it, return at once: the whole subtree below that choice is skipped. On a grid or board, the rules are usually stay in bounds, step to an adjacent cell, never reuse a cell on the current path, which is the last lesson's used flag, and fit whatever the next placement requires.

Build orderings of nums = [7, 1, 5, 3, 6] in which neighbors differ by at least 2. After 7, the candidates 1, 5, and 3 keep the rule. Placing 6 next to 7 breaks it at once, a gap of 1, so that branch returns before any third element is tried, and the 3! = 6 orderings that would extend it are never built.

• Graphs

  A grid is a graph whose neighbors are the four adjacent cells. That lesson walks one the same way.

  Open lesson

Case Scenario

Word Search asks whether word can be spelled on a letter board by moving between adjacent cells without reusing one. Each placement must match the next letter and stay off the current path, so a mismatch kills a branch after one step. For word = "ABCCED" on the example board, the path A, B, C, C, E, D exists, so the answer is True.

The direct approach enumerates paths and checks each one only once it is complete: every walk of length L from every start, then a test of whether it spells the word. That is up to m · n · 4ᴸ paths, though a path that starts with the wrong letter fails at its first step, and one that reuses a cell is invalid from that step on.