nurikabe.cpp

// Copyright (c) Microsoft Corporation. All rights reserved.
// Licensed under the MIT License.

// Nurikabe Solver by Stephan T. Lavavej
// https://en.wikipedia.org/wiki/Nurikabe_(puzzle)

// cl /EHsc /nologo /W4 /std:c++17 /MT /O2 /GL nurikabe.cpp && nurikabe && wikipedia_hard.html

#include <stddef.h>
#include <stdlib.h>
#include <algorithm>
#include <array>
#include <chrono>
#include <exception>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <ostream>
#include <queue>
#include <random>
#include <ratio>
#include <regex>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
using namespace std::chrono;

class Grid {
public:
    Grid(int width, int height, const string& s);

    enum SitRep {
        CONTRADICTION_FOUND,
        SOLUTION_FOUND,
        KEEP_GOING,
        CANNOT_PROCEED
    };

    SitRep solve(bool verbose = true, bool guessing = true);

    int known() const;

    void write(ostream& os, steady_clock::time_point start, steady_clock::time_point finish) const;

private:
    // The states that a cell can be in. Numbered cells are positive,
    // which is why this has an explicitly specified underlying type.
    enum State : int {
        UNKNOWN = -3,
        WHITE = -2,
        BLACK = -1
    };

    // Each region is black, white, or numbered. This allows us to
    // remember when white cells are connected to numbered cells,
    // as the whole region is marked as numbered.
    // Each region keeps track of the coordinates that it occupies.
    // Each region also keeps track of the unknown cells that it's surrounded by.
    class Region {
    public:
        Region(const State state, const int x, const int y, const set<pair<int, int>>& unknowns)
            : m_state(state), m_coords(), m_unknowns(unknowns) {

            if (state == UNKNOWN) {
                throw logic_error("LOGIC ERROR: Grid::Region::Region() - state must be known!");
            }

            m_coords.insert(make_pair(x, y));
        }


        bool white() const {
            return m_state == WHITE;
        }

        bool black() const {
            return m_state == BLACK;
        }

        bool numbered() const {
            return m_state > 0;
        }

        int number() const {
            if (!numbered()) {
                throw logic_error(
                    "LOGIC ERROR: Grid::Region::number() - This region is not numbered!");
            }

            return m_state;
        }


        set<pair<int, int>>::const_iterator begin() const {
            return m_coords.begin();
        }

        set<pair<int, int>>::const_iterator end() const {
            return m_coords.end();
        }

        int size() const {
            return static_cast<int>(m_coords.size());
        }

        bool contains(const int x, const int y) const {
            return m_coords.find(make_pair(x, y)) != m_coords.end();
        }

        template <typename InIt> void insert(InIt first, InIt last) {
            m_coords.insert(first, last);
        }


        set<pair<int, int>>::const_iterator unk_begin() const {
            return m_unknowns.begin();
        }

        set<pair<int, int>>::const_iterator unk_end() const {
            return m_unknowns.end();
        }

        int unk_size() const {
            return static_cast<int>(m_unknowns.size());
        }

        template <typename InIt> void unk_insert(InIt first, InIt last) {
            m_unknowns.insert(first, last);
        }

        void unk_erase(const int x, const int y) {
            m_unknowns.erase(make_pair(x, y));
        }

    private:
        State m_state;
        set<pair<int, int>> m_coords;
        set<pair<int, int>> m_unknowns;
    };

    typedef map<shared_ptr<Region>, set<pair<int, int>>> cache_map_t;

    bool analyze_complete_islands(bool verbose);
    bool analyze_single_liberties(bool verbose);
    bool analyze_dual_liberties(bool verbose);
    bool analyze_unreachable_cells(bool verbose);
    bool analyze_potential_pools(bool verbose);
    bool analyze_confinement(bool verbose, cache_map_t& cache);
    vector<pair<int, int>> guessing_order();
    bool analyze_hypotheticals(bool verbose);

    // We use an upper-left origin.
    // This is convenient during construction and printing.
    // It's irrelevant during analysis.

    bool valid(int x, int y) const;

    State& cell(int x, int y);
    const State& cell(int x, int y) const;

    shared_ptr<Region>& region(int x, int y);
    const shared_ptr<Region>& region(int x, int y) const;

    void print(const string& s, const set<pair<int, int>>& updated = {},
        int failed_guesses = 0, const set<pair<int, int>>& failed_coords = {});
    bool process(bool verbose, const set<pair<int, int>>& mark_as_black,
        const set<pair<int, int>>& mark_as_white, const string& s,
        int failed_guesses = 0, const set<pair<int, int>>& failed_coords = {});

    template <typename F> void for_valid_neighbors(int x, int y, F f) const;
    void insert_valid_neighbors(set<pair<int, int>>& s, int x, int y) const;
    void insert_valid_unknown_neighbors(set<pair<int, int>>& s, int x, int y) const;

    void add_region(int x, int y);
    void mark(State s, int x, int y);
    void fuse_regions(shared_ptr<Region> r1, shared_ptr<Region> r2);

    bool impossibly_big_white_region(int n) const;

    bool unreachable(int x_root, int y_root,
        set<pair<int, int>> discovered = {}) const;

    bool confined(const shared_ptr<Region>& r, cache_map_t& cache,
        const set<pair<int, int>>& verboten = {}) const;

    bool detect_contradictions(bool verbose, cache_map_t& cache);


    int m_width; // x is valid within [0, m_width).
    int m_height; // y is valid within [0, m_height).
    int m_total_black; // The total number of black cells that will be in the solution.

    // m_cells[x][y].first is the state of a cell.
    // m_cells[x][y].second is the region of a cell.
    // (If the state is unknown, the region is empty.)
    vector<vector<pair<State, shared_ptr<Region>>>> m_cells;

    // The set of all regions can be traversed in linear time.
    set<shared_ptr<Region>> m_regions;

