Skip to content

Releases: guillaumeast/42_rush01

Early pruning with partial visibility checks (sub-ms performance)

17 Oct 23:04

Choose a tag to compare

Adds early pruning logic to dynamically reject impossible branches based on partial visibility counts.

Each row and column is now checked in real-time while filling the grid, ensuring only valid branches are explored.

Performance results:

6x6 = < 1 ms
7x7 = < 1 ms
8x8 = < 1 ms
9x9 = < 1 ms

The solver now handles all grids up to 9×9 in sub-millisecond time.

Pre-fill obvious values before backtracking

17 Oct 22:07

Choose a tag to compare

Pre-filling of obvious values (clue = n → full row/column, clue = 1 → cell = n) before backtracking.

Speedup compared to v1.0.0:

6x6 = 4 ms (vs 66 ms)
7x7 = 5 510 ms (vs 652 200 ms)
8x8 = n.a. (> 30 min)
9x9 = n.a. (> 30 min)

Unoptimized backtracking solver

17 Oct 19:34

Choose a tag to compare

Naive backtracking with a full-row/full-column uniqueness scan and final clue checks.

6x6 = 66ms
7x7 = 652 200 ms
8x8 = n.a. (> 30 min)
9x9 = n.a. (> 30 min)