SudokuSolver

/*
 * Sudoku Solver
 * Michele Marolla
 */

#include <iostream>
#include <fstream>
#include <string>

int sudoku[81][10];
int unsolved = 0;

void printSudoku(){
    for(int i=0; i<81; i++){
        if(sudoku[i][0] == 1)
            std::cout << sudoku[i][1] << " ";
        else
            std::cout << "x ";
        if((i+1)%9 == 0)
            std::cout << std::endl;
    }
    std::cout << std::endl;
}

void solve(int *cell, int n){
    if(cell[0] == 1) return;

    // Check row
    int row = n/9;
    for(int i=row*9; i<=row*9+8; i++){
        if(sudoku[i][0] == 1)
            cell[sudoku[i][1]] = -1;
    }


    // Check column
    int col = n%9;
    for(int i=col; i<=72+col; i=i+9){
        if(sudoku[i][0] == 1)
            cell[sudoku[i][1]] = -1;
    }

    // Check rectangle
    int startRow=0, startCol=0;

    if(row < 3) startRow = 0;
    else if(row >= 3 && row < 6) startRow = 3;
    else if(row >= 6) startRow = 6;

    if(col < 3) startCol = 0;
    else if(col >= 3 && col < 6) startCol = 3;
    else if(col >= 6) startCol = 6;

    int _n;
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            _n = (startRow + i) * 9 + startCol + j;
            if(n == _n) continue;
            if(sudoku[_n][0] == 1)
                cell[sudoku[_n][1]] = -1;
        }
    }

    // Final check
    int choice = -1;
    for(int i=1; i<10; i++){
        if(cell[i] != -1){
            if(choice == -1)
                choice = i;
            else
                return;
        }
    }

    if(choice == -1){
        std::cout << std::endl << "Unable to solve sudoku" << std::endl;
        std::exit(1);
    }

    cell[0] = 1;
    cell[1] = choice;
    unsolved--;

}

int main(){
    std::cout << "Sudoku solver by Michele Marolla" << std::endl;

    // Initialize
    std::cout << "Loading.." << std::endl;
    for(int i=0; i<81; i++){
        sudoku[i][0] = -1;
        for(int j=1; j<10; j++){
            sudoku[i][j] = j;
        }
    }

    // Read sudoku table
    std::cout << "Opening sudoku..." << std::endl;
    std::ifstream myfile;
    myfile.open("sudoku.txt");
    if(!myfile.is_open()){
        std::cout << "Error: cannot open the file 'sudoku.txt'" << std::endl;
        return 1;
    }


    std::string line;
    for(int i=0; i<9; i++){
        getline(myfile, line);
#ifdef _WIN32
        if(i!=0 && line.compare("\r") == 0)
            getline(myfile, line);
#endif
        if(line.length() != 17)
            return 1;

        std::string sub;
        for(int j=0; j<17; j=j+2){
            sub = line.substr(j,1);
            if(sub == "x"){
                unsolved++;
            }else{
                sudoku[9*i + j/2][0] = 1;
                sudoku[9*i + j/2][1] = atoi(sub.c_str());
            }
        }

    }
    myfile.close();

    // Testing
    printSudoku();

    // Solving
    std::cout << std::endl << "Solving..." << std::endl;
    while(unsolved > 0){
        for(int i=0; i<81; i++)
            solve(sudoku[i], i);
    }

    // Output
    std::cout << "Solved!" << std::endl;
    printSudoku();

    // Quit
    char x;
    std::cout << "Press 'q' and then enter to quit: ";
    std::cin >> x;

    return 0;
}