Copmile-time sudoku solver.

SudokuSolver.cpp

#include <cstdint>

namespace {
using namespace std;
template<uint32_t MaxCCol = 9 * 9 * 4, uint32_t MaxCNode = 9 * 9 * 9 * 9, uint32_t MaxCAns = 9 * 9>
class DancingLink {
private:
    struct Node {
        uint32_t U, D, L, R;
        uint32_t Col, Row;
    } XNodes[MaxCNode] {};
    uint32_t XCNodeInCol[MaxCCol + 1] {};
    uint32_t XAns[MaxCAns] {};
    uint32_t XCurNode = 0;
    uint32_t XCRow = 0;
    uint32_t XCCol, CNode;

public:
    constexpr DancingLink(uint32_t CCol) noexcept : XCCol(CCol), CNode(XCCol + 1) {
        for (uint32_t Col = 1; Col <= XCCol; ++Col) {
            auto &col = XNodes[Col];
            col.U = Col;
            col.D = Col;
            col.L = Col - 1;
            col.R = Col + 1;
            col.Col = Col;
        }
        XNodes[0].L = XCCol;
        XNodes[0].R = 1;
        XNodes[XCCol].R = 0;
    }
    
    constexpr const uint32_t *GetAns() const noexcept {
        return XAns;
    }

    constexpr uint32_t GetCRow() const noexcept {
        return XCRow;
    }

    constexpr void NewRow() noexcept {
        XCurNode = 0;
        ++XCRow;
    }

    constexpr void NewNode(uint32_t Col) noexcept {
        auto &cur = XNodes[CNode];
        cur.Col = Col;
        cur.Row = XCRow;
        auto &col = XNodes[Col];
        ++XCNodeInCol[Col];
        cur.U = col.U;
        cur.D = Col;
        XNodes[col.U].D = CNode;
        col.U = CNode;
        if (XCurNode) {
            auto &prv = XNodes[XCurNode];
            cur.L = XCurNode;
            cur.R = prv.R;
            XNodes[prv.R].L = CNode;
            prv.R = CNode;
        }
        else {
            cur.L = CNode;
            cur.R = CNode;
        }
        XCurNode = CNode++;
    }

    constexpr uint32_t Solve() noexcept {
        return XSearch(0);
    }

private:
    constexpr uint32_t XSearch(uint32_t CAns) noexcept {
        if (!XNodes[0].R)
            return CAns;
        auto Col = XNodes[0].R;
        for (auto CurCol = XNodes[Col].R; CurCol; CurCol = XNodes[CurCol].R)
            if (XCNodeInCol[CurCol] < XCNodeInCol[Col])
                Col = CurCol;
        XDelCol(Col);
        auto &col = XNodes[Col];
        for (auto InCol = col.D; InCol != Col; InCol = XNodes[InCol].D) {
            auto &incol = XNodes[InCol];
            XAns[CAns] = incol.Row;
            for (auto InRow = incol.R; InRow != InCol; InRow = XNodes[InRow].R)
                XDelCol(XNodes[InRow].Col);
            auto res = XSearch(CAns + 1);
            if (~res)
                return res;
            for (auto InRow = incol.L; InRow != InCol; InRow = XNodes[InRow].L)
                XAddCol(XNodes[InRow].Col);
        }
        XAddCol(Col);
        return 0xffffffff;
    }

    constexpr void XDelCol(uint32_t Col) noexcept {
        auto &col = XNodes[Col];
        XNodes[col.L].R = col.R;
        XNodes[col.R].L = col.L;
        for (auto InCol = col.D; InCol != Col; InCol = XNodes[InCol].D) {
            auto &incol = XNodes[InCol];
            for (auto InRow = incol.R; InRow != InCol; InRow = XNodes[InRow].R) {
                auto &inrow = XNodes[InRow];
                XNodes[inrow.U].D = inrow.D;
                XNodes[inrow.D].U = inrow.U;
                --XCNodeInCol[inrow.Col];
            }
        }
    }

