Created
February 3, 2022 21:20
-
-
Save Muaath5/70e9954f73dec8b82122a33a981e8684 to your computer and use it in GitHub Desktop.
C++ console app that solves sudoku 9x9 via Backtracking (Recursion)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Copyright 2022 - Muaath Alqarni | |
#define _CRT_NO_DEPRECATE | |
#include <iostream> | |
#include <vector> | |
#define endl '\n'; | |
#define fast std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); | |
using std::cin; | |
using std::cout; | |
using std::vector; | |
const char EMPTY = '.'; | |
const int BOX_SIZE = 3; | |
const int GRID_SIZE = 9; | |
char grid[GRID_SIZE][GRID_SIZE]; | |
vector<std::pair<int, int>> emptyPlaces; | |
inline char getVal(int num) | |
{ | |
return num + '0'; | |
} | |
bool existsInRow(int num, int row) | |
{ | |
for (int i = 0; i < GRID_SIZE; i++) | |
if (grid[row][i] == getVal(num)) | |
return true; | |
return false; | |
} | |
bool existsInCol(int num, int col) | |
{ | |
for (int i = 0; i < GRID_SIZE; i++) | |
if (grid[i][col] == getVal(num)) | |
return true; | |
return false; | |
} | |
// x and y must be in the top-left of the box | |
bool existsInBlock(int num, int x, int y) | |
{ | |
for (int i = 0; i < BOX_SIZE; i++) | |
{ | |
for (int j = 0; j < BOX_SIZE; j++) | |
{ | |
if (grid[x+i][y+j] == getVal(num)) | |
return true; | |
} | |
} | |
return false; | |
} | |
bool isValid(int x, int y, int num) | |
{ | |
return | |
!existsInCol(num, y) && | |
!existsInRow(num, x) && | |
!existsInBlock(num, x-x%BOX_SIZE, y-y%BOX_SIZE); | |
} | |
bool solve(int index) | |
{ | |
// All blocks aree filled | |
if (index == emptyPlaces.size()) | |
return true; | |
const int x = | |
emptyPlaces[index].first; | |
const int y = | |
emptyPlaces[index].second; | |
for (int i = 1; i <= GRID_SIZE; i++) | |
{ | |
if (isValid(x, y, i)) | |
{ | |
grid[x][y] = getVal(i); | |
if (solve(index + 1)) | |
return true; | |
// In case if it was incorrect solution | |
grid[x][y] = EMPTY; | |
} | |
} | |
return false; | |
} | |
int main() | |
{ | |
fast; | |
InError: | |
for (int i = 0; i < GRID_SIZE; i++) | |
{ | |
for (int j = 0; j < GRID_SIZE; j++) | |
{ | |
cin >> grid[i][j]; | |
if (grid[i][j] == EMPTY) | |
emptyPlaces.push_back({ i, j }); | |
} | |
} | |
if (solve(0) == false) | |
{ | |
//std::system("cls"); | |
cout << "This isn't solvable!" << endl; | |
cout << "Input again:" << endl; | |
goto InError; | |
} | |
cout << "\nSolution:" << endl; | |
for (int i = 0; i < GRID_SIZE; i++) | |
{ | |
for (int j = 0; j < GRID_SIZE; j++) | |
{ | |
cout << grid[i][j]; | |
if ((j + 1) % BOX_SIZE == 0 && j != 0 && j + 1 != GRID_SIZE) | |
cout << "|"; | |
} | |
cout << endl; | |
if ((i+1) % BOX_SIZE == 0 && i != 0 && i+1 != GRID_SIZE) | |
cout << "-----------" << endl; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment