(129). 32.8. SUDOKU SOLVER ‐ HASHING. - anishsingh90/Data_Structure_And_Algorithm_In_Cpp_github.io GitHub Wiki

#include <bits/stdc++.h> using namespace std;

// Helper function bool isValid(int r, int c, vector<vector>& a, vector<vector>& row, vector<vector>& col, vector<vector>& box, char num) { int numInt = num - '0'; if (row[r][numInt] || col[c][numInt] || box[(r / 3) * 3 + (c / 3)][numInt]) { return false; } return true; }

bool solve(int r, int c, vector<vector>& a, vector<vector>& row, vector<vector>& col, vector<vector>& box) { if (r == 9) { return true; // Solved } if (c == 9) { return solve(r + 1, 0, a, row, col, box); } if (a[r][c] != '.') { return solve(r, c + 1, a, row, col, box); }

for (char num = '1'; num <= '9'; num++) {
    if (isValid(r, c, a, row, col, box, num)) {
        int numInt = num - '0';
        a[r][c] = num;
        row[r][numInt] = 1;
        col[c][numInt] = 1;
        box[(r / 3) * 3 + (c / 3)][numInt] = 1;
        
        if (solve(r, c + 1, a, row, col, box)) {
            return true;
        }
        
        // Backtrack
        a[r][c] = '.';
        row[r][numInt] = 0;
        col[c][numInt] = 0;
        box[(r / 3) * 3 + (c / 3)][numInt] = 0;
    }
}

return false;

}

void solveSudoku(vector<vector>& a) { vector<vector> row(9, vector(10, 0)); // 0-9 to represent numbers vector<vector> col(9, vector(10, 0)); vector<vector> box(9, vector(10, 0));

// Initialize row, col, and box
for (int i = 0; i < 9; i++) {
    for (int j = 0; j < 9; j++) {
        if (a[i][j] != '.') {
            int num = a[i][j] - '0';
            row[i][num] = 1;
            col[j][num] = 1;
            box[(i / 3) * 3 + (j / 3)][num] = 1;
        }
    }
}

solve(0, 0, a, row, col, box);

}

int main() { vector<vector> sudoku = { {'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'} };

solveSudoku(sudoku);

for (const auto& row : sudoku) {
    for (char num : row) {
        cout << num << " ";
    }
    cout << endl;
}

return 0;

}

/* OUTPUT: 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9 */