    constexpr void XAddCol(uint32_t Col) noexcept {
        auto &col = XNodes[Col];
        for (auto InCol = col.U; InCol != Col; InCol = XNodes[InCol].U) {
            auto &incol = XNodes[InCol];
            for (auto InRow = incol.L; InRow != InCol; InRow = XNodes[InRow].L) {
                auto &inrow = XNodes[InRow];
                XNodes[inrow.U].D = InRow;
                XNodes[inrow.D].U = InRow;
                ++XCNodeInCol[inrow.Col];
            }
        }
        XNodes[col.L].R = Col;
        XNodes[col.R].L = Col;
    }

};

struct Sudoku {
    uint32_t Val[9][9];
};

class SudokuSolver {
private:
    constexpr static uint32_t ColFilled = 1;
    constexpr static uint32_t ColRowOccupied = ColFilled + 9 * 9;
    constexpr static uint32_t ColColOccupied = ColRowOccupied + 9 * 9;
    constexpr static uint32_t ColSubOccupied = ColColOccupied + 9 * 9;
    constexpr static uint32_t CCol = ColSubOccupied + 9 * 9 - 1;

    struct NodeInfo {
        uint32_t X, Y, Val;
    } XInfo[9 * 9 * 9 * 9] {};
    DancingLink<CCol, 9 * 9 * 9 * 9, 9 * 9> XDL {CCol};

public:
    constexpr SudokuSolver(const Sudoku &Puzzle_) noexcept {
        auto &Puzzle = Puzzle_.Val;
        for (uint32_t x = 0; x < 9; ++x) {
            for (uint32_t y = 0; y < 9; ++y) {
                auto min = Puzzle[x][y] ? Puzzle[x][y] : 1;
                auto max = Puzzle[x][y] ? Puzzle[x][y] : 9;
                for (auto val = min; val <= max; ++val) {
                    auto off = (val - 1) * 9;
                    XDL.NewRow();
                    XDL.NewNode(ColFilled + x * 9 + y);
                    XDL.NewNode(ColRowOccupied + x + off);
                    XDL.NewNode(ColColOccupied + y + off);
                    XDL.NewNode(ColSubOccupied + x / 3 * 3 + y / 3 + off);
                    auto &info = XInfo[XDL.GetCRow()];
                    info.X = x;
                    info.Y = y;
                    info.Val = val;
                }
            }
        }
    }

    constexpr Sudoku Solve() noexcept {
        auto cfill = XDL.Solve();
        if (cfill != 9 * 9)
            return {};
        Sudoku res {};
        for (uint32_t i = 0; i < cfill; ++i) {
            auto &info = XInfo[XDL.GetAns()[i]];
            res.Val[info.X][info.Y] = info.Val;
        }
        return res;
    }

};

}

#include <chrono>
#include <cstdio>
#include <cstdlib>
#include <vector>

int main() {
    using namespace std;
    using namespace chrono;
    constexpr Sudoku pzl {{
        {5, 3, 0,  0, 7, 0,  0, 0, 0},
        {6, 0, 0,  1, 9, 5,  0, 0, 0},
        {0, 9, 8,  0, 0, 0,  0, 6, 0},

        {8, 0, 0,  0, 6, 0,  0, 0, 3},
        {4, 0, 0,  8, 0, 3,  0, 0, 1},
        {7, 0, 0,  0, 2, 0,  0, 0, 6},

        {0, 6, 0,  0, 0, 0,  2, 8, 0},
        {0, 0, 0,  4, 1, 9,  0, 0, 5},
        {0, 0, 0,  0, 8, 0,  0, 7, 9},
    }};
    auto t1 = high_resolution_clock::now();
    constexpr auto res = SudokuSolver(pzl).Solve();
    auto t2 = high_resolution_clock::now();
    printf("%f ms\n", duration_cast<microseconds>(t2 - t1).count() / 1000.0);
    for (auto &row : res.Val) {
        for (auto val : row)
            printf("%u ", val);
        printf("\n");
    }
    return 0;
}