sudokuSolver.cpp 5.22 KB
Newer Older
1
2
//Recursive backtracking algorithm that can solve any sudoku puzzle.
//Created by Nathan Rossol 8/16/20
nrossol's avatar
nrossol committed
3
4
5
6
#include <iostream>
#include <map>
#include <set>

7
8
//Main Algorithm:
bool solveSudoku(int (&grid)[9][9]);
nrossol's avatar
nrossol committed
9

10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
//Helper Functions:
bool checkBox(const int (&grid)[9][9], const int &row, const int &col);
bool checkSolution(const int (&grid)[9][9], const int &row, const int &col);
bool findZero(const int (&grid)[9][9], std::pair<int,int> &zeroIndex);
void printBoard(const int (&grid)[9][9]);
void solve(int (&grid)[9][9]);

/////////Main/////////
int main(int argc, char *argv[]) {

    //basic error checking:
    if(argc != 2 ){
        std::cout << "[ERROR] Correct Use: ./sudokuSolver.exe [grid number 1-3]" << std::endl;
        return -1;
    } 
    std::string arg = argv[1];
    if (arg != "1" && arg != "2" && arg != "3") {
        std::cout << "[ERROR] Correct Use: ./sudokuSolver.exe [grid number 1-3]" << std::endl;
        return -1;
    }


    //grid selection:
    if(arg == "1"){
        int grid[9][9] = { { 3, 2, 1, 0, 5, 0, 9, 4, 7 },
        {7, 8, 0, 0, 1, 0, 0, 6, 5},
        {0, 0, 6, 7, 0, 4, 1, 0, 0},
        {5, 4, 9, 0, 0, 0, 7, 8 ,6},
        {0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 9, 0, 6, 0, 0, 0},
        {1, 0, 5, 0, 6, 0, 4, 0, 2},
        {0 ,3 ,0, 2, 0, 7, 0, 5, 0},
        {2, 0, 7, 0, 4, 0, 8, 0, 3} };  
        solve(grid);      
    } else if (arg == "2"){
        int grid[9][9] = { {1, 0, 0, 3, 0, 0, 0, 8, 0},
        {3, 0, 0, 9, 0, 0, 6, 0, 0},
        {0, 0, 0, 7, 4, 8, 1, 0, 5},
        {4, 2, 6, 0, 0, 0, 7, 0, 0},
        {0, 7, 8, 4, 0, 9, 3, 6, 0},
        {0, 0, 3, 0, 0, 0, 4, 5, 8},
        {2, 0, 1, 8, 9, 4, 0, 0, 0},
        {0, 0, 4, 0, 0, 6, 0, 0, 9},
        {0, 3, 0, 0, 0, 5, 0, 0, 6} };
        solve(grid);
    } else if (arg == "3"){
        int grid[9][9] = { {0, 0, 0, 4, 9, 0, 1, 5, 0},
        {2, 9, 0, 7, 1, 0, 6, 8, 0},
        {6, 1, 0, 0, 8, 0, 0, 0, 0},
        {0, 0, 0, 1, 0, 7, 0, 2, 6},
        {9, 3, 2, 0, 0, 0, 4, 7, 1},
        {1, 7, 0, 9, 0, 4, 0, 0, 0},
        {0, 0, 0, 0, 7, 0, 0, 6, 4},
        {0, 6, 9, 0, 4, 3, 0, 1, 5},
        {0, 2, 3, 0, 5, 1, 0, 0, 0} };   
        solve(grid);     
    }

    return 0;
}

/////////Main Solving Algorithm/////////
nrossol's avatar
nrossol committed
72
73
74
//Sudoku rules: The grid has 81 squares: 9 boxes of 9 squares. Each box must contain
//all numbers 1-9 in its squares, and each number can appear only once in any row, 
//column, or box.
75
76
bool solveSudoku(int (&grid)[9][9]){

nrossol's avatar
nrossol committed
77
78
    std::pair<int,int> zeroIndex; //row,col of the zero to be filled.
    bool foundZero = findZero(grid, zeroIndex);
79
80
    bool solved;

nrossol's avatar
nrossol committed
81
    if(foundZero){
82

nrossol's avatar
nrossol committed
83
        for(int i = 1; i < 10; ++i){
84
            grid[zeroIndex.first][zeroIndex.second] = i;
nrossol's avatar
nrossol committed
85
            if(checkSolution(grid, zeroIndex.first, zeroIndex.second)){
86
87
88
                // std::cout<< zeroIndex.first << ", " << zeroIndex.second << " == " << grid[zeroIndex.first][zeroIndex.second] << std::endl;
                solved = solveSudoku(grid);
                if(solved) {return true;}
nrossol's avatar
nrossol committed
89
90
            }
        }
91
92

        grid[zeroIndex.first][zeroIndex.second] = 0; 
nrossol's avatar
nrossol committed
93
        return false;
94
95


nrossol's avatar
nrossol committed
96
97
98
    } else {
        return true; //solved
    }
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

}

/////////Helper functions/////////
//checks the boxes to assure no duplicate numbers
bool checkBox(const int (&grid)[9][9], const int &row, const int &col){
    std::set<int> numbers;
    for(int i = 0; i < 3; ++i){
        for(int j = 0; j < 3; ++j){
            //std::cout << "ROW, COL: " << row+i << " ," << col + j << std::endl;
            if(numbers.insert(grid[row+i][col+j]).second == false && grid[row+i][col+j] != 0) { //duplicate detected!
                //std::cout << "DUPLICATE!" << std::endl;
                return false;
            }
        }
    }
    return true;
nrossol's avatar
nrossol committed
116
117
118
}

//checks the solution for a given index and returns true if valid.
119
120
bool checkSolution(const int (&grid)[9][9], const int &row, const int &col){ 
    //check cols and rows:
nrossol's avatar
nrossol committed
121
122
123
124
125
126
127
    for(int i = 0; i < 9; ++i){
        if(grid[i][col] == grid[row][col] && i != row) {
            return false;
        } else if (grid[row][i] == grid[row][col] && i != col){
            return false;
        }
    }
128
129
130
131
132
133
134
135

    //check boxes:
    for(int i = 0; i < 9; i += 3){
        for(int j = 0; j < 9; j += 3){
            if(!checkBox(grid,i,j)) {return false;}
        }   
    }

nrossol's avatar
nrossol committed
136
    return true;
137

nrossol's avatar
nrossol committed
138
139
140
}

//Finds the index of the next zero to be solved.
141
bool findZero(const int (&grid)[9][9], std::pair<int,int> &zeroIndex){
nrossol's avatar
nrossol committed
142
143
144
145
146
147
148
149
150
151
152
153
154
155
    for(int i = 0; i < 9; ++i){
        for(int j = 0; j < 9; ++j){
            if(grid[i][j] == 0) {
                zeroIndex.first = i;
                zeroIndex.second = j;
                return true;
            }
        }
    }
    return false;

}

//Prints the board.
156
void printBoard(const int (&grid)[9][9]){
nrossol's avatar
nrossol committed
157
158
    for(int i = 0; i < 9; ++i){
        for(int j = 0; j < 9; ++j){
159
            std::cout << grid[i][j] << " ";
nrossol's avatar
nrossol committed
160
161
162
163
164
        }
        std::cout << std::endl;
    }
}

165
166
//Executes the algorithm:
void solve(int (&grid)[9][9]) {
nrossol's avatar
nrossol committed
167
168
169
    if(solveSudoku(grid)==true) {std::cout << "Solved!" << std::endl;}
    else {std::cout << "Unsolvable :(" << std::endl;}

170
171
    printBoard(grid);    
}