Video Introduction to the STL, Parts 6 and 7
Part 1 (sequence containers)
Part 2 (associative containers)
Part 3 (smart pointers)
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