Sokoban Optimization ✨

Scoring

A score measures how much of the starting gap a system resolves across all ten boards. For each board, use its strongest independently verified lower bound and shortest verified solution. Every push of gap closed earns the same credit.

Any valid lower-bound proof counts once independently verified, whatever method produced it. A proof that the best solution is optimal closes a board’s whole gap. A score of 100% means the lower and upper bounds meet on every board. The starting bounds are fixed for each benchmark version.

Each push flips one box’s checkerboard color, so every solution to a fixed board has the same push-count parity. The judge rounds lower bounds up to that parity. Gaps close in steps of two pushes; .

Evidence & sources

Baseline lower bounds checked

Baseline solutions replayed

The judge replays solutions and counts box pushes. Built-in certificates provide automatic lower-bound checks. A SAT/UNSAT route automatically checks LRAT proofs that a proposed push limit is impossible. Other proofs can be independently reviewed; submissions with pending proofs await a final score. Board hashes bind the evidence to the exact puzzle layout.