March 20, 2026 Part 1
Martin has been working with the Claude AI code generation tool. You have to get the professional version because they don’t let the free version do much at all.
Specifically Claude Code v2.1.80 and Sonnet 4.6.
This thing is completely amazing. I gave it just partial headers and nothing in the C++ files but the top of file comment and it just took off and did it. Here’s the 1st part of the terminal session with my inputs bolded and my comments at the right in blue:
March 20, 2026 at 8:21:33 AM MDT
❯ what nonogram line solving algorithms do you know
⏺ Here are the main nonogram line solving algorithms:
Exact / Complete Methods
- Backtracking with constraint propagation — try placements recursively, prune early when constraints violated
- Dynamic programming (left-most / right-most shift) — compute the leftmost and rightmost valid positions for each clue block, then
cells where both agree are determined
Constraint-Based / Logic Methods
- Simple Box — for each clue block, overlap the leftmost and rightmost valid placement; the overlapping cells must be filled
- Simple Space — cells that cannot be covered by any valid placement are empty
- Edge/boundary logic — if a filled cell is at the edge of a possible block range, constrain neighbors
- Capping — if a filled segment's length matches a clue, mark adjacent cells as empty
- Merging — two adjacent filled segments that must belong to the same clue get connected
- Splitting — gaps that are too small for any remaining clue must be empty
More Advanced Heuristics
- Contradiction/forcing — hypothesize a cell is filled/empty, propagate consequences; if contradiction arises, the opposite is forced
- Set-based / BDD (Binary Decision Diagram) — enumerate all valid line solutions as a set, intersect across rows and columns
- Regex/NFA matching — model each line's valid solutions as a regular language, use NFA to find the intersection of possible states per
cell
Key Concepts Underlying Most Algorithms
- Clue permutation enumeration — explicitly list all valid arrangements of blocks on a line
- Interval arithmetic — track [min_start, max_start] for each block and derive certainties from overlaps
The DP overlap method (leftmost/rightmost placement) is the most commonly implemented efficient algorithm — O(n·k) per line where n is
line length and k is number of clues. Full solvers typically combine this with contradiction-based propagation for harder puzzles.
Want details on any specific one?
❯ add all constraint-based methods to the nonogram solver in this directory
While Claude is working:
✳ Razzmatazzing… (25m 59s · ↓ 15.3k tokens · thinking)
⎿ Tip: Use /btw to ask a quick side question without interrupting Claude's current work
. Julienning…
· Tinkering…
Searched for 1 pattern, read 2 files, recalled 1 memory (ctrl+o to expand)
⏺ Let me also check the data structures:
Read 2 files (ctrl+o to expand)
⏺ Let me use the Plan agent to design the implementation before writing code:
⏺ Plan(Plan constraint-based method additions)
⎿ Done (7 tool uses · 31.8k tokens · 2m 47s)
(ctrl+o to expand)
⏺ Now I'll implement the changes. Starting with the header:
⏺ Update(LineSolverCmdLine.hpp)
⎿ Added 16 lines
59
60 vector<short> pushLeft(); ///< Returns start positions of each clue pushed hard-left.
61 vector<short> pushRight(); ///< Returns start positions of each clue pushed hard-right.
62 +
63 + /// Tightens leftStarts/rightStarts using the boundary (board-edge or solved-empty)
64 + /// on each side of every contiguous solved-filled run. Returns false on contradiction.
65 + bool ApplyEdgeLogic(vector<short> &leftStarts, vector<short> &rightStarts);
66 +
67 + /// Marks the cell adjacent to the open end of a bounded run as solved-empty when
68 + /// exactly one clue of matching length can cover the run. Returns true if any cell changed.
69 + bool ApplyCapping (const vector<short> &leftStarts, const vector<short> &rightStarts);
70 +
71 + /// Fills every unsolved cell inside a fully pinned clue's span (leftStarts[i]==rightStarts[i]).
72 + /// Returns true if any cell changed.
73 + bool ApplyMerging (const vector<short> &leftStarts, const vector<short> &rightStarts);
74 +
75 + /// Marks every cell in an unsolved segment as solved-empty when no clue can fit there.
76 + /// Returns true if any cell changed.
77 + bool ApplySplitting(const vector<short> &leftStarts, const vector<short> &rightStarts);
78 };
79
⏺ Now update the .cpp — add the new static helpers and method implementations, then revise HardLeftHardRight:
⏺ Update(LineSolverCmdLine.cpp)
⎿ Added 250 lines
261 }
262
263 /* ------------------------------------------------------------------------ */
264 +// Cell Run
265 +/* ------------------------------------------------------------------------ */
266 +// Describes a contiguous run of solved-filled cells that share the same color.
267 +/* ------------------------------------------------------------------------ */
268 +struct CellRun {
269 + short start; ///< First cell of the run (inclusive).
270 + short end; ///< Last cell of the run (inclusive).
271 + unsigned char color; ///< Color of every cell in the run.
272 +};
273 +
274 +/* ------------------------------------------------------------------------ */
275 +// Find Filled Runs
276 +/* ------------------------------------------------------------------------ */
277 +// Populates 'runs' with every contiguous run of solved-filled cells in line.
278 +// Adjacent filled cells of different colors are treated as separate runs.
279 +/* ------------------------------------------------------------------------ */
280 +static void FindFilledRuns(const vector<solverCell> &line, short lineSize,
281 + vector<CellRun> &runs)
282 +{
283 + runs.clear();
284 + short i = 0;
285 + while (i < lineSize){
286 + if (!line[i].solved || line[i].isEmpty){ i++; continue; }
287 +
288 + short start = i;
289 + unsigned char color = line[i].color;
290 + while (i < lineSize && line[i].solved && !line[i].isEmpty && line[i].color == color)
291 + i++;
292 + runs.push_back({start, (short)(i - 1), color});
293 + }
294 +}
295 +
296 +/* ------------------------------------------------------------------------ */
297 +// Apply Edge Logic
298 +/* ------------------------------------------------------------------------ */
299 +// For every contiguous run of solved-filled cells whose left or right end
300 +// abuts a hard boundary (board edge or a solved-empty cell), the clue that
301 +// covers the run cannot start before (left-bounded) or end after (right-bounded)
302 +// that boundary. When exactly one candidate clue covers the run, its
303 +// leftStarts / rightStarts are tightened accordingly, and ordering constraints
304 +// are re-propagated. Returns false on contradiction.
305 +/* ------------------------------------------------------------------------ */
306 +bool LineSolverCmdLine::ApplyEdgeLogic(vector<short> &leftStarts,
307 + vector<short> &rightStarts)
308 +{
309 + short n = (short)clues.size();
310 + if (n == 0) return true; // No clues: no bounds to tighten; not a contradiction.
311 +
312 + vector<CellRun> runs;
313 + FindFilledRuns(theLine, lineSize, runs);
314 +
315 + bool changed = false;
316 +
317 + for (const CellRun &run : runs){
318 + bool leftBounded = (run.start == 0) ||
319 + (theLine[run.start - 1].solved && theLine[run.start - 1].isEmpty);
320 + bool rightBounded = (run.end == lineSize - 1) ||
321 + (theLine[run.end + 1].solved && theLine[run.end + 1].isEmpty);
322 +
323 + if (!leftBounded && !rightBounded) continue; // No boundary information to exploit.
324 +
325 + // Gather candidate clues: same color, reachable range spans the entire run.
326 + short soleCandidate = -1;
327 + short candidateCount = 0;
328 + for (short i = 0; i < n; i++){
329 + if (clues[i].color != run.color) continue;
330 + if (clues[i].realLength <= 0) continue;
331 + if (leftStarts[i] > run.start) continue; // Can't start early enough.
332 + if (rightStarts[i] + clues[i].realLength - 1 < run.end) continue; // Can't end late enough.
333 + soleCandidate = i;
334 + if (++candidateCount > 1) break;
335 + }
336 +
337 + if (candidateCount != 1) continue;
338 +
339 + short i = soleCandidate;
340 + bool tightened = false;
341 +
342 + if (leftBounded){
343 + // The clue must start at run.start (barrier prevents starting earlier).
344 + if (leftStarts[i] < run.start){
345 + leftStarts[i] = run.start;
346 + tightened = true;
347 + }
348 + }
349 +
350 + if (rightBounded){
351 + // The clue must end at run.end at the latest → start ≤ run.end - realLength + 1.
352 + short maxStart = run.end - clues[i].realLength + 1;
353 + if (rightStarts[i] > maxStart){
354 + rightStarts[i] = maxStart;
355 + tightened = true;
356 + }
357 + }
358 +
359 + if (tightened){
360 + if (leftStarts[i] > rightStarts[i])
361 + return false; // Contradiction.
362 + if (!PropagateBounds(clues, leftStarts, rightStarts))
363 + return false;
364 + changed = true;
365 + }
366 + }
367 +
368 + return true; // (changed is informational; caller doesn't need it from this method.)
369 +}
370 +