    // This is initially KEEP_GOING.
    // If an attempt is made to fuse two numbered regions, or to mark an already known cell,
    // this is set to CONTRADICTION_FOUND.
    SitRep m_sitrep;

    // This stores the output that is generated during solving, to be converted into HTML later.
    vector<tuple<string, vector<vector<State>>, set<pair<int, int>>, steady_clock::time_point,
        int, set<pair<int, int>>>> m_output;

    // This is used to guess cells in a deterministic but pseudorandomized order.
    mt19937 m_prng;

    Grid(const Grid& other);
    Grid& operator=(const Grid&) = delete;
};

string format_time(const steady_clock::time_point start, const steady_clock::time_point finish) {
    ostringstream oss;

    if (finish - start < 1ms) {
        oss << duration_cast<duration<double, micro>>(finish - start).count() << " microseconds";
    } else if (finish - start < 1s) {
        oss << duration_cast<duration<double, milli>>(finish - start).count() << " milliseconds";
    } else {
        oss << duration_cast<duration<double>>(finish - start).count() << " seconds";
    }

    return oss.str();
}

int main() {
    struct Puzzle {
        const char * name;
        int w;
        int h;
        const char * s;
    };

    const array<Puzzle, 12> puzzles = { {
        {
            "wikipedia_hard", 10, 9,
            "2        2\n"
            "      2   \n"
            " 2  7     \n"
            "          \n"
            "      3 3 \n"
            "  2    3  \n"
            "2  4      \n"
            "          \n"
            " 1    2 4 \n"
        },

        {
            "wikipedia_easy", 10, 10,
            "1   4  4 2\n"
            "          \n"
            " 1   2    \n"
            "  1   1  2\n"
            "1    3    \n"
            "  6      5\n"
            "          \n"
            "     1   2\n"
            "    2  2  \n"
            "          \n"
        },

        {
            "nikoli_1", 10, 10,
            "       5 2\n"
            "3         \n"
            " 4  2     \n"
            "      3   \n"
            " 4   4    \n"
            "         3\n"
            "          \n"
            "          \n"
            " 3  3     \n"
            "  1  1 3 3\n"
        },

        {
            "nikoli_2", 10, 10,
            "6 2 3    3\n"
            "          \n"
            "         4\n"
            "          \n"
            "    2    2\n"
            "3    5    \n"
            "          \n"
            "3         \n"
            "          \n"
            "4    5 4 1\n"
        },

        {
            "nikoli_3", 10, 10,
            " 3    4   \n"
            "     6    \n"
            "       2  \n"
            "      3   \n"
            "        2 \n"
            " 4     3  \n"
            "         1\n"
            " 10      3 \n"
            "          \n"
            "  3      2\n"
        },

        {
            "nikoli_4", 18, 10,
            "  4            1 3\n"
            " 3    5   1 2     \n"
            "       5 3        \n"
            "            2 3   \n"
            "  4             3 \n"
            " 3             4  \n"
            "   1 1            \n"
            "        3 4       \n"
            "     1 1   5    5 \n"
            "4 4            3  \n"
        },

        {
            "nikoli_5", 18, 10,
            " 1 1    1     1   \n"
            "    5    2     1  \n"
            "        1     1   \n"
            "     5         1  \n"
            "1 1       4   1   \n"
            " 1     3     7    \n"
            "  3              6\n"
            "    4   2  4      \n"
            "      5         5 \n"
            " 1           5    \n"
        },

        {
            "nikoli_6", 18, 10,
            "                  \n"
            "1    12     3 12    \n"
            "                 2\n"
            "2    3     3    3 \n"
            "    1     1       \n"
            "3    1            \n"
            "   2  2 3 2       \n"
            "2           1     \n"
            "  3               \n"
            "1              12 1\n"
        },

        {
            "nikoli_7", 24, 14,
            "    5                   \n"
            "          2 6    7 3   4\n"
            "  1    5        3 5     \n"
            " 7   6                 1\n"
            "        4               \n"
            "   1      1   5      3  \n"
            "  2  3                  \n"
            "        3   3   2  7    \n"
            "                        \n"
            "6   1    5   5   1    5 \n"
            "      6        5     3  \n"
            "   4               4    \n"
            " 5          1           \n"
            "        3 4     5       \n"
        },

        {
            "nikoli_8", 24, 14,
            "    2 1           5 5   \n"
            "  4             12     1 \n"
            " 7      1               \n"
            "              1        3\n"
            "          7             \n"
            "6            5          \n"
            "           6           1\n"
            "9           15           \n"
            "          3            3\n"
            "             8          \n"
            "2        8              \n"
            "               4      3 \n"
            " 4     5             3  \n"
            "   8 3           2 4    \n"
        },

        {
            "nikoli_9", 36, 20,
            "2   2  1  1               1         \n"
            "   4    3        9      8      5    \n"
            "      1        7                   5\n"
            "4      1  1  4              2    1  \n"
            "      2  3         2         1 3    \n"
            "4   2           5    2              \n"
            "       1  1 17          3 4        4 \n"
            "                 9              21  2\n"
            "2       2                 4         \n"
            "  7  4            3   13             \n"
            "          1               6    1    \n"
            "  4      2    9  1                  \n"
            "     6               3          9   \n"
            "22                  1      8  1      \n"
            "   1   6   1   4                    \n"
            "    2     2     1      1       1   1\n"
            "                  4     2           \n"
            "   3 3   2   2       8      2     3 \n"
            "            1              1        \n"
            "                3       5       5   \n"
        },

        {
            "nikoli_10", 36, 20,
            "           4            2           \n"
            "3 4          2   7         8      2 \n"
            "    7      5   1   8 5   1  2  4   2\n"
            "6    4       3          2 2         \n"
            "           6                   4    \n"
            "    2             1  2           2  \n"
            "        1       4     4    4  1     \n"
            " 1                  3            4 4\n"
            "     2     4  4            4        \n"
            "       5  3                   2 4   \n"
            " 5 1              1    3   8   2    \n"
            "     1   2                          \n"
            "2            2 5           4     2 1\n"
            "                             2      \n"
            "1  2   4  7   18   1            1   1\n"
            "                     2   8 4        \n"
            "    3           18     1          4  \n"
            "                 4                4 \n"
            "      3 1   4      4    2    4   4  \n"
            "6      1  3                 4       \n"
        },
    } };

    try {
        for (const auto& puzzle : puzzles) {
            const auto start = steady_clock::now();

            Grid g(puzzle.w, puzzle.h, puzzle.s);

            while (g.solve() == Grid::KEEP_GOING) { }

            const auto finish = steady_clock::now();


            ofstream f(puzzle.name + string(".html"));

            g.write(f, start, finish);


            cout << puzzle.name << ": " << format_time(start, finish) << ", ";

            const int k = g.known();
            const int cells = puzzle.w * puzzle.h;

            cout << k << "/" << cells << " (" << k * 100.0 / cells << "%) solved" << endl;
        }
    } catch (const exception& e) {
        cerr << "EXCEPTION CAUGHT! \"" << e.what() << "\"" << endl;
        return EXIT_FAILURE;
    } catch (...) {
        cerr << "UNKNOWN EXCEPTION CAUGHT!" << endl;
        return EXIT_FAILURE;
    }
}

