Solution to live archive problem 3304

sudoku.cpp

using namespace std;
#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>

#define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
#define For(i, a, b) for (int i=(a); i<(b); ++i)
#define D(x) cout << #x " is " << x << endl

int board[9][9];
int can_row[9], can_col[9], can_box[9];

bool has_bit(int i, int mask){
    return (mask & (1 << i)) != 0;
}

int set_bit(int i, int mask){
    return (mask | (1 << i));
}

int clear_bit(int i, int mask){
    return (mask & ~(1 << i));
}

// Return box to which cell (i, j) belongs
int box(int i, int j){
    return (3 * (i/3) + j/3);
}

// Check if number num can be placed on cell (i, j)
bool can_put(int i, int j, int num){
    if (board[i][j] == num) return true;
    int b = box(i, j);
    return (board[i][j] == 0 and has_bit(num, can_row[i]) and has_bit(num, can_col[j]) and has_bit(num, can_box[b]));
}

// Put number num on cell (i, j)
void put(int i, int j, int num){
    assert(board[i][j] == 0);
    int b = box(i, j);
    board[i][j] = num;
    can_row[i] = clear_bit(num, can_row[i]);
    can_col[j] = clear_bit(num, can_col[j]);
    can_box[b] = clear_bit(num, can_box[b]);
    assert(!has_bit(num, can_row[i]) and !has_bit(num, can_col[j]) and !has_bit(num, can_box[b]));
}

// Remove number num of cell (i, j)
void remove(int i, int j, int num){
    assert(board[i][j] == num);
    int b = box(i, j);
    board[i][j] = 0;
    can_row[i] = set_bit(num, can_row[i]);
    can_col[j] = set_bit(num, can_col[j]);
    can_box[b] = set_bit(num, can_box[b]);
    assert(can_put(i, j, num));
}

// Check if puzzle can be solved when placing number num on cell (i, j)
bool solve(int i, int j, int num){
    bool filled = (board[i][j] == num);
    assert(can_put(i, j, num));
    
    // Put number (if not already filled)
    if (!filled) put(i, j, num);
    // Next cell
    int new_j = (j+1) % 9;
    int new_i = i + (new_j == 0);
    // If next cell is outside board -> puzzle is complete
    if (new_i == 9) return true;
    // Try putting all numbers on next cell
    for (int k = 1; k <= 9; ++k){
        if (can_put(new_i, new_j, k) and solve(new_i, new_j, k)) return true;
    }
    // No number could be placed on next cell -> remove number placed (if not already filled) and return false
    if (!filled) remove(i, j, num);
    return false;
}

void print_board(){
    for (int i = 0; i < 9; ++i){
        for (int j = 0; j < 9; ++j){
            printf("%d", board[i][j]);
        }
        printf("\n");
    }
}


int main(){
    int cases; cin >> cases;
    while (cases--){
        // Reset can array
        for (int i = 0; i < 9; ++i){
            can_row[i] = can_col[i] = can_box[i] = (1 << 10) - 1;
        }
        // Read board and fill can arrays
        for (int i = 0; i < 9; ++i){
            string s; cin >> s;
            for (int j = 0; j < 9; ++j){
                int num = s[j] - '0';
                board[i][j] = 0;
                if (num != 0) put(i, j, num);
            }
        }
        // printf("BEFORE\n"); print_board(); printf("\n");
        
        // Try solving firs cell. If cell is filled solve with number, if not try all possible numbers
        if (board[0][0] != 0){
            solve(0, 0, board[0][0]);
        }else{
            for (int num = 1; num <= 9; ++num){
                if (can_put(0, 0, num) and solve(0, 0, num)) break;
            }
        }
        
        print_board();
    }
    return 0;
}

sudoku_pretty.cpp

using namespace std;
#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>

#define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
#define For(i, a, b) for (int i=(a); i<(b); ++i)
#define D(x) cout << #x " is " << x << endl

int board[9][9];
int can_row[9], can_col[9], can_box[9];

bool has_bit(int i, int mask){
    return (mask & (1 << i)) != 0;
}

int set_bit(int i, int mask){
    return mask | (1 << i);
}

int clear_bit(int i, int mask){
    return mask & ~(1 << i);
}

// Return box to which cell (i, j) belongs
int box(int i, int j){
    return (3 * (i/3) + j/3);
}

// Check if number num can be placed on cell (i, j)
bool can_put(int i, int j, int num){
    assert(board[i][j] == 0);
    int b = box(i, j);
    return (has_bit(num, can_row[i]) and has_bit(num, can_col[j]) and has_bit(num, can_box[b]));
}

// Put number num on cell (i, j)
void put(int i, int j, int num){
    assert(board[i][j] == 0);
    int b = box(i, j);
    board[i][j] = num;
    can_row[i] = clear_bit(num, can_row[i]);
    can_col[j] = clear_bit(num, can_col[j]);
    can_box[b] = clear_bit(num, can_box[b]);
    assert(!has_bit(num, can_row[i]) and !has_bit(num, can_col[j]) and !has_bit(num, can_box[b]));
}

// Remove number num of cell (i, j)
void remove(int i, int j, int num){
    assert(board[i][j] == num);
    int b = box(i, j);
    board[i][j] = 0;
    can_row[i] = set_bit(num, can_row[i]);
    can_col[j] = set_bit(num, can_col[j]);
    can_box[b] = set_bit(num, can_box[b]);
    assert(can_put(i, j, num));
}

// Check if puzzle can be solved when filling cell (i, j) with all possible values
bool solve(int i, int j){
    // Puzzle complete
    if (i == 9) return true;
    
    int next_j = (j+1) % 9;
    int next_i = i + (next_j == 0);
    
    // Cell already filled
    if (board[i][j] != 0) return solve(next_i, next_j);
    
    // Try putting all numbers on next cell
    for (int k = 1; k <= 9; ++k){
        if (can_put(i, j, k)){
            put(i, j, k);
            if (solve(next_i, next_j)) return true;
            remove(i, j, k);
        }
    }
    return false;
}

void print_board(){
    for (int i = 0; i < 9; ++i){
        for (int j = 0; j < 9; ++j){
            printf("%d", board[i][j]);
        }
        printf("\n");
    }
}


int main(){
    int cases; cin >> cases;
    while (cases--){
        // Reset can array
        for (int i = 0; i < 9; ++i){
            can_row[i] = can_col[i] = can_box[i] = (1 << 10) - 1;
        }
        // Read board and fill can arrays
        for (int i = 0; i < 9; ++i){
            string s; cin >> s;
            for (int j = 0; j < 9; ++j){
                int num = s[j] - '0';
                board[i][j] = 0;
                if (num != 0) put(i, j, num);
            }
        }
        
        assert(solve(0, 0));
        print_board();
    }
    return 0;
}