generate by DeepSeek

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>
#include <time.h>

using namespace std;

class SudokuGenerator {
private:
    int board[9][9] = {{0}};      // 数独棋盘
    int rows[9] = {0};            // 行掩码
    int cols[9] = {0};            // 列掩码
    int boxes[3][3] = {{0}};      // 宫掩码
    mt19937 rng;                  // 随机数生成器
    
    // 获取(i,j)位置可用的数字
    vector<int> getPossibleNumbers(int i, int j) {
        int used = rows[i] | cols[j] | boxes[i/3][j/3];
        vector<int> possible;
        for (int num = 1; num <= 9; ++num) {
            if (!(used & (1 << (num-1)))) {
                possible.push_back(num);
            }
        }
        return possible;
    }
    
    // 找到下一个需要填充的单元格（MRV启发式）
    bool findNextCell(int &row, int &col) {
        int minCount = 10;
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == 0) {
                    auto possible = getPossibleNumbers(i, j);
                    if (possible.size() < minCount) {
                        minCount = possible.size();
                        row = i;
                        col = j;
                        if (minCount == 0) return false; // 发现冲突
                    }
                }
            }
        }
        return minCount != 10; // 是否找到空单元格
    }
    
    // 递归填充函数
    bool fillSudoku() {
        int i, j;
        if (!findNextCell(i, j)) return true; // 所有单元格已填满
        
        auto possible = getPossibleNumbers(i, j);
        if (possible.empty()) return false;
        
        shuffle(possible.begin(), possible.end(), rng); // 随机化数字顺序
        
        for (int num : possible) {
            int mask = 1 << (num-1);
            // 设置状态
            board[i][j] = num;
            rows[i] |= mask;
            cols[j] |= mask;
            boxes[i/3][j/3] |= mask;
            
            if (fillSudoku()) return true;
            
            // 回溯
            board[i][j] = 0;
            rows[i] &= ~mask;
            cols[j] &= ~mask;
            boxes[i/3][j/3] &= ~mask;
        }
        return false;
    }

public:
    SudokuGenerator() {
        // 初始化随机数生成器
        rng.seed(chrono::system_clock::now().time_since_epoch().count());
    }
    
    void generate() {
        // 重置状态
        memset(board, 0, sizeof(board));
        memset(rows, 0, sizeof(rows));
        memset(cols, 0, sizeof(cols));
        memset(boxes, 0, sizeof(boxes));
        fillSudoku();
    }
    
    void print() const {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                cout << board[i][j] << " ";
                if (j % 3 == 2 && j != 8) cout << "| ";
            }
            cout << endl;
            if (i % 3 == 2 && i != 8) {
                cout << "------+-------+------" << endl;
            }
        }
    }
};

int main() {
    SudokuGenerator generator;
    generator.generate();
    generator.print();
    return 0;
}

榨干：

#include <iostream>
#include <bitset>
#include <array>
#include <algorithm>
#include <random>
#include <immintrin.h>  // AVX2指令集头文件

using namespace std;

constexpr uint16_t ALL_NUMBERS = 0x1FF; // 低9位表示1-9

class SudokuGenerator {
private:
    struct Cell {
        uint8_t row, col;
        uint16_t candidates;
        bool operator<(const Cell& other) const {
            return __builtin_popcount(candidates) < __builtin_popcount(other.candidates);
        }
    };

    array<array<uint8_t, 9>, 9> board;
    array<uint16_t, 9> rows;
    array<uint16_t, 9> cols;
    array<array<uint16_t, 3>, 3> boxes;
    vector<Cell> cells;
    mt19937_64 rng;

    // 使用AVX2指令加速位运算
    static inline uint16_t fast_candidates(uint16_t row, uint16_t col, uint16_t box) {
        __m256i mask = _mm256_set1_epi16(row | col | box);
        __m256i nums = _mm256_setr_epi16(1,2,4,8,16,32,64,128,256,0,0,0,0,0,0,0);
        __m256i result = _mm256_andnot_si256(mask, nums);
        return _mm256_movemask_epi8(_mm256_cmpeq_epi16(result, _mm256_setzero_si256()));
    }

    // 预生成第一宫优化
    void prefill_first_box() {
        array<uint8_t, 9> nums{1,2,3,4,5,6,7,8,9};
        shuffle(nums.begin(), nums.end(), rng);
        
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                const uint8_t num = nums[i*3+j];
                board[i][j] = num;
                rows[i] |= 1 << (num-1);
                cols[j] |= 1 << (num-1);
                boxes[0][0] |= 1 << (num-1);
            }
        }
    }

    // 使用缓存友好的数据结构存储候选数
    void update_candidates() {
        cells.clear();
        for (uint8_t i = 0; i < 9; ++i) {
            for (uint8_t j = 0; j < 9; ++j) {
                if (board[i][j] == 0) {
                    const uint16_t used = rows[i] | cols[j] | boxes[i/3][j/3];
                    const uint16_t candidates = ALL_NUMBERS & ~used;
                    if (candidates == 0) return;
                    cells.push_back({i, j, candidates});
                }
            }
        }
        sort(cells.begin(), cells.end());
    }

    bool solve() {
        update_candidates();
        if (cells.empty()) return true;
        
        const Cell current = cells.front();
        const auto [i, j, candidates] = current;

        // 使用位扫描直接获取候选数
        uint32_t mask = candidates;
        const int count = __builtin_popcount(mask);
        array<uint8_t, 9> nums;
        int idx = 0;
        
        while (mask) {
            const uint8_t num = __builtin_ctz(mask) + 1;
            nums[idx++] = num;
            mask ^= 1 << (num-1);
        }
        
        // 费雪耶茨洗牌优化
        for (int k = count-1; k > 0; --k) {
            uniform_int_distribution<int> dist(0, k);
            swap(nums[k], nums[dist(rng)]);
        }

        for (int k = 0; k < count; ++k) {
            const uint8_t num = nums[k];
            const uint16_t bit = 1 << (num-1);

            // 更新状态
            board[i][j] = num;
            rows[i] |= bit;
            cols[j] |= bit;
            boxes[i/3][j/3] |= bit;

            if (solve()) return true;

            // 回溯
            board[i][j] = 0;
            rows[i] &= ~bit;
            cols[j] &= ~bit;
            boxes[i/3][j/3] &= ~bit;
        }
        return false;
    }

public:
    SudokuGenerator() : rng(random_device{}()) {
        // 预热随机数生成器
        for (int i = 0; i < 100; ++i) rng();
    }

    void generate() {
        // 内存清零优化
        memset(&board, 0, sizeof(board));
        memset(&rows, 0, sizeof(rows));
        memset(&cols, 0, sizeof(cols));
        memset(&boxes, 0, sizeof(boxes));
        
        prefill_first_box();
        solve();
    }

    void print() const {
        for (int i = 0; i < 9; ++i) {
            if (i % 3 == 0 && i != 0) 
                cout << "------+-------+------\n";
            for (int j = 0; j < 9; ++j) {
                if (j % 3 == 0 && j != 0) 
                    cout << "| ";
                cout << static_cast<int>(board[i][j]) << " ";
            }
            cout << "\n";
        }
    }
};

int main() {
    SudokuGenerator generator;
    
    const auto start = chrono::high_resolution_clock::now();
    generator.generate();
    const auto end = chrono::high_resolution_clock::now();
    
    cout << "Generation time: " 
         << chrono::duration_cast<chrono::microseconds>(end-start).count() 
         << " μs\n";
    generator.print();
    
    return 0;
}