Skip to content

Instantly share code, notes, and snippets.

@Muaath5
Created February 3, 2022 21:20
Show Gist options
  • Save Muaath5/70e9954f73dec8b82122a33a981e8684 to your computer and use it in GitHub Desktop.
Save Muaath5/70e9954f73dec8b82122a33a981e8684 to your computer and use it in GitHub Desktop.
C++ console app that solves sudoku 9x9 via Backtracking (Recursion)
// 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