Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * 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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement