Part 6 and Part 7 of my video lecture series introducing the Standard Template Library are now available; they cover algorithms and functors.

Previous parts:

Part 1 (sequence containers)

Part 2 (associative containers)

Part 3 (smart pointers)

Part 4 (Nurikabe solver introduction)

Part 5 (Nurikabe solver conclusion)

My Nurikabe solver, available here, demonstrates how I use the STL components that I’ve talked about.  I’ve continued to optimize it; there’s more work to do, but I’ve already obtained dramatic speedups:

Here’s the changelog:

1.0 (8/24/2010) – First version, appearing in Channel 9’s Video Introduction to the STL, Part 4.

1.1 (9/1/2010) – Added 1 more puzzle from Wikipedia and 10 puzzles from Nikoli. Improved time formatting with microseconds/milliseconds/seconds. The time taken by initial construction and each step of analysis is now recorded.

1.2 (9/1/2010) – Massively accelerated hypothetical contradiction analysis by guessing cells in a deterministic but pseudorandomized order.

1.3 (9/8/2010) – Reorganized Grid::solve() into smaller member functions. Thanks, Corrector2!

1.4 (9/24/2010) – Accelerated hypothetical contradiction analysis further by prioritizing guesses near white cells. Thanks, Michael B.!

1.5 (10/19/2010) – Increased performance by making Grid::confined() use vector<vector<Flag>> instead of set<pair<int, int>>. Further increased performance by postponing Grid::detect_contradictions() until just before Grid::analyze_confinement().

1.6 (10/20/2010) – Removed Grid::analyze_isolated_unknown_regions(), which was successful exactly once (on wikipedia_hard), during both top-level analysis and hypothetical contradiction analysis. Removed Grid::operator=()’s definition and entirely removed Grid::swap(), as they were unused. Avoided copying m_output in Grid’s private copy ctor, as it isn’t needed during hypothetical contradiction analysis. Even if, in the future, the solver is extended to capture the outp