1 2 3 4 5 6 7 8 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 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120
|
#include <iostream>
#include <algorithm>
#define N 16
using namespace std;
class Sudoku
{
public:
int matrix[N][N];
bool solve(int matrix[N][N]);
bool find_zero(int matrix[N][N], int &row, int &col);
bool valid_positions(int matrix[N][N], int row, int col, int num);
void print_matrix(int matrix[N][N]);
};
bool Sudoku::find_zero(int matrix[N][N], int &row, int &col){
for (row = 0; row < N; row++){
for (col = 0; col < N; col++){
if (matrix[row][col] == 0){
return true;
}
}
}
return false;
}
bool Sudoku::valid_positions(int matrix[N][N], int row, int col, int num){
for (int i = 0; i < N; i++){
if (matrix[row][i] == num){
return true;
}
}
for (int i = 0; i < N; i++){
if (matrix[i][col] == num){
return true;
}
}
int box_row = (row / 4) * 4;
int box_col = (col / 4) * 4;
for (int i = 0; i < 4; i++){
for (int j = 0; j < 4; j++){
if (matrix[box_row + i][box_col + j] == num){
return true;
}
}
}
return false;
}
bool Sudoku::find_zero(int matrix[N][N], int &row, int &col);
bool Sudoku::valid_positions(int matrix[N][N], int row, int col, int num);
bool Sudoku::solve(int matrix[N][N]){
Sudoku grid;
int row;
int col;
if (!grid.find_zero(matrix, row, col)){
return true;
}
for (int num = 1; num <= N; num++){
if (!grid.valid_positions(matrix, row, col, num)){
matrix[row][col] = num;
if (grid.solve(matrix)) {
return true; //if value fits its true....
}
matrix[row][col] = 0; //otherwise backtrack amd replace it with a 0 if false
}
}
return false;
}
void Sudoku::print_matrix(int matrix[N][N]){
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
if (matrix[i][j] >= 10){
cout << char(matrix[i][j] + 55) << " ";
}
else{
cout << matrix[i][j];
if (j != N - 1){
cout << " ";
}
}
}
cout << endl;
}
}
int main(){
int matrix[N][N];
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
char x;
cin >> x;
if (int(x) < 58){
matrix[i][j] = x - 48;
}
else{
matrix[i][j] = x - 55;
}
}
}
Sudoku grid;
if (grid.solve(matrix) == true){
cout << endl;
grid.print_matrix(matrix);
}
else{
cout << "No Solution" << endl;
}
return 0;
}
| |