BitGrid

BitGrid is a low-level C constraint-solving engine for Hitori puzzles.

It expands a coursework Hitori assignment into a portfolio-level systems-style C project focused on compact memory representation, byte-level state encoding, explicit heap ownership, graph connectivity validation, recursive search, CLI tooling, benchmark instrumentation, and memory-safety hardening.

Current status: Phase 14 post-review quality hardening. The engine has compact cells, owned boards, strict parsing, deterministic writing, state transitions, deduction rules, sound forced-white gate logic, independent validation, clone-based recursive search, explanation traces, benchmark instrumentation, focused tests, file-based regression fixtures, and a CLI for inspection, solving, explanation, validation, and benchmarking.

Why C

BitGrid is intentionally written in C because the project is about systems-level engineering concerns:

• compact row-major board storage
• byte-level bit masks and state flags
• explicit create/destroy ownership contracts
• pointer and index validation
• custom low-level data structures
• deterministic recursive search and rollback
• external memory-safety tools such as Valgrind, AddressSanitizer, and UndefinedBehaviorSanitizer

The goal is not to build a GUI puzzle app. The goal is to make representation, ownership, correctness, and instrumentation visible in a small C engine.

Implemented Features

• cell: one-byte cell representation with black, circle, reserved, and number bits.
• board: owned row-major board allocation, destruction, cloning, indexing, get, and set helpers.
• parser: strict numeric .puz parsing with malformed-input rejection and cleanup on failure.
• writer: deterministic numeric board output that masks away state bits.
• state: black/circle decisions, contradiction handling, and neighbor propagation.
• rules: deterministic Hitori deductions, including unique cells, circled duplicate propagation, sandwich patterns, doublets, and forced-white gate deductions.
• validate: independent duplicate, adjacent-black, and white-connectivity validation.
• solver: fixed-point propagation plus clone-based recursive search.
• structures: owned bounded size_t queue used by graph traversal.
• log: optional structured trace events for deductions, rule passes, guesses, branches, and final status.
• bench: single-puzzle timing and solver-counter instrumentation.
• main: thin CLI dispatch for user-facing commands.

Build And Test

Expected compiler flags:

gcc -Wall -Wextra -std=gnu99

Build the CLI:

make

Run smoke and unit tests:

make test

Run the benchmark smoke command:

make bench

Run stricter warning and regression checks:

make harden

Run memory-safety targets:

make asan
make ubsan
make valgrind

On native Windows, the binary is usually bitgrid.exe; on Unix-like environments it is usually bitgrid.

CLI Examples

./bitgrid help
./bitgrid inspect tests/fixtures/valid_3x3.puz
./bitgrid solve tests/fixtures/valid_3x3.puz
./bitgrid solve tests/fixtures/search_3x3.puz --logic-only
./bitgrid solve tests/fixtures/search_3x3.puz --search
./bitgrid solve tests/fixtures/search_3x3.puz --search --explain
./bitgrid validate tests/fixtures/valid_3x3.puz
./bitgrid bench tests/fixtures/search_3x3.puz --search

PowerShell users can substitute ./bitgrid.exe.

Help output:

BitGrid CLI
Usage:
  bitgrid help
  bitgrid inspect <puzzle.puz>
  bitgrid solve <puzzle.puz> [--logic-only|--search] [--explain]
  bitgrid validate <puzzle.puz>
  bitgrid bench <puzzle.puz> [--logic-only|--search]

Inspect output:

dimensions: 3 x 3
3 3
1 2 3
4 5 6
7 8 9

Search with explanation:

status: solved
nodes: 2
guesses: 1
3 3
B2 O3 O2
O3 O2 O1
B1 O1 B1
trace:
  deduction circle r1 c2 count=1: unique active number
  deduction circle r2 c1 count=1: unique active number
  deduction circle r2 c2 count=1: unique active number
  deduction circle r3 c2 count=1: sandwich middle must stay white
  deduction black r3 c3 count=2: doublet removes other row match
  rule-pass count=6: rule pass changed board
  deduction black r3 c1 count=1: circled number removes row peer
  rule-pass count=1: rule pass changed board
  rule-pass: rule pass reached fixed point
  guess r1 c1: first undecided cell
  branch black r1 c1: try black branch
    deduction circle r1 c3 count=1: unique active number
    rule-pass count=1: rule pass changed board
    rule-pass: rule pass reached fixed point
  branch-result black r1 c1: solved
  finish: solved

Benchmark output:

puzzle: tests/fixtures/search_3x3.puz
mode: search
status: solved
rows: 3
cols: 3
nodes: 2
guesses: 1
elapsed_ms: 0.000

Puzzle File Format

The current .puz format is numeric and strict:

3 3
1 2 3
4 5 6
7 8 9

The first line contains row and column counts. The remaining tokens contain exactly rows * cols numeric values in the range 1..31. The parser rejects zero dimensions, malformed dimensions, short input, extra data, out-of-range values, unreadable files, and oversized dimensions that would overflow board allocation.

Cell Layout

Each board cell is stored in one byte:

bit 7      bit 6      bit 5      bits 4-0
BLACK      CIRCLE     RESERVED   NUMBER

Implemented masks:

#define CELL_BLACK  0x80u
#define CELL_CIRCLE 0x40u
#define CELL_NUMBER 0x1Fu

State helpers preserve number bits when black or circle flags change. Raw bit operations are centralized in the cell module.

Memory Ownership

Boards are owned heap objects:

typedef struct {
    size_t rows;
    size_t cols;
    Cell *cells;
} Board;

The caller owns boards returned by board_create, board_clone, and successful parser calls, and must release them with board_destroy.

Board *board_create(size_t rows, size_t cols);
void board_destroy(Board *board);
Board *board_clone(const Board *board);

Parser, solver, validator, trace, queue, and benchmark paths are written around explicit cleanup on failure.

Testing And Memory Safety

The test suite includes CLI smoke checks and focused C tests for:

• benchmark reporting
• trace ownership and event growth
• queue ownership and FIFO behavior
• cell masks and flag preservation
• board allocation, indexing, cloning, and malformed board rejection
• parser and writer behavior
• state transitions and contradictions
• deduction rules and gate logic
• independent validation and connectivity
• solver search, rollback, and traced/untraced consistency

The project has Make targets for ASan, UBSan, and Valgrind. These are required hardening checks before stronger public memory-safety claims. If local policy blocks freshly built binaries in an ordinary shell, run the targets from an administrator PowerShell or another supported environment and record the result.

Known Limitations

• Solver status distinguishes logic-only stalls from exhausted search failure.
• Gate deduction is intentionally limited to candidates whose black branch would disconnect already forced white cells.
• Search rollback is clone-based. A custom undo log would be a future optimization.
• Benchmarking currently runs one puzzle at a time and prints human-readable metrics. Directory traversal, CSV/JSON output, and statistical multi-run reporting are future work.
• The solver uses a simple row-major branching heuristic.
• Explanation output is operational rather than a polished human proof system.
• Hitori is the only puzzle proving ground; broader puzzle abstraction is intentionally out of scope.

Documentation

• Design notes
• Testing notes
• Reviewer walkthrough
• Project specification
• AI-native builder journal
• Agent instructions
• Phase closeouts

Portfolio Positioning

BitGrid demonstrates systems-style C engineering beyond ordinary coursework: compact data layout, manual ownership, byte-level state encoding, deterministic rule propagation, graph traversal, recursive search, CLI tooling, benchmark instrumentation, and memory-safety discipline.

It should not be described as kernel, embedded, compiler, database, or production infrastructure experience. The accurate claim is narrower and stronger: BitGrid is a focused C engine where memory layout, correctness, and explicit ownership matter.