Grid::Grid(const int width, const int height, const string& s)
    : m_width(width), m_height(height), m_total_black(width * height),
    m_cells(), m_regions(), m_sitrep(KEEP_GOING), m_output(), m_prng(1729) {

    // Validate width and height.

    if (width < 1) {
        throw runtime_error("RUNTIME ERROR: Grid::Grid() - width must be at least 1.");
    }

    if (height < 1) {
        throw runtime_error("RUNTIME ERROR: Grid::Grid() - height must be at least 1.");
    }

    // Initialize m_cells. We must set everything to UNKNOWN before calling add_region() below.

    m_cells.resize(width, vector<pair<State, shared_ptr<Region>>>(
        height, make_pair(UNKNOWN, shared_ptr<Region>())));

    // Parse the string.

    vector<int> v;

    const regex r(R"((\d+)|( )|(\n)|[^\d \n])");

    for (sregex_iterator i(s.begin(), s.end(), r), end; i != end; ++i) {
        const smatch& m = *i;

        if (m[1].matched) {
            v.push_back(stoi(m[1]));
        } else if (m[2].matched) {
            v.push_back(0);
        } else if (m[3].matched) {
            // Do nothing.
        } else {
            throw runtime_error("RUNTIME ERROR: Grid::Grid() - "
                "s must contain only digits, spaces, and newlines.");
        }
    }

    // Validate the number of cells. Note that we can't do this before
    // parsing, because numbers 10 and above occupy multiple characters.

    if (v.size() != static_cast<size_t>(width * height)) {
        throw runtime_error("RUNTIME ERROR: Grid::Grid() - "
            "s must contain width * height numbers and spaces.");
    }

    for (int x = 0; x < width; ++x) {
        for (int y = 0; y < height; ++y) {
            const int n = v[x + y * width];

            if (n > 0) {
                // Testing x - 1 and x + 1 is unnecessary because
                // horizontally adjacent numbers would have been concatenated.
                // Testing y + 1 is unnecessary because if there are
                // vertically adjacent numbers, one's above and one's below.

                if (valid(x, y - 1) && cell(x, y - 1) > 0) {
                    throw runtime_error("RUNTIME ERROR: Grid::Grid() - "
                        "s contains vertically adjacent numbers.");
                }

                // Set the cell's state and region.

                cell(x, y) = static_cast<State>(n);

                add_region(x, y);

                // m_total_black is width * height - (sum of all numbered cells).
                // Calculating this allows us to determine whether black regions
                // are partial or complete with a simple size test.
                // Humans are capable of this but it's not convenient for them.

                m_total_black -= n;
            }
        }
    }

    print("I'm okay to go!");
}

Grid::SitRep Grid::solve(const bool verbose, const bool guessing) {
    cache_map_t cache;


    // See if we're done. Before declaring victory, look for contradictions.

    if (known() == m_width * m_height) {
        if (detect_contradictions(verbose, cache)) {
            return CONTRADICTION_FOUND;
        }

        if (verbose) {
            print("I'm done!");
        }

        return SOLUTION_FOUND;
    }


    // Run increasingly expensive steps of analysis.
    // Return as soon as one succeeds.

    // Running detect_contradictions() just before analyze_confinement() increases performance.
    // detect_contradictions() is moderately expensive, so it should be run after extremely cheap
    // steps of analysis. However, detect_contradictions() accelerates analyze_confinement(),
    // which is even more expensive. This doesn't affect correctness:
    // * We always run detect_contradictions() before declaring victory.
    // * The other steps of analysis are robust; if they attempt to fuse two numbered regions
    // or mark an already known cell, they bail out early.
    // * analyze_confinement() can still assume that it has a cache.

    if (analyze_complete_islands(verbose)
        || analyze_single_liberties(verbose)
        || analyze_dual_liberties(verbose)
        || analyze_unreachable_cells(verbose)
        || analyze_potential_pools(verbose)
        || detect_contradictions(verbose, cache)
        || analyze_confinement(verbose, cache)
        || (guessing && analyze_hypotheticals(verbose))) {

        return m_sitrep;
    }


    if (verbose) {
        print("I'm stumped!");
    }

    return CANNOT_PROCEED;
}

// Look for complete islands.
bool Grid::analyze_complete_islands(const bool verbose) {
    set<pair<int, int>> mark_as_black;
    set<pair<int, int>> mark_as_white;

    for (const auto& sp : m_regions) {
        const Region& r = *sp;

        if (r.numbered() && r.size() == r.number()) {
            mark_as_black.insert(r.unk_begin(), r.unk_end());
        }
    }

    return process(verbose, mark_as_black, mark_as_white, "Complete islands found.");
}

