main.cpp

#include <algorithm>
#include <random>
#include <cmath>
#include <iostream>
#include <vector>
#include <set>
#include <chrono>


#include <thread> //only for pauses between different tests
using namespace std;

inline bool isDecimalCharacter(char c) {
    return (c >= '0') && (c <= '9');
}

void fillBoardArray(const vector<vector<char>>& out, vector<vector<int>>& board, vector<vector<bool>>& fixed_squares) {
    for (int i = 0; i < 9; i++) {
        board[i].resize(9);
        fixed_squares[i].resize(9);
        for (int j = 0; j < 9; j++) {
            if (isDecimalCharacter(out[i][j])) {
                board[i][j] = out[i][j] - '0';
                fixed_squares[i][j] = true;
            } else {
                board[i][j] = 0;
                fixed_squares[i][j] = false;
            }
        }
    }
}

void initializeBoard(vector<vector<int>>& board, const vector<vector<bool>>& fixed_squares, mt19937& generator) {
    // For each 3x3 block, fill with missing numbers
    for (int blockRow = 0; blockRow < 3; blockRow++) {
        for (int blockCol = 0; blockCol < 3; blockCol++) {
            // Track used numbers in this block
            set<int> usedNumbers;
            vector<pair<int, int>> emptyCells;
            
            // First pass: collect used numbers and empty cells
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    int r = blockRow * 3 + i;
                    int c = blockCol * 3 + j;
                    if (board[r][c] != 0) {
                        usedNumbers.insert(board[r][c]);
                    } else if (!fixed_squares[r][c]) {
                        emptyCells.push_back({r, c});
                    }
                }
            }
            
            // Determine missing numbers
            vector<int> missingNumbers;
            for (int num = 1; num <= 9; num++) {
                if (usedNumbers.find(num) == usedNumbers.end()) {
                    missingNumbers.push_back(num);
                }
            }
            
            // Shuffle and assign to empty cells
            shuffle(missingNumbers.begin(), missingNumbers.end(), generator);
            for (size_t idx = 0; idx < emptyCells.size(); idx++) {
                int r = emptyCells[idx].first;
                int c = emptyCells[idx].second;
                board[r][c] = missingNumbers[idx];
            }
        }
    }
}

int cost(const vector<vector<int>>& board) {
    int totalCost = 0;
    
    // Check rows
    for (int i = 0; i < 9; i++) {
        vector<int> count(10, 0);
        for (int j = 0; j < 9; j++) {
            count[board[i][j]]++;
        }
        for (int num = 1; num <= 9; num++) {
            if (count[num] > 1) totalCost += count[num] - 1;
        }
    }
    
    // Check columns
    for (int j = 0; j < 9; j++) {
        vector<int> count(10, 0);
        for (int i = 0; i < 9; i++) {
            count[board[i][j]]++;
        }
        for (int num = 1; num <= 9; num++) {
            if (count[num] > 1) totalCost += count[num] - 1;
        }
    }
    
    // Check 3x3 blocks
    for (int blockRow = 0; blockRow < 3; blockRow++) {
        for (int blockCol = 0; blockCol < 3; blockCol++) {
            vector<int> count(10, 0);
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    int r = blockRow * 3 + i;
                    int c = blockCol * 3 + j;
                    count[board[r][c]]++;
                }
            }
            for (int num = 1; num <= 9; num++) {
                if (count[num] > 1) totalCost += count[num] - 1;
            }
        }
    }
    
    return totalCost;
}

void generateNeighbor(vector<vector<int>>& board, const vector<vector<bool>>& fixed_squares, mt19937& generator) {
    // Select a random 3x3 block
    int blockRow = uniform_int_distribution<int>(0, 2)(generator);
    int blockCol = uniform_int_distribution<int>(0, 2)(generator);
    
    // Find mutable cells in this block
    vector<pair<int, int>> mutableCells;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            int r = blockRow * 3 + i;
            int c = blockCol * 3 + j;
            if (!fixed_squares[r][c]) {
                mutableCells.push_back({r, c});
            }
        }
    }
    
    if (mutableCells.size() < 2) return;
    
    // Select two distinct cells to swap
    uniform_int_distribution<int> dist(0, mutableCells.size() - 1);
    int idx1 = dist(generator);
    int idx2 = dist(generator);
    while (idx1 == idx2) {
        idx2 = dist(generator);
    }
    
    // Swap the values
    swap(board[mutableCells[idx1].first][mutableCells[idx1].second],
         board[mutableCells[idx2].first][mutableCells[idx2].second]);
}

void generateDiversificationMove(vector<vector<int>>& board, const vector<vector<bool>>& fixed_squares, mt19937& generator) {
    // With a small probability, make a more significant change
    // Reinitialize a random block to escape local minima
    int blockRow = uniform_int_distribution<int>(0, 2)(generator);
    int blockCol = uniform_int_distribution<int>(0, 2)(generator);
    
    // Collect fixed numbers in this block
    set<int> fixedNumbers;
    vector<pair<int, int>> mutableCells;
    
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            int r = blockRow * 3 + i;
            int c = blockCol * 3 + j;
            if (fixed_squares[r][c]) {
                fixedNumbers.insert(board[r][c]);
            } else {
                mutableCells.push_back({r, c});
            }
        }
    }
    
    // Determine available numbers
    vector<int> availableNumbers;
    for (int num = 1; num <= 9; num++) {
        if (fixedNumbers.find(num) == fixedNumbers.end()) {
            availableNumbers.push_back(num);
        }
    }
    
    // Shuffle and assign to mutable cells
    shuffle(availableNumbers.begin(), availableNumbers.end(), generator);
    for (size_t i = 0; i < mutableCells.size(); i++) {
        int r = mutableCells[i].first;
        int c = mutableCells[i].second;
        board[r][c] = availableNumbers[i];
    }
}

