Skip to content
Tutorials Center
My learning

Topics

Lesson 81 of 86 ยท Projects

Project: Puzzle and Seating Solver

Build a brute-force constraint solver for seating and who-does-what puzzles in JavaScript, then use it to check your own reasoning clue by clue.

Arrangement puzzles look hard because there are so many possible layouts. Computers are good at exactly that kind of problem. In this project you build a small brute-force solver: it lists every possible arrangement, throws away the ones that break a clue, and prints what is left. No cleverness is needed, only a clean way to write clues as code.

The solver is useful for more than fun. When you invent your own practice puzzles you can check that they have exactly one answer, and when you get stuck on a puzzle from Linear Seating Arrangements or Circular and Square Seating Arrangements, you can see which clue you misread. Brute force would be far too slow in an exam, so treat it as a lab for learning the human method.

The idea: generate, test, filter

A puzzle has three parts: the people (or objects), the seats, and the clues. A candidate layout is one way of placing every person in a seat, which is a permutation. Five people have 5! = 120 layouts; six have 720; ten already have 3,628,800. The solver tries them all and keeps those where every clue is true.

flowchart LR
    A["People list"] --> B["Generate every<br/>permutation"]
    B --> C{"Does the layout<br/>satisfy every clue?"}
    C -->|yes| D["Keep it"]
    C -->|no| E["Discard it"]
    D --> F["Print the survivors"]

Generate each layout, test it against all clues, keep the survivors.

A good puzzle has exactly one survivor. Zero survivors means the clues contradict each other; more than one means the puzzle is under-specified.

Writing clues as functions

The trick is to turn each clue into a small function that takes a layout (an array, seat 0 first) and returns true or false. Each helper is a clue factory: calling immediatelyLeft("Chen", "Dev") returns the test for that one clue.

JavaScript
const seat = (row, who) => row.indexOf(who);
const leftEnd = (p) => (row) => seat(row, p) === 0;
const immediatelyLeft = (a, b) => (row) => seat(row, a) + 1 === seat(row, b);

Sentences from a puzzle translate almost word for word:

Clue in words Code
"A sits at the left end" seat(row, "A") === 0
"A sits immediately to the left of B" seat(row, "A") + 1 === seat(row, "B")
"A and B are neighbors" Math.abs(seat(row, "A") - seat(row, "B")) === 1
"A is somewhere to the left of B" seat(row, "A") < seat(row, "B")
"A sits in the middle of five" seat(row, "A") === 2

Left and right here mean left and right as the row is drawn, from the viewer's side, which is also how most puzzles state it. If a puzzle says everyone faces north, left and right swap relative to someone looking at them. Decide the convention once and keep it.

Step 1: a linear solver

The first TryIt contains the whole solver. A generator function produces permutations lazily, so even large rows do not need a giant list in memory. Run it, then try adding or removing clues.

JS Solve a row of five

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Reading the result: of the 120 layouts, exactly one passes all four clues, so the puzzle is well formed. The puzzle text could be: "Five friends sit in a row. Asha is at the left end. Chen sits directly to the left of Dev. Asha and Bela are not neighbors. Bela is somewhere to the left of Chen. Find the order."

Step 2: watch the clues narrow the field

A solver that only prints the answer teaches little. This version applies the clues one at a time and prints how many layouts survive after each, which is exactly what you do on paper when you cross out impossible cases. It also shows why every clue matters: remove the last one and four layouts survive.

JS Clue-by-clue elimination

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The counts 120, 24, 6, 4, 1 are worth studying. Fixing Asha at the left end leaves 4! = 24 layouts. Gluing Chen and Dev into one block leaves 6. Each further clue prunes more. When you solve by hand, order the clues the same way: begin with the clues that fix a position or glue people together, because they remove the most possibilities.

Step 3: circular tables

A circular table changes two things. First, "next to" wraps around: seat 5 is next to seat 0 at a table of six. Second, rotating everyone one place gives the same arrangement, so the 720 raw permutations of six people contain each real arrangement six times. The standard fix is to fix one person at seat 0 and permute the others, which gives (n โˆ’ 1)! layouts (120 for six people).