// Look for partial regions that can expand into only one cell. They must expand.
bool Grid::analyze_single_liberties(const bool verbose) {
    set<pair<int, int>> mark_as_black;
    set<pair<int, int>> mark_as_white;

    for (const auto& sp : m_regions) {
        const Region& r = *sp;

        const bool partial =
            (r.black() && r.size() < m_total_black)
                || r.white()
                || (r.numbered() && r.size() < r.number());

        if (partial && r.unk_size() == 1) {
            if (r.black()) {
                mark_as_black.insert(*r.unk_begin());
            } else {
                mark_as_white.insert(*r.unk_begin());
            }
        }
    }

    return process(verbose, mark_as_black, mark_as_white,
        "Expanded partial regions with only one liberty.");
}

// Look for N - 1 islands with exactly two diagonal liberties.
bool Grid::analyze_dual_liberties(const bool verbose) {
    set<pair<int, int>> mark_as_black;
    set<pair<int, int>> mark_as_white;

    for (const auto& sp : m_regions) {
        const Region& r = *sp;

        if (r.numbered() && r.size() == r.number() - 1 && r.unk_size() == 2) {
            const int x1 = r.unk_begin()->first;
            const int y1 = r.unk_begin()->second;
            const int x2 = next(r.unk_begin())->first;
            const int y2 = next(r.unk_begin())->second;

            if (abs(x1 - x2) == 1 && abs(y1 - y2) == 1) {
                pair<int, int> p;

                if (r.contains(x1, y2)) {
                    p = make_pair(x2, y1);
                } else {
                    p = make_pair(x1, y2);
                }

                // The far cell might already be black, in which case there's nothing to do.
                // It could even be white/numbered (if it's part of this island), in which case
                // there's still nothing to do.
                // (If it's white/numbered and not part of this island,
                // we'll eventually detect a contradiction.)

                if (cell(p.first, p.second) == UNKNOWN) {
                    mark_as_black.insert(p);
                }
            }
        }
    }

    return process(verbose, mark_as_black, mark_as_white,
        "N - 1 islands with exactly two diagonal liberties found.");
}

// Look for unreachable cells. They must be black.
// This supersedes complete island analysis and forbidden bridge analysis.
// (We run complete island analysis above because it's fast
// and it makes the output easier to understand.)
bool Grid::analyze_unreachable_cells(const bool verbose) {
    set<pair<int, int>> mark_as_black;
    set<pair<int, int>> mark_as_white;

    for (int x = 0; x < m_width; ++x) {
        for (int y = 0; y < m_height; ++y) {
            if (unreachable(x, y)) {
                mark_as_black.insert(make_pair(x, y));
            }
        }
    }

    return process(verbose, mark_as_black, mark_as_white, "Unreachable cells blackened.");
}

// Look for squares of one unknown and three black cells, or two unknown and two black cells.
bool Grid::analyze_potential_pools(const bool verbose) {
    set<pair<int, int>> mark_as_black;
    set<pair<int, int>> mark_as_white;

    for (int x = 0; x < m_width - 1; ++x) {
        for (int y = 0; y < m_height - 1; ++y) {
            struct XYState {
                int x;
                int y;
                State state;
            };

            array<XYState, 4> a = { {
                { x, y, cell(x, y) },
                { x + 1, y, cell(x + 1, y) },
                { x, y + 1, cell(x, y + 1) },
                { x + 1, y + 1, cell(x + 1, y + 1) }
            } };

            static_assert(UNKNOWN < BLACK, "This code assumes that UNKNOWN < BLACK.");

            sort(a.begin(), a.end(), [](const XYState& l, const XYState& r) {
                return l.state < r.state;
            });

            if (a[0].state == UNKNOWN
                && a[1].state == BLACK
                && a[2].state == BLACK
                && a[3].state == BLACK) {

                mark_as_white.insert(make_pair(a[0].x, a[0].y));

            } else if (a[0].state == UNKNOWN
                && a[1].state == UNKNOWN
                && a[2].state == BLACK
                && a[3].state == BLACK) {

                for (int i = 0; i < 2; ++i) {
                    set<pair<int, int>> imagine_black;

                    imagine_black.insert(make_pair(a[0].x, a[0].y));

                    if (unreachable(a[1].x, a[1].y, imagine_black)) {
                        mark_as_white.insert(make_pair(a[0].x, a[0].y));
                    }

                    std::swap(a[0], a[1]);
                }
            }
        }
    }

    return process(verbose, mark_as_black, mark_as_white, "Whitened cells to prevent pools.");
}

// A region would be "confined" if it could not be completed.
// Black regions need to consume m_total_black cells.
// White regions need to escape to a number.
// Numbered regions need to consume N cells.

// Confinement analysis consists of imagining what would happen if a particular unknown cell
// were black or white. If that would cause any region to be confined, the unknown cell
// must be the opposite color.

// Black cells can't confine black regions, obviously.
// Black cells can confine white regions, by isolating them.
// Black cells can confine numbered regions, by confining them to an insufficiently large space.

