There are 5 demo puzzles already given in the puzzles.py file and their respective solutions are stored in the solutions.py file. You can change last digits of the puzzle0 and solution0 on lines #5 and #6, respectively, to check the algorithm for different puzzles. So, if you want to skip the visualization part to speed it up, feel free to comment out the lines #28 to #30. It takes more time to show the output on every iteration. Instructions for which are commented in the same file on line #3.Ģ - The algorithm takes only ~1 second to compute most of the Sudoku Puzzles. Run the solve.py file using python to see the solutionġ - If you are using Linux or Mac you will need to change one line of code. Once the requirements are checked, you can easily download this project and use it on your machine in few simple steps.ĭownload this repository as a zip file onto your machine and extract all the files from it. Python 3.0 and above OR Python 2.2 and above.To download and use this code, the minimum requirements are: So, to solve this problem in a comparatively less time, the Backtracking Algorithm is one of the best solutions to it. For doing this in a conventional way, the processor will require to try all 2*10 77 possible combinations in a worst case scenario which is a huge number. The objective of the algorithm is to replace all the zeros with valid digits such that the entire Sudoku Puzzle is solved. This is a project which takes an input of the sudoku puzzles as an 81 characters long string containing the digits from 0 to 9, where 0 represents an unfilled cell of the Sudoku Board. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that compose the grid contain all of the digits from 1 to 9. Sudoku is a logic-based, combinatorial number-placement puzzle. I’ve tested it with both regular size Sudokus and mini-size (6×6), and it seems to preform pretty fast.Sudoko Solver using Backtracking Algorithm Another nice thing, is that if there isn’t a unique solution, it will be output say which cells have definite value, and output the constraints that hold for the rest of the cells. You can see below a prolog solution that demos solving a Sudoku. Now solving is easily by passing integers instead of the variables. Vars = ,Īll_different(),Īll_different().Īgain, not so pretty, but it’s python-generated hence simple as hell. Rects.append("all_different()")įor example running the script with 3 3 as arguments generates a regular 9×9 Sudoku solver. Rows.append("all_different()")Ĭolumn = Ĭolumns.append("all_different()") Vars = map(lambda j: VAR_TEMPLATE % (i,j), range(x*y)) ![]() The script gets the dimensions of the sub-grid. As mangling with lists in prolog isn’t fun, I’ve wrote a python program that outputs all the prolog statements with hardcoded references to the variables which build-up the board. You need to state that every cell is in a given range and that all rows, columns and sub-grid contain different integers. ![]() I although kind of liked it as I haven’t done anything in Prolog for quite a few years.ĭescribing Sudoku in terms of constraints is extremely simple. I chose Prolog because as a logic programming language, constraints are its bread and butter. I considered several libraries but in the end I’ve settled on plainly using Prolog. So while pondering whether it would be interesting enough to go forward and actually implementing the algorithm compared to the work it would require, I started thinking what will be the simplest way to solve such puzzles, as opposed to efficient.Īt first I’ve looked at general purpose constraint solvers, and decided to tackle Sudoku instead as it’s a bit simple to define in terms of constraints. Two weeks ago, I add came up with an interesting algorithm for solving Hidato which basically involves decomposing the board the grid (can be square, hexagonal or any other shape), into classes of pieces and then arranging them (maybe I’ll write a detailed post on it in the future).
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |