So, how do we do this? Well, first, let’s look at the minimzation (also read optimization) problem before us. Check out the Dancing Links algorithm created by Donald Knuth for a more general approach to solving problems like this. There are many decision optimization problems that can be solved using this technique. This allows us to minimize the number of incorrect guesses, which will reduce the number of times we need to backtrack, ultimately improving the performance of our solution. Instead of picking a random square, it would make more sense to only pick squares that give us the greatest possibility of being right. It just randomly picks a square, and then randomly picks a number, but what if we could add some intelligence to those guesses. Currently our sequence doesn’t seem to do anything intelligent with its guesses. The question is, can we make our program’s job easier? And the answer is “Yes.” The DesignĪt the heart of Sudoku is essentially a decision optimziation problem. The problem, is that there are 6.67x10^21 solutions to a Sudoku grid, so letting our program just fumble around guessing solutions is probably not something we’re going to hang around for.
In fact, with just this algorithm we can find a solution to every Sudoku puzzle. This is the basic skeleton of our algorithm. Rinse and repeat until the puzzle is filled.If no number matches our conditions, then we made a mistake earlier, so back up to the previously selected square.If the number is not in the same row, column, or grid as the selected square, then place the number, otherwise, select a different number.Simple, right? So essentially the sequence of our game is as follows: If you’ve never played Sudoku before, here is the objective:įill a 9x9 grid with digits so that each column, each row, and each of the nine 3x3 sub-grids that compose the grid (also called “boxes”, “blocks”, “regions”, or “sub-squares”) contains all of the digits from 1 to 9. The Ideaįirst, let’s think about the algorithm before we begin coding. However, it should be easy to follow the logic discussed here. It has a few additional optimizations that don’t assist in our search for knowledge and edification.
Solving sudoku algorithm c uiuc code#
This code will not be the exact same as the code presented here. And better yet, we can implement the solution in our favorite programming language - C#! So why all this talk about Sudoku? Well, it turns out that the solution to the puzzles that most people reason out in their heads can be conveniently constructed into a computer algorithm that can solve any Sudoku in fractions of a second. Most people believe that the game originated in Japan, but earliest records indicate that during the 18th century, the genius, Swedish mathematician Leonhard Euler began formulating a number puzzle very similar to the Sudoku we know today. Any Sudoku fans out there? This cool little combinatorial puzzle has been around for thousands of years in many different forms, but the most popular version that we know of today gained a mainstream audience only within the last decade.
0 kommentar(er)
