Sudoku Solver Solutions in C++

// Source : https://oj.leetcode.com/problems/sudoku-solver/
// Author : Hao Chen
// Date   : 2014-09-20



#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <iostream>
#include <vector>
using namespace std;


const int SodukuSize = 9;
bool row_mask[SodukuSize][SodukuSize];
bool col_mask[SodukuSize][SodukuSize];
bool area_mask[SodukuSize][SodukuSize];

bool initSudokuMask(vector< vector<char> > &board){
    //reset the memory
    memset(row_mask, false, sizeof(row_mask));
    memset(col_mask, false, sizeof(col_mask));
    memset(area_mask, false, sizeof(area_mask));

    //check each rows and cols
    for(int r=0; r<board.size(); r++){
        for (int c=0; c<board[r].size(); c++){
            if (!isdigit(board[r][c])) {
                continue;
            };
            int idx =  board[r][c] - '0' - 1;

            //check the rows/cols/areas
            int area = (r/3) * 3 + (c/3);
            if (row_mask[r][idx] || col_mask[c][idx] || area_mask[area][idx] ){
                return false;
            }
            row_mask[r][idx] = col_mask[c][idx] = area_mask[area][idx] = true;
        }
    }
    return true;

}


bool recursiveSudoKu(vector< vector<char> > &board, int row, int col){

    if (row >= SodukuSize) {
        return true;
    }

    if (col >= SodukuSize){
        return recursiveSudoKu(board, row+1, 0);
    }
    
    if (board[row][col] != '.'){
        return recursiveSudoKu(board, row, col+1);    
    }
    //pick a number for empty cell
    int area;
    for(int i=0; i<SodukuSize; i++){
        area = (row/3) * 3 + (col/3);
        if (row_mask[row][i] || col_mask[col][i] || area_mask[area][i] ){
            continue;
        }
        //set the number and sovle it recursively
        board[row][col] = i + '1';
        row_mask[row][i] = col_mask[col][i] = area_mask[area][i] = true;
        if (recursiveSudoKu(board, row, col+1) == true){
            return true;
        }
        //backtrace
        board[row][col] = '.';
        row_mask[row][i] = col_mask[col][i] = area_mask[area][i] = false;
         
    }
    return false;
}


void solveSudoku(vector<vector<char> > &board) {
    if (initSudokuMask(board) == false){
        return;
    }
    recursiveSudoKu(board, 0, 0); 
}


int main(int argc, char**argv) {
    return 0;
}

#include <vector>
using std::vector;
#include <unordered_map>
#include <unordered_set>
#include <iostream>

class Solution {
    bool findEmptyCell(const vector<vector<char> > &board, size_t &row, size_t &col)
    {
        for (row = 0; row < board.size(); ++row)
            for (col = 0; col < board[row].size(); ++col)
                if (board[row][col] == '.') return true;
        return false;
    }
    bool isSafe(const vector<vector<char> > &board, size_t row, size_t col, char c)
    {
        for (size_t i=0; i<9; ++i) {
            if (board[row][i] == c) return false;
            if (board[i][col] == c) return false;
            if (board[row/3 * 3 + i / 3][col/3 * 3 + i % 3] == c) return false;
        }
        return true;
    }
public:
    bool solveSudoku(vector<vector<char> > &board) {
        size_t row = 0, col = 0;
        if (!findEmptyCell(board, row, col)) return true;
        for (char c : {'1', '2', '3', '4', '5', '6', '7', '8', '9'})
            if (isSafe(board, row, col, c)) {
                board[row][col] = c;
                if (solveSudoku(board)) return true;
                board[row][col] = '.';
            }
        return false;
    }
};

/// Source : https://leetcode.com/problems/sudoku-solver/description/
/// Author : liuyubobobo
/// Time   : 2018-10-03

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


/// Backtracking
/// Time Complexity: O(n^{need to fill})
/// Space Complexity: O(9*9)
class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {

        vector<vector<bool>> row(9, vector<bool>(10, false));
        vector<vector<bool>> col(9, vector<bool>(10, false));
        vector<vector<bool>> block(9, vector<bool>(10, false));
        for(int i = 0; i < 9; i ++)
            for(int j = 0; j < 9; j ++)
                if(board[i][j] != '.'){
                    row[i][board[i][j] - '0'] = true;
                    col[j][board[i][j] - '0'] = true;
                    block[i / 3 * 3 + j / 3][board[i][j] - '0'] = true;
                }

        for(int i = 0; i < 81; i ++)
            if(board[i / 9][i % 9] == '.'){
                assert(dfs(board, i, row, col, block));
                return;
            }
    }

private:
    bool dfs(vector<vector<char>>& board, int pos,
             vector<vector<bool>>& row, vector<vector<bool>>& col,
             vector<vector<bool>>& block){

        if(pos == 81)
            return true;

        int next = pos + 1;
        for(; next < 81; next ++)
            if(board[next / 9][next % 9] == '.')
                break;

        int x = pos / 9, y = pos % 9;
        for(int i = 1; i <= 9; i ++)
            if(!row[x][i] && !col[y][i] && !block[x / 3 * 3 + y / 3][i]){
                row[x][i] = true;
                col[y][i] = true;
                block[x / 3 * 3 + y / 3][i] = true;
                board[x][y] = '0' + i;

                if(dfs(board, next, row, col, block))
                    return true;

                row[x][i] = false;
                col[y][i] = false;
                block[x / 3 * 3 + y / 3][i] = false;
                board[x][y] = '.';
            }
        return false;
    }
};


int main() {

    return 0;
}