Abstract : 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. 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. 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. And better yet, we can implement the solution in our favorite programming language - C#!
? This algorithm is quite efficient because it does not have to check all the possibilities that exist, but which leads to only the solution that will be processed, namely by pruning every element that does not lead to the solution.
? Thus the time required is quite efficient and suitable for use in reasonably complex numbers games like sudoku.
? The backtracking algorithm flowchart is a data flow based on an existing algorithm.
? Algorithm complexity is done by finding the big theta of the existing pseudocode. This pseudocode is part of a program that has been designed according to the backtracking algorithm.
? This technique is known as constraint propagation, a powerful optimization techinque used to solve complex decision problems where choices have consequences that “ripple” across the solution space.
? At the heart of Sudoku is essentially a decision optimziation problem. Currently our sequence doesn’t seem to do anything intelligent with its guesses.
? If we are minimizing our problem space, then that means there must be a set of constraints (or rules) that we must adhere to in order for our decision to be optimal, and since we know the rules of the game, let’s start there.
• This paper proposed a solution to solve Sudoku using the Backtracking Algorithm.
• The backtracking algorithm is one of the problem-solving methods included in a strategy based on searching the solution space, but it does not have to examine all possibilities, only those that lead to only solutions will be processed.
• Algorithms backtracking is also an algorithm that works recursively, where the search process is based on the Depth-First Search (DFS) algorithm, which is to search for systematic solutions to all possible solutions and search for answers is done by tracing a tree-shaped structure rooted.
? 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.
? There are many decision optimization problems that can be solved using this technique.
? This allows my minimum lookup to take place in essentially one operation.
? This improved performance by about 25%, so implementation approach can definitely have a lot of weight on how your solution performs.
? My solution is not the most efficient solution out there, and there are a few links to other implementations.
|