void PrintCurrentBoardAndCost(const vector<vector<int>>& board, int cost, long iterations) {
    cout << "Iteration: " << iterations << ", Cost: " << cost << endl;
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cout << board[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

void solveSudoku(vector<vector<char>>& out) {
    vector<vector<int>> board(9);
    vector<vector<bool>> fixed_squares(9);
    fillBoardArray(out, board, fixed_squares);

    std::random_device rand_dev;
    std::mt19937 generator(rand_dev());
    std::uniform_real_distribution<> realDistribution(0, 1);
    
    // Initialize board with valid blocks
    initializeBoard(board, fixed_squares, generator);
    
    int currentCost = cost(board);
    double temperature = 20.0;
    double coolingRate = 0.99995;
    double minTemperature = 0.0001;
    long iterations = 0;
    int sameCostCount = 0;
    int lastCost = currentCost;
    auto startTime = chrono::steady_clock::now();
    
    while (temperature > minTemperature && currentCost > 0) {
        vector<vector<int>> newBoard = board;
        
        // With a small probability, make a diversification move
        if (realDistribution(generator) < 0.05) {
            generateDiversificationMove(newBoard, fixed_squares, generator);
        } else {
            generateNeighbor(newBoard, fixed_squares, generator);
        }
        
        int newCost = cost(newBoard);
        int costDiff = newCost - currentCost;
        
        if (costDiff <= 0) {
            board = newBoard;
            currentCost = newCost;
        } else {
            double probability = exp(-costDiff / temperature);
            if (realDistribution(generator) < probability) {
                board = newBoard;
                currentCost = newCost;
            }
        }
        
        temperature *= coolingRate;
        iterations++;
        
        // Check for stagnation
        if (currentCost == lastCost) {
            sameCostCount++;
            if (sameCostCount > 5000) {
                // Randomize to escape local minimum
                initializeBoard(board, fixed_squares, generator);
                currentCost = cost(board);
                temperature = 20.0;
                sameCostCount = 0;
            }
        } else {
            sameCostCount = 0;
            lastCost = currentCost;
        }
        
        // Print progress occasionally
        if (iterations % 10000 == 0) {
            PrintCurrentBoardAndCost(board, currentCost, iterations);
            
            // Check if we're taking too long
            auto currentTime = chrono::steady_clock::now();
            auto elapsed = chrono::duration_cast<chrono::seconds>(currentTime - startTime).count();
            if (elapsed > 30) { // 30 seconds timeout
                cout << "Timeout reached. Restarting with new initialization." << endl;
                initializeBoard(board, fixed_squares, generator);
                currentCost = cost(board);
                temperature = 20.0;
                startTime = chrono::steady_clock::now();
            }
        }
        
        // If cost is zero, we found a solution
        if (currentCost == 0) {
            break;
        }
    }
    
    // Output the solution
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (!fixed_squares[i][j]) {
                out[i][j] = '0' + board[i][j];
            }
        }
    }
}

int main() {
    vector<vector<char>> test = {
        {'5','3','.','.','7','.','.','.','.'},
        {'6','.','.','1','9','5','.','.','.'},
        {'.','9','8','.','.','.','.','6','.'},
        {'8','.','.','.','6','.','.','.','3'},
        {'4','.','.','8','.','3','.','.','1'},
        {'7','.','.','.','2','.','.','.','6'},
        {'.','6','.','.','.','.','2','8','.'},
        {'.','.','.','4','1','9','.','.','5'},
        {'.','.','.','.','8','.','.','7','9'}
    };

    vector<vector<char>> test2 = {
        {'.','2','6','5','.','.','.','9','.'},
        {'5','.','.','.','7','9','.','.','4'},
        {'3','.','.','.','1','.','.','.','.'},
        {'6','.','.','.','.','.','8','.','7'},
        {'.','7','5','.','2','.','.','1','.'},
        {'.','1','.','.','.','.','4','.','.'},
        {'.','.','.','3','.','8','9','.','2'},
        {'7','.','.','.','6','.','.','4','.'},
        {'.','3','.','2','.','.','1','.','.'}
    };

    vector<vector<vector<char>>> tests = {test, test2};


    int testCounter = 0;
    for(vector<vector<char>> test : tests){
        solveSudoku(test);
        
        cout << "Final Solution:" << endl;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                cout << test[i][j] << " ";
            }
            cout << endl;
        }
        
        // Verify the solution
        vector<vector<int>> board(9);
        vector<vector<bool>> fixed_squares(9);
        fillBoardArray(test2, board, fixed_squares);
        int finalCost = cost(board);
        cout << "Final cost: " << finalCost << endl;

        testCounter++;
        if(testCounter >= tests.size()) return 0;
        
        std::cout << "Waiting 5 seconds before the next test" << std::endl;
        std::chrono::seconds sleepDuration(5);
        std::this_thread::sleep_for( sleepDuration );
        std::cout << "Waited 5s\n";
    }
    
    
    
    return 0;
}