So, I decided to make a robot that can follow the same thought process that I was using but hopefully solve the puzzles a lot faster and without manual effort.
My brain was having fun, but my writing hand was getting sore. This tedious manual effort can cause an infraction to Rule 3: “Have fun!”Īfter playing Sudoku many times myself, I realized that I was using the same patterns, again and again, to find the solutions to these puzzles. Sometimes, these strategies can be very repetitive and require a lot of manual effort to execute (the game is typically played on paper with a pencil).
While the game itself can be challenging and complex, several strategies can be used successfully to find the solution. For very hard puzzles, that number can be much higher. It is believed that the average Sudoku player spends approximately 20 minutes solving a typical Sudoku puzzle. Stop when each row, column and nonet’s sum is equal to 45.īased on all of these steps and on the rules we stated earlier in the formal definition, we can build an algorithm which might be successful at solving problems faster.It seems simple, right? Wrong! It can be incredibly challenging to solve a Sudoku puzzle.Go to 1., select the next row that have the second least number of empty cells, and so on.Select a cell which has a unique possible number, that no other cell have in that row, then select that unique number pn.Then go to the next cell, so j=(index of next empty cell), and repeat 3. If you checked all the numbers from p(i) for the x(i,j) cell.Still remain on the j-th empty cell of that row x(i,j), check all the other numbers of p(i), if they are possible to place onto the cell write them down similarly like in 4.Write down the selected number from 3.and check if there is a number that is not in the current column and not in the current nonet. Go to the j-th empty cell in the selected row x(i,j), then go through the possible numbers p(i), that was selected in 2.Check which numbers are NOT in that row, and write them next to the puzzle, name them p(i) (these are the numbers which could go into that empty cells).Select the row x(i) with the least number of empty cells, i=(row index for row, having the least number of empty cells).There are some techniques for doing it, here is simplified step-by-step way of doing it: Photo by Mark Fletcher-Brown on Unsplash A Unique Approach Solving sudoku on paperįirst, we should discuss what a human person would do to solve a sudoku puzzle on paper. Find a solution that is in P for that problem.ģ. Understanding how protein folding works and being able to predict the fold of a protein is a critical step in finding the cure of cancer. It is really hard to fold up proteins properly. Protein folding is related to the formulation of cancer cells, where the task is to make a 3D protein coil from a 2D one. Protein folding is an NP-C problem, so if you can solve Sudoku in polynomial time, protein folding can also be solved. Interesting to note about NP-C problems, that If a solution is found for only one of the NP-complete problems that is in P, then that will lead us to the solution of all the NP-C problems. The cure of cancer lies in protein folding Sudoku algorithms are currently NP-complete (NP-C), meaning It is in NP, the solution for any puzzle can be quickly verified if known, but there is no known algorithm for sudoku that is in P. NP includes the following problems: shortest path (once the shortest path is found, verifying the solution is really easy), the traveling salesman, satisfiability problems. NP (Non-deterministic Polynomial time) is a set of functions/algorithms that can check the solution quickly (in polynomial time). Some example P problems are: sorting a list of numbers, finding the greatest common divisor, etc. So more simply saying, P algorithms can solve a problem quickly. P is a set of functions/algorithms that can solve a problem in a relatively short time. Once a sudoku algorithm is found to be in P ( Polynomial time), meaning that the solution can be found in a relatively short time, then fundamentally, It will lead us to the cure of cancer. First I’ll tell why the algorithm that solves a sudoku puzzle could lead us to the cure of cancer, then I’ll introduce the formal description of the problem, then I’ll introduce the most used algorithms and the comparison of their runtime, lastly I’d like to meditate on some unique algorithms. In this article, I would like to show the most efficent algorithms that can make a computer solve any sudoku puzzle. Sudoku is also called Number Place Puzzle. Even if you play a lot of sudoku, you will find it very difficult to improve in the speed of your game.
0 kommentar(er)
