Do you know what backtracking algorithm is? If not, you have come to the right place :). I created a simple web application that allows you to solve a sudoku table using this algorithm. In short: backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution [wikipedia]. Another interesting using of this algorithm is so-called the eight queens puzzle problem. The problem is to place 8 chess queens on the board so that none of them can capture another with one move [wikipedia]. In the context of my application, backtracking looks for an empty field in the sudoku board, put on that place number 1 and checks if the all board is correct. If not, it put on the same place number 2 and checks again up to number 9. If the algorithm finds the correct number it goes to the next empty field, if not it goes back one field and looks for that field the next number. It sounds a little complicated, but it is a relatively simple algorithm. Its disadvantage is the large number of functions calls in the case of very difficult sudoku. The application allows to view the number of function calls for each solution and the duration of the algorithm.
I created this application because I wanted to practice Vue.js frontend framework in conjunction with Django Rest Framework and I wantend to improve my skils in HTML, CSS and JS ;).
- Creating an account (registration) and login into the application
- Validation the numbers entered into the sudoku board
- Solving sudoku via backtracking algorithm
- Algorithm operation statistics (operation time and number of backtracking function calls)
- Removing solved sudoku
Main technologies:
- Python 3.9.1
- JavaScript
- Django 3.0.8
- Django Rest Framework 3.11.1
- Vue.js 2.6.11
- HTML 5
- CSS 3
- Bootstrap 4.5.0
Libraries for connecting frontend with backend:
- django webpack_loader 0.7.0
- webpack bundle tracker 0.4.3
Libraries for creating registration and login forms:
- django-crispy-forms 1.9.2
Libraries for user authentication:
- django-allauth 0.42.0
- django-registration 3.1
- django-rest-auth 0.9.5
- Create folder for app.
- Open your code editor inside that folder.
- Create virtual environment and activate it:
$ python -m venv venv (if you work on Windows system)- Clone repository:
$ git clone https://github.com/adm108/SudokuSolver.git- Go to SudokuSolver folder where requirements.txt file is and install all packages:
$ pip install -r requirements.txt- Use manage.py to enter following commands. Generate SQL commands:
$ python manage.py makemigrations- Execute SQL commands:
$ python manage.py migrate- Create superuser (enter email, username and password):
$ python manage.py createsuperuser- Go to frontend folder and install all frontend packages (you should have node.js engine installed on your system):
$ npm install- Now you can open 2 terminal windows and run 2 local servers (frontend and backed). Inside frontend folder:
$ npm run serve- Inside SudokuSolver folder (where manage.py is):
$ python manage.py runserver- You can log in using superuser account or you can create the new one and then you can use backtracking algorithm to solve your sudoku!
It is a open source project. Anybody is free to use, study, modify and distribute this project for any purpose.
Great course about Django, Django REST Framework and Vue.js frameworks. It shows how to use all above mentioned technologies in one project [Michele Saba]
Simple explanation how to write backtracking algorithm for solving sudoku board [Tech With Tim]
Cool concept for creating sudoku board in HTML and CSS also with checking the correctness of the entered values [Morgan Schmiedt]
