C++11 Maximum(-O3)

Average time: 715 μs (131072 tests)

Bugs: May return some sudoku with suffix zeros

#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;
    
    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() 
         << " us\n";
    generator.print();
    
    return 0;
}