This C++ code can solve a 9x9 sudoku puzzle using Backtracking Algorithm!
For the Telegram bot refer to this repository!
Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, that incrementally builds candidates to the solutions, and abandons each partial candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution. Abandoning a candidate typically results in visiting a previous stage of the problem-solving-process. This is what it means to “backtrack” — visit a previous stage and explore new possibilities from thereon.
Backtracking is a systematic way of trying out different sequences of decisions until we find one that "works."
function backtrack(position){
if (isEndOfGrid == true){ // Empty cells filled. Solution found. Abort
return true;
}
foreach (x from 1 ... 9){
grid[position] = x;
if (gridIsValid == true){ // Check for collisions
if (backtrack(nextPosition) == true){ // Move to next empty cell
return true; // Empty cells filled. Solution found. Abort.
}
}
}
grid[position] = NULL; // Empties cell
return false; //Solution not found. Backtrack.
}Given a, possibly, partially filled grid of size 9x9, completely fill the grid with number between 1 and 9.
A fully filled grid is a solution if:
- Each row has all numbers form 1 to 9.
- Each column has all numbers form 1 to 9.
- Each sub-grid (if any) has all numbers form 1 to 9.
$ git clone https://github.com/7enTropy7/Sudoku_Vision.git$ pip3 install -r requirements.txt$ cd Sudoku_Vision
$ tree
.
├── a.out
├── app.py
├── fmodelwts.h5
├── main.py
├── README.md
├── requirements.txt
├── square.png
├── sudoku.cpp
├── test2.jpg
├── test_images
│ └── 2020-02-04_01-22-40.png
├── testing123.png
├── test.jpeg
└── unsolved.txt
1 directory, 13 files
This project is licensed under the MIT License - see the LICENSE file for details