// White cells can confine black regions, by confining them to an insufficiently large space.
//   (Humans look for isolation here, i.e. permanently separated black regions.
//   That's harder for us to detect, but counting cells is similarly powerful.)
// White cells can't confine white regions.
//   (This is true for freestanding white cells, white cells added to other white regions,
//   and white cells added to numbered regions.)
// White cells can confine numbered regions, when added to other numbered regions.
//   This is the most complicated case to analyze. For example:
//   ####3
//   #6 xXx
//   #.  x
//   ######
//   Imagining cell 'X' to be white additionally prevents region 6 from consuming
//   three 'x' cells. (This is true regardless of what other cells region 3 would
//   eventually occupy.)
bool Grid::analyze_confinement(const bool verbose, cache_map_t& cache) {
    set<pair<int, int>> mark_as_black;
    set<pair<int, int>> mark_as_white;

    for (int x = 0; x < m_width; ++x) {
        for (int y = 0; y < m_height; ++y) {
            if (cell(x, y) == UNKNOWN) {
                set<pair<int, int>> verboten;
                verboten.insert(make_pair(x, y));

                for (const auto& sp : m_regions) {
                    const Region& r = *sp;

                    if (confined(sp, cache, verboten)) {
                        if (r.black()) {
                            mark_as_black.insert(make_pair(x, y));
                        } else {
                            mark_as_white.insert(make_pair(x, y));
                        }
                    }
                }
            }
        }
    }

    for (const auto& sp1 : m_regions) {
        const Region& r = *sp1;

        if (r.numbered() && r.size() < r.number()) {
            for (auto u = r.unk_begin(); u != r.unk_end(); ++u) {
                set<pair<int, int>> verboten;
                verboten.insert(*u);

                insert_valid_unknown_neighbors(verboten, u->first, u->second);

                for (const auto& sp2 : m_regions) {
                    if (sp2 != sp1 && sp2->numbered() && confined(sp2, cache, verboten)) {
                        mark_as_black.insert(*u);
                    }
                }
            }
        }
    }

    return process(verbose, mark_as_black, mark_as_white, "Confinement analysis succeeded.");
}

// Guess cells in a deterministic but pseudorandomized order.
// This attempts to avoid repeatedly guessing cells that won't get us anywhere.
// Prioritize guesses near white cells, which appears to be an especially good heuristic.
// (In particular, it appears to be better than prioritizing guesses near white regions.)
// Manhattan distance appears to work well; see https://en.wikipedia.org/wiki/Taxicab_geometry
vector<pair<int, int>> Grid::guessing_order() {
    // Find all unknown cells and all white cells.
    // The greatest possible Manhattan distance on the grid is m_width - 1 + m_height - 1,
    // so we use m_width + m_height as an extremely large placeholder.

    vector<tuple<int, int, int>> x_y_manhattan;
    vector<pair<int, int>> white_cells;

    for (int x = 0; x < m_width; ++x) {
        for (int y = 0; y < m_height; ++y) {
            switch (cell(x, y)) {
                case UNKNOWN:
                    x_y_manhattan.push_back(make_tuple(x, y, m_width + m_height));
                    break;
                case WHITE:
                    white_cells.push_back(make_pair(x, y));
                    break;
                default:
                    break;
            }
        }
    }


    // Randomly shuffle the unknown cells.

    shuffle(x_y_manhattan.begin(), x_y_manhattan.end(), m_prng);


    // Determine the Manhattan distance from each unknown cell to the nearest white cell.
    // There's probably a cleverer algorithm for this.

    for (auto& [ x1, y1, manhattan ] : x_y_manhattan) {
        for (const auto& [ x2, y2 ] : white_cells) {
            manhattan = min(manhattan, abs(x1 - x2) + abs(y1 - y2));
        }
    }


    // Prioritize the unknown cells by the Manhattan distance to the nearest white cell.
    // stable_sort() avoids disrupting the random_shuffle() above.

    stable_sort(x_y_manhattan.begin(), x_y_manhattan.end(),
        [](const tuple<int, int, int>& l, const tuple<int, int, int>& r) {
            return get<2>(l) < get<2>(r);
        });


    vector<pair<int, int>> ret(x_y_manhattan.size());

    transform(x_y_manhattan.begin(), x_y_manhattan.end(), ret.begin(),
        [](const tuple<int, int, int>& t) { return make_pair(get<0>(t), get<1>(t)); });

    return ret;
}

bool Grid::analyze_hypotheticals(const bool verbose) {
    set<pair<int, int>> mark_as_black;
    set<pair<int, int>> mark_as_white;

    const vector<pair<int, int>> v = guessing_order();

    int failed_guesses = 0;
    set<pair<int, int>> failed_coords;

    for (const auto& [ x, y ] : v) {
        for (int i = 0; i < 2; ++i) {
            const State color = i == 0 ? BLACK : WHITE;
            auto& mark_as_diff = i == 0 ? mark_as_white : mark_as_black;
            auto& mark_as_same = i == 0 ? mark_as_black : mark_as_white;

            Grid other(*this);

            other.mark(color, x, y);

            SitRep sr = KEEP_GOING;

            while (sr == KEEP_GOING) {
                sr = other.solve(false, false);
            }

            if (sr == CONTRADICTION_FOUND) {
                mark_as_diff.insert(make_pair(x, y));
                return process(verbose, mark_as_black, mark_as_white,
                    "Hypothetical contradiction found.", failed_guesses, failed_coords);
            }

            if (sr == SOLUTION_FOUND) {
                mark_as_same.insert(make_pair(x, y));
                return process(verbose, mark_as_black, mark_as_white,
                    "Hypothetical solution found.", failed_guesses, failed_coords);
            }

            // sr == CANNOT_PROCEED
            ++failed_guesses;
            failed_coords.insert(make_pair(x, y));
        }
    }

    return false;
}

int Grid::known() const {
    int ret = 0;

    for (int x = 0; x < m_width; ++x) {
        for (int y = 0; y < m_height; ++y) {
            if (cell(x, y) != UNKNOWN) {
                ++ret;
            }
        }
    }

    return ret;
}

void Grid::write(ostream& os, const steady_clock::time_point start, const steady_clock::time_point finish) const {
    os <<
R"(<!DOCTYPE html>
<html lang="en">
  <head>
    <meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
    <style>
      body {
        font-family: Verdana, sans-serif;
        line-height: 1.4;
      }
      table {
        border: solid 3px #000000;
        border-collapse: collapse;
      }
      td {
        border: solid 1px #000000;
        text-align: center;
        width: 20px;
        height: 20px;
      }
      td.unknown   { background-color: #C0C0C0; }
      td.white.new { background-color: #FFFF00; }
      td.white.old { }
      td.black.new { background-color: #008080; }
      td.black.old { background-color: #808080; }
      td.number    { }
      td.failed    { border: solid 3px #000000; }
    </style>
    <title>Nurikabe</title>
  </head>
  <body>
)";

    steady_clock::time_point old_ctr = start;

    for (const auto& [ s, v, updated, ctr, failed_guesses, failed_coords ] : m_output) {
        os << s << " (" << format_time(old_ctr, ctr) << ")\n";

        if (failed_guesses == 1) {
            os << "<br/>1 guess failed.\n";
        } else if (failed_guesses > 0) {
            os << "<br/>" << failed_guesses << " guesses failed.\n";
        }

        old_ctr = ctr;

        os << "<table>\n";

        for (int y = 0; y < m_height; ++y) {
            os << "<tr>";

            for (int x = 0; x < m_width; ++x) {
                os << "<td class=\"";
                os << (updated.find(make_pair(x, y)) != updated.end() ? "new " : "old ");

                if (failed_coords.find(make_pair(x, y)) != failed_coords.end()) {
                    os << "failed ";
                }

                switch (v[x][y]) {
                    case UNKNOWN: os << "unknown\"> ";           break;
                    case WHITE:   os <<   "white\">.";           break;
                    case BLACK:   os <<   "black\">#";           break;
                    default:      os <<  "number\">" << v[x][y]; break;
                }

                os << "</td>";
            }

            os << "</tr>\n";
        }

        os << "</table><br/>\n";
    }

    os << "Total: " << format_time(start, finish) << "\n";

    os <<
        "  </body>\n"
        "</html>\n";
}

bool Grid::valid(const int x, const int y) const {
    return x >= 0 && x < m_width && y >= 0 && y < m_height;
}

Grid::State& Grid::cell(const int x, const int y) {
    return m_cells[x][y].first;
}

const Grid::State& Grid::cell(const int x, const int y) const {
    return m_cells[x][y].first;
}

shared_ptr<Grid::Region>& Grid::region(const int x, const int y) {
    return m_cells[x][y].second;
}

const shared_ptr<Grid::Region>& Grid::region(const int x, const int y) const {
    return m_cells[x][y].second;
}

void Grid::print(const string& s, const set<pair<int, int>>& updated,
    const int failed_guesses, const set<pair<int, int>>& failed_coords) {
    vector<vector<State>> v(m_width, vector<State>(m_height));

    for (int x = 0; x < m_width; ++x) {
        for (int y = 0; y < m_height; ++y) {
            v[x][y] = cell(x, y);
        }
    }

    m_output.push_back(make_tuple(s, v, updated, steady_clock::now(), failed_guesses, failed_coords));
}

bool Grid::process(const bool verbose, const set<pair<int, int>>& mark_as_black,
    const set<pair<int, int>>& mark_as_white, const string& s,
    const int failed_guesses, const set<pair<int, int>>& failed_coords) {

    if (mark_as_black.empty() && mark_as_white.empty()) {
        return false;
    }

    for (const auto& [ x, y ] : mark_as_black) {
        mark(BLACK, x, y);
    }

    for (const auto& [ x, y ] : mark_as_white) {
        mark(WHITE, x, y);
    }

    if (verbose) {
        set<pair<int, int>> updated(mark_as_black);
        updated.insert(mark_as_white.begin(), mark_as_white.end());

        string t = s;

        if (m_sitrep == CONTRADICTION_FOUND) {
            t += " (Contradiction found! Attempted to fuse two numbered regions"
                " or mark an already known cell.)";
        }

        print(t, updated, failed_guesses, failed_coords);
    }

    return true;
}

template <typename F> void Grid::for_valid_neighbors(const int x, const int y, F f) const {
    if (x > 0) {
        f(x - 1, y);
    }

    if (x + 1 < m_width) {
        f(x + 1, y);
    }

    if (y > 0) {
        f(x, y - 1);
    }

    if (y + 1 < m_height) {
        f(x, y + 1);
    }
}

void Grid::insert_valid_neighbors(set<pair<int, int>>& s, const int x, const int y) const {
    for_valid_neighbors(x, y, [&](const int a, const int b) {
        s.insert(make_pair(a, b));
    });
}

void Grid::insert_valid_unknown_neighbors(set<pair<int, int>>& s, const int x, const int y) const {
    for_valid_neighbors(x, y, [&](const int a, const int b) {
        if (cell(a, b) == UNKNOWN) {
            s.insert(make_pair(a, b));
        }
    });
}

void Grid::add_region(const int x, const int y) {
    // Construct a region, then add it to the cell and the set of all regions.

    set<pair<int, int>> unknowns;
    insert_valid_unknown_neighbors(unknowns, x, y);

    auto r = make_shared<Region>(cell(x, y), x, y, unknowns);

    region(x, y) = r;

    m_regions.insert(r);
}

void Grid::mark(const State s, const int x, const int y) {
    if (s != WHITE && s != BLACK) {
        throw logic_error("LOGIC ERROR: Grid::mark() - s must be either WHITE or BLACK.");
    }

    // If we're asked to mark an already known cell, we've encountered a contradiction.
    // Remember this, so that solve() can report the contradiction.

    if (cell(x, y) != UNKNOWN) {
        m_sitrep = CONTRADICTION_FOUND;
        return;
    }

    // Set the cell's new state. Because it's now known,
    // update each region's set of surrounding unknown cells.

    cell(x, y) = s;

    for (const auto& sp : m_regions) {
        sp->unk_erase(x, y);
    }

    // Marking a cell as white or black could create an independent region,
    // could be added to an existing region, or could connect 2, 3, or 4 separate regions.
    // The easiest thing to do is to create a region for this cell,
    // and then fuse it to any adjacent compatible regions.

    add_region(x, y);

    // Don't attempt to cache these regions.
    // Each fusion could change this cell's region or its neighbors' regions.

    for_valid_neighbors(x, y, [this, x, y](const int a, const int b) {
        fuse_regions(region(x, y), region(a, b));
    });
}

// Note that r1 and r2 are passed by modifiable value. It's convenient to be able to swap them.
void Grid::fuse_regions(shared_ptr<Region> r1, shared_ptr<Region> r2) {

    // If we don't have two different regions, we're done.

    if (!r1 || !r2 || r1 == r2) {
        return;
    }

    // If we're asked to fuse two numbered regions, we've encountered a contradiction.
    // Remember this, so that solve() can report the contradiction.

    if (r1->numbered() && r2->numbered()) {
        m_sitrep = CONTRADICTION_FOUND;
        return;
    }

    // Black regions can't be fused with non-black regions.

    if (r1->black() != r2->black()) {
        return;
    }

    // We'll use r1 as the "primary" region, to which r2's cells are added.
    // It would be efficient to process as few cells as possible.
    // Therefore, we'd like to use the bigger region as the primary region.

    if (r2->size() > r1->size()) {
        std::swap(r1, r2);
    }

    // However, if the secondary region is numbered, then the primary region
    // must be white, so we need to swap them, even if the numbered region is smaller.

    if (r2->numbered()) {
        std::swap(r1, r2);
    }

    // Fuse the secondary region into the primary region.

    r1->insert(r2->begin(), r2->end());
    r1->unk_insert(r2->unk_begin(), r2->unk_end());

    // Update the secondary region's cells to point to the primary region.

    for (const auto& [ x, y ] : *r2) {
        region(x, y) = r1;
    }

    // Erase the secondary region from the set of all regions.
    // When this function returns, the secondary region will be destroyed.

    m_regions.erase(r2);
}

bool Grid::impossibly_big_white_region(const int n) const {
    // A white region of N cells is impossibly big
    // if it could never be connected to any numbered region.

    return none_of(m_regions.begin(), m_regions.end(),
        [n](const shared_ptr<Region>& p) {
            // Add one because a bridge would be needed.
            return p->numbered() && p->size() + n + 1 <= p->number();
        });
}

// The cell at (x_root, y_root) is unreachable if it is unknown
// and it cannot be connected to a numbered region or a white region.
// An unknown cell completely surrounded by black cells is obviously unreachable,
// but because unreachability takes distance into account, it is considerably more powerful.
// We use a breadth-first search to discover the shortest path from the root to a numbered region
// or a white region. (Essentially, we're imagining a chain of white cells starting from the root.)
// We refuse to consider stepping anywhere that would join two numbered regions.
// Additionally, while we want to connect to a numbered region, we can't create a region that's
// too big for its number. (We'll add up the number of white cells that it took us to get from
// the root to the potential connection point, the current size of the numbered region,
// and the sizes of any white regions (up to 2) that would also be connected.)
// Finally, while we'd like to connect to a white region, we can't create
// an impossibly big white region.
// Note that this supersedes complete island analysis and forbidden bridge analysis.
// The "discovered" parameter can be used to tell unreachable() to avoid stepping on a cell.
// This is used when identifying squares of two unknown and two black cells;
// if imagining cell A to be black makes cell B unreachable, then cell A must be white.
bool Grid::unreachable(const int x_root, const int y_root, set<pair<int, int>> discovered) const {

    // We're interested in unknown cells.

    if (cell(x_root, y_root) != UNKNOWN) {
        return false;
    }

    // See https://en.wikipedia.org/wiki/Breadth-first_search

    queue<tuple<int, int, int>> q;

    q.push(make_tuple(x_root, y_root, 1));
    discovered.insert(make_pair(x_root, y_root));

    while (!q.empty()) {
        const auto [ x_curr, y_curr, n_curr ] = q.front();
        q.pop();

        set<shared_ptr<Region>> white_regions;
        set<shared_ptr<Region>> numbered_regions;

        for_valid_neighbors(x_curr, y_curr, [&](const int x, const int y) {
            const shared_ptr<Region>& r = region(x, y);

            if (r && r->white()) {
                white_regions.insert(r);
            } else if (r && r->numbered()) {
                numbered_regions.insert(r);
            }
        });

        int size = 0;

        for (const auto& sp : white_regions) {
            size += sp->size();
        }

        for (const auto& sp : numbered_regions) {
            size += sp->size();
        }

        if (numbered_regions.size() > 1) {
            continue;
        }

        if (numbered_regions.size() == 1) {
            const int num = (*numbered_regions.begin())->number();

            if (n_curr + size <= num) {
                return false;
            } else {
                continue;
            }
        }

        if (!white_regions.empty()) {
            if (impossibly_big_white_region(n_curr + size)) {
                continue;
            } else {
                return false;
            }
        }

        for_valid_neighbors(x_curr, y_curr, [&](const int x, const int y) {
            if (cell(x, y) == UNKNOWN && discovered.insert(make_pair(x, y)).second) {
                q.push(make_tuple(x, y, n_curr + 1));
            }
        });
    }

    return true;
}

namespace {
    // This explicitly specified underlying type significantly increases performance.
    enum Flag : unsigned char {
        NONE,
        OPEN,
        CLOSED,
        VERBOTEN
    };
}

// Is r confined, assuming that we can't consume verboten cells?
bool Grid::confined(const shared_ptr<Region>& r, cache_map_t& cache,
    const set<pair<int, int>>& verboten) const {

    // When we look for contradictions, we run confinement analysis (A) without verboten cells.
    // This gives us an opportunity to accelerate later confinement analysis (B)
    // when we have verboten cells.
    // During A, we'll record the unknown cells that we consumed.
    // During B, if none of the verboten cells are ones that we consumed,
    // then the verboten cells can't confine us.

    if (!verboten.empty()) {
        const auto i = cache.find(r);

        if (i == cache.end()) {
            return false; // We didn't consume any unknown cells.
        }

        const auto& consumed = i->second;

        if (none_of(verboten.begin(), verboten.end(), [&](const pair<int, int>& p) {
            return consumed.find(p) != consumed.end();
        })) {
            return false;
        }
    }


    vector<Flag> flags(m_width * m_height, NONE);

    // The open set contains cells that we're considering adding to the region.
    for (auto i = r->unk_begin(); i != r->unk_end(); ++i) {
        const auto& [ x, y ] = *i;
        flags[x + y * m_width] = OPEN;
    }

    // The closed set contains cells that we've hypothetically added to the region.
    for (const auto& [ x, y ] : *r) {
        flags[x + y * m_width] = CLOSED;
    }

    int closed_size = r->size();

    // Flag the verboten cells last, because this could overwrite open flags.
    for (const auto& [ x, y ] : verboten) {
        flags[x + y * m_width] = VERBOTEN;
    }

    // While we need to consume more cells...
    while ((r->black() && closed_size < m_total_black)
        || r->white()
        || (r->numbered() && closed_size < r->number())) {

        // Do we have a cell to consider?

        const auto iter = find(flags.begin(), flags.end(), OPEN);

        if (iter == flags.end()) {
            break; // We don't.
        }

        *iter = NONE;

        const int index = static_cast<int>(iter - flags.begin());

        const pair<int, int> p(index % m_width, index / m_width);

        // Consider cell p.

        // We need to compare our region r with p's region (if any).
        const auto& area = region(p.first, p.second);

        if (r->black()) {
            if (!area) {
                // Keep going. A black region can consume an unknown cell.
            } else if (area->black()) {
                // Keep going. A black region can consume another black region.
            } else { // area->white() || area->numbered()
                continue; // We can't consume this. Discard it.
            }
        } else if (r->white()) {
            if (!area) {
                // Keep going. A white region can consume an unknown cell.
            } else if (area->black()) {
                continue; // We can't consume this. Discard it.
            } else if (area->white()) {
                // Keep going. A white region can consume another white region.
            } else { // area->numbered()
                return false; // Yay! Our region r escaped to a numbered region.
            }
        } else { // r->numbered()
            if (!area) {
                // A numbered region can't consume an unknown cell
                // that's adjacent to another numbered region.
                bool rejected = false;

                for_valid_neighbors(p.first, p.second, [&](const int a, const int b) {
                    const auto& other = region(a, b);

                    if (other && other->numbered() && other != r) {
                        rejected = true;
                    }
                });

                if (rejected) {
                    continue;
                }

                // Keep going. This unknown cell is okay to consume.
            } else if (area->black()) {
                continue; // We can't consume this. Discard it.
            } else if (area->white()) {
                // Keep going. A numbered region can consume a white region.
            } else { // area->numbered()
                throw logic_error("LOGIC ERROR: Grid::confined() - "
                    "I was confused and thought two numbered regions would be adjacent.");
            }
        }

        if (!area) { // Consume an unknown cell.
            flags[p.first + p.second * m_width] = CLOSED;
            ++closed_size;

            for_valid_neighbors(p.first, p.second, [&](const int a, const int b) {
                Flag& f = flags[a + b * m_width];

                if (f == NONE) {
                    f = OPEN;
                }
            });

            if (verboten.empty()) {
                cache[r].insert(p);
            }
        } else { // Consume a whole region.
            for (const auto& [ x, y ] : *area) {
                flags[x + y * m_width] = CLOSED;
            }

            closed_size += area->size();

            for (auto i = area->unk_begin(); i != area->unk_end(); ++i) {
                const auto& [ x, y ] = *i;
                Flag& f = flags[x + y * m_width];

                if (f == NONE) {
                    f = OPEN;
                }
            }
        }
    }

    // We're confined if we still need to consume more cells.
    return (r->black() && closed_size < m_total_black)
        || r->white()
        || (r->numbered() && closed_size < r->number());
}

bool Grid::detect_contradictions(const bool verbose, cache_map_t& cache) {
    auto uh_oh = [&](const string& s) -> bool {
        if (verbose) {
            print(s);
        }

        m_sitrep = CONTRADICTION_FOUND;

        return true;
    };

    for (int x = 0; x < m_width - 1; ++x) {
        for (int y = 0; y < m_height - 1; ++y) {
            if (cell(x, y) == BLACK
                && cell(x + 1, y) == BLACK
                && cell(x, y + 1) == BLACK
                && cell(x + 1, y + 1) == BLACK) {

                return uh_oh("Contradiction found! Pool detected.");
            }
        }
    }

    int black_cells = 0;
    int white_cells = 0;

    for (const auto& sp : m_regions) {
        const Region& r = *sp;

        // We don't need to look for gigantic black regions because
        // counting black cells is strictly more powerful.

        if ((r.white() && impossibly_big_white_region(r.size()))
            || (r.numbered() && r.size() > r.number())) {

            return uh_oh("Contradiction found! Gigantic region detected.");
        }

        (r.black() ? black_cells : white_cells) += r.size();


        if (confined(sp, cache)) {
            return uh_oh("Contradiction found! Confined region detected.");
        }
    }

    if (black_cells > m_total_black) {
        return uh_oh("Contradiction found! Too many black cells detected.");
    }

    if (white_cells > m_width * m_height - m_total_black) {
        return uh_oh("Contradiction found! Too many white/numbered cells detected.");
    }

    return false;
}

Grid::Grid(const Grid& other)
    : m_width(other.m_width),
    m_height(other.m_height),
    m_total_black(other.m_total_black),
    m_cells(other.m_cells),
    m_regions(),
    m_sitrep(other.m_sitrep),
    m_output(), // Intentionally not copied to increase performance. This copy ctor is private.
    m_prng(other.m_prng) {

    for (const auto& sp : other.m_regions) {
        m_regions.insert(make_shared<Region>(*sp));
    }

    for (const auto& sp : m_regions) {
        for (const auto& [ x, y ] : *sp) {
            region(x, y) = sp;
        }
    }
}