Distances are measured as the clockwise gap (seat(b) - seat(a) + n) % n. A gap of 1 means b is the next person clockwise from a, a gap of n โˆ’ 1 means the next counter-clockwise, and a gap of n / 2 means directly opposite (for an even n).

JS Six people at a round table

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The answer is the order P, Q, R, S, T, U going clockwise. Check it against the clues by hand: Q follows P clockwise, S is three seats from P (opposite), R is two seats from P (not next to it), and T is opposite Q.

Step 4: who-does-what tables

Not every puzzle is about seats. In "who drinks what, and who travels how", each category is its own permutation: one assignment of drinks to people, one of transport to people. The brute force simply nests the loops: 3! drinks times 3! transport methods gives 36 combinations. With more categories you add more nested loops, and the count grows quickly, which is why the human tabulation method matters.

The example below also demonstrates the most useful thing a solver can do: tell you when your puzzle is under-specified. With four clues two answers survive. Adding a fifth clue removes one of them.

JS Who drinks what, who rides what

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Turning the solver into a puzzle checker

You now have everything needed to test your own puzzles. A tidy workflow:

  1. Write the people and the clues as plain sentences.
  2. Translate each sentence into one factory call.
  3. Run the solver. If it reports zero solutions, two clues contradict each other (or you coded one backwards).
  4. If it reports several, add a clue until exactly one remains.
  5. Solve the same puzzle by hand with a diagram and compare.

Step 5 is the learning step. The solver explores all layouts, while you must find a path of forced deductions. A good clue order is one in which every step is forced: no guessing, no backtracking.

Limits and extensions

Brute force breaks down fast: eight people give 40,320 layouts (instant), ten give 3.6 million (a second or two), but twelve give 479 million (minutes). Real solvers prune early, abandoning a partial layout as soon as one clue is already broken. You can try that as an extension: fill seats left to right and test each clue as soon as both of its people are seated. Other extensions: add middle(p), atEnd(p) and "exactly one person between A and B" helpers; support two-row tables where people face each other; or print the survivors as a text diagram.

If a clue says "A is not B's neighbor", remember that it is also satisfied when A is far away. Negative clues are weak, so a solver that applies them last (as above) gives the clearest picture of how strong each one is.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Five people can be arranged in a row in how many ways, before any clue is applied?

    Each arrangement is a permutation of five people: 5! = 5 x 4 x 3 x 2 x 1 = 120.
  2. 2. At a round table of six, you fix one person at seat 0 before generating layouts. How many layouts does the solver check?

    Rotations of the same arrangement are not different, so fixing one person leaves (6 - 1)! = 120 layouts.
  3. 3. A solver reports zero solutions for a puzzle. What is the most likely reason?

    Every layout fails at least one clue, so the clues cannot all be true together. Zero solutions never means 'many answers'.
  4. 4. In a circular solver the clockwise gap from a to b is (seat(b) - seat(a) + n) % n. For n = 8, which gap means 'directly opposite'?

    Opposite means half the table away, n / 2 = 4 seats. A gap of 1 is the next seat clockwise and 7 is the next seat counter-clockwise.
  5. 5. In the clue-by-clue run, fixing Asha at the left end reduced 120 layouts to 24. Why 24?

    With Asha's seat fixed, the remaining four people fill the remaining four seats in 4 x 3 x 2 x 1 = 24 ways.

Summary

  • A brute-force solver generates every permutation, keeps those where all clues are true, and prints the survivors.
  • Clues become small functions built by factories such as immediatelyLeft(a, b), so puzzle sentences translate almost word for word.
  • Fix one person at seat 0 for circular tables, and use a clockwise gap modulo n for neighbors and opposites.
  • Nest one permutation loop per category for who-does-what puzzles, and use the solution count to detect contradictory or under-specified clues.
  • The solver is a lab, not an exam tool: compare its survivors with your hand deductions to learn which clues to use first.

Next: practice what you have learned in Practice Set: Quantitative Aptitude.