University of North Carolina Wilmington



SudokuKimberley Parnell, Skylar Freeze, Phillip SmithUniversity of North Carolina WilmingtonAbstract The goal of this project is to design a variety of algorithms that are capable of solving standard 9x9 Sudoku puzzles of ranging difficulties, in order to learn more about Sudoku solving techniques and to better understand constraint satisfaction problems as a whole. We began by using a na?ve brute force algorithm to solve the puzzles. While a brute force approach is capable of solving any puzzle in a given amount of time, it has the chance of requiring a substantial amount runtime to reach the correct solution. An optimized take on the brute force algorithm we developed was also produced, and showed noticeably improvement upon the initial brute force results. In an attempt to find a more logical and efficient algorithm, an iterative depth first search algorithm was also designed and implemented. This method improved the average runtime, but could still potentially take over thirty seconds to solve a difficult problem and averaged roughly five seconds on the hardest difficulty. An improvement to this was the recursive backtracking algorithm, which solved the hardest puzzles attempted in an average of less than a second. Also, a stochastic algorithm was implemented to learn how a stochastic technique could be applied to a Sudoku puzzle. All algorithms presented were written in the Python programming language and all algorithms, with the exception of the brute force algorithm, were tested on the same 75 Sudoku puzzles, 25 from each difficulty level (easy, medium, and hard). The brute force and optimized brute force puzzles were tested solely against the 25 easy level puzzles, as well as their own set of ‘simple’ puzzles, to test their efficiency and range. Also, the results for the depth first search and backtracking methods were further validated using 1000 additional Sudoku puzzles from each difficulty range.Key Words: ? Algorithm, Backtracking, Brute Force, Stochastic Search, Stochastic Search, Depth First Search, Constraint Satisfaction1. Introduction Our group, Team Sudoku, has created and implemented five different algorithms that are capable of solving a standard 9x9 Sudoku puzzle. To complete a standard Sudoku puzzle one must fill a 9x9 grid with the digits 1 to 9 so that each column, row, and subrectangle contain all digits 1 to 9 within them. A starting grid is partially filled by a selection of given values that determine the puzzle difficulty and the uniqueness of the solution. Our algorithms will be tested on a 9x9 sized puzzle and we will analyze how well each of these algorithms solves a puzzle, based on the depth, speed, and coverage. Algorithms will be assessed based on the number of iterations the algorithm has to run before a solution is returned, the time it takes an algorithm to run before it returns a solution and lastly, the range of puzzles an algorithm is able to handle. 2. Formal Problem Statement Formally speaking, a standard square Sudoku puzzle, based on the original, unmodified game format, is solved by filling an NxN two-dimensional array with N distinct symbols in such a way each cell of the array contains only one symbol and each row, column, and subrectangle of the array is a permutation of the N symbols. Each subrectangle is a MxM two-dimensional array where M is equal to sqrt(N). The number of sub rectangles within the array is equal to N.The solver algorithms will search for a valid (/unique) solution to the inputted Sudoku puzzles. Testing will determine which algorithm solves the puzzles most efficiently. Efficiency will be determined by time elapsed and number of attempts needed. The range of puzzles that the algorithms are able to complete will also be considered.3. ContextThe name Sudoku comes from the Japanese, who brought the modern Sudoku puzzle into the mainstream, and consists of the Japanese characters Su, meaning ‘number’, and Doku, meaning ‘single’. Sudoku was originated, however, in Switzerland, by a mathematician named Leonhard Euler. Euler created the modern puzzle using the consolidation of the mathematics pioneered by Isaac Newton. A major contributor in the study of solving Sudoku puzzles through the use of computer programming is Peter Norvig. Norvig wrote an essay on tackling the problem of solving every Sudoku puzzle using two ideas: constraint propagation and search. Constraint propagation is the process of finding a solution to a set of constraints that impose conditions that the variables must satisfy, and idea of searching involves finding an item with specified properties among a collection of items which are coded into a computer program, that look for clues to return what is wanted. The results from his essay showed that the average time to solve a random puzzle was 0.01 seconds, and more than 99.95% took less than 0.1 seconds. His results were produced from the solving of a million randomly generated puzzles.4. Difficultly in SudokuIn Sudoku, a standard 9x9 grid, as we have focused on for the purposes of this project, must have at least 17 given values to be deemed ‘solvable.’ A ‘solvable’ Sudoku puzzle is one that has a unique solution. A puzzle with 16 or fewer given values will have more than one possible solution, preventing it from being a ‘true’ Sudoku puzzle. This statistic was determined by a study completed and published in 2012 by a student at University College Dublin, which was later supported at a mathematical conference in Boston Massachusetts. The average puzzle one can find in a newspaper has approximately 25 give values, with the number tending to decrease as the puzzle difficulty grows.In Sudoku, there are five levels of difficulty, ranging from Easy (level 1) to Master (level 5). The level of difficulty of a given puzzle is determined by the manner in which a player is required to go about solving the puzzle. The difficulty levels are broken down in a way such that:? Level 1 - The puzzle is solvable by reducing possibilities of square to a single value.? Level 2 – Player must locate the occurrence of number pairs within the puzzle.? Level 3 – The player must utilize special techniques such as ‘X-Wing’ or ‘Y-wing’ techniques, requiring the player to take a more tactical approach. ? Level 4 – Requires the use of ‘Forcing Chains’ where the Sudoku player must make a guess of a possible solution, then trace that guess to determine if it can fit and produce a valid solution (aka ‘Guess and Check’) ? Level 5 – Requires the Sudoku player to use trial and error to map out a possible solution, or to make use of lookup tables. These puzzles cannot be solved by logic alone.Difficulty can also be affected by how the given values are placed within the grid. 5. BacktrackingThe backtracking algorithm solves each unassigned/empty space (represented by a ‘0’ in this algorithm) one at a time, the order determined by its current row and column. It then searches through a list of numbers ranging from 1 to 9, to check if the constraints were satisfied. The three constraints that need to be satisfied to find the unique solution of the puzzle are that no two of the same numbers are presented in the current row, column or 3x3 subrectangle. The algorithm continues to the next blank space to do this same process so long as the constraints are satisfied and until the Sudoku puzzle is solved. If it is determined that the space that was previously solved will not solve the Sudoku puzzle, the algorithm backs up from its current state and finds other valid solutions which will satisfy all constraints.Figure 5.1247657556500Figure 5.1 shows the data after running 25 puzzles, ranging with the level of difficulties of easy, medium and hard. Puzzles that were easy resulted in the least of amount of average time. The average time for easy, medium and hard puzzles were recorded as 0.1903, 0.2171 and 0.2052 seconds, respectively. There was no distinct correlation between puzzles with the difficulty of medium and hard, and the backtracking algorithm was able to successfully solve all three difficulties. To further analyze the correlation between ranging difficulties of Sudoku puzzles based on computational time, data from a sample size of 1000 Sudoku puzzles, ranging from the same level of difficulties was recorded. With a larger sample size than previously recorded, the data shows a correlation between the level of difficulty and time, as it takes the backtracking algorithm the most time to solve the hardest level of difficulty. The number of recorded iterations the backtracking algorithm implemented had a correlation with the ranging level of difficulties, as well. The algorithm tended to require more instances of backtracking the harder the difficulty of the puzzle, because there would be a larger set of numbers that would satisfy the constraints, therefore requiring more recursions. For its complexity, the backtracking algorithm has a Big-O notation of O(n!)n, where n factorial represents the number of possible values within a Sudoku puzzle. The algorithm will go through each number from 1-9 to see if it satisfies the constraints, this is represented by the n factorial in the Big O. Once it finds the value or values that could be a possible solution it pushes the value or values into an ordered stack and pops the first value that into the unassigned space. The algorithm will go to the next unassigned space and do this same process again. If the algorithm is at an unassigned space where there are no possible numbers that can satisfy the constraints, it will then keep the unassigned space as a ‘0’ and backtrack to the last assigned space. Once it goes back to the last assigned space, the algorithm will assign the current space to the next popped number from the stack. The number of times the algorithm would backtrack, to show that it requires another number from the stack of possible values, is represented as the nth power.6. Brute Force The brute force algorithm created for this project was completely randomized and given minimal logic. It featured no optimization in order to distinctly differentiate itself from the backtracking algorithm developed for this same problem. Our algorithm represented an extremely na?ve solving system in contrast to the different logic-based algorithms that we designed.The algorithm begins by reading through each value in the array, one row at a time. When it lands upon a ‘0’ (the symbol in our programming for an empty cell), the algorithm sends two lists to an outside method: a list of all the integers in that value’s row and a list of all of the integers in that value’s column. The outside method, genRandom, then continuously generates a value between 1 and N until it finds one that does not already exist in the given row or column. If the generator runs through all N integers it will return its state as broken, recognizing that the current randomized solution is incorrect and does not fit within the constraints of a valid Sudoku solution.After a random value has been generated, it will be returned to the main algorithm and replace the ‘0’ value at its index. The algorithm will then continue through the rest of the array until it reaches the end, having found a valid solution. The algorithm will also run an outside method after finishing each set of sub rectangles to ensure no repeated values within the sub rectangles, verifying that the generated solution is remaining within the constraints of a valid and correct solution. While effective on the smallest tested puzzle size (4x4), the brute force algorithm becomes exponentially less efficient as the puzzle size increases. As the algorithm is randomized and does not utilize any optimization, it relies solely on luck. The range of attempts needed to solve the solution using the brute force algorithm was highly variant and had no distinguishable correlation. In relation to that, there was also a high variance in runtime needed to solve the puzzles. Because of this, the brute force algorithm developed is a very inefficient and ineffective method of solving the Sudoku problem. Figure 6.1The variance for the times and attempts needed for our brute force algorithm to solve a given puzzle was tested by running the same puzzle through the algorithm one-hundred times. The results (as seen in Figure 6.1 above) were highly inconsistent and relied solely on the luck of the draw from the random number generator. In addition to a very basic brute force algorithm, we also created an optimized brute force algorithm. The optimized form of the algorithm utilizes the same general process as the original, however it takes the subrectangles into account when generating a randomized number. This optimized algorithm has increased effectiveness, though it is still limited in contrast to the backtracking and DFS algorithms we developed. The optimized brute force algorithm we developed improved the randomized algorithm’s ability to solve the puzzles. While the basic algorithm we developed for a brute force approach was unable to solve any puzzles in the easy set of 25 puzzles in under 2 million attempts, the algorithm in its optimized form had approximately 60% coverage of the same puzzles, the majority of which were solvable in half a million attempts or less. The optimized algorithm was also run against the previously presented puzzle for one hundred attempts. Adding the additional constraint in regards to the subrectangles greatly reduced the needed attempts and the variance of results.Figure 6.2While the original brute force algorithm we developed took an average of approximately eleven-thousand attempts to solve (minimum of 154, maximum of 51,735), the optimized algorithm took an average of approximately 60 attempts (minimum of 3, maximum of 247). The average runtime was also decreased, with an initial average of 2.65 seconds, and an average of .06 seconds in the optimized form. In decreasing the chances of error coming from the random generator, the effectiveness and efficiency of the solver was increased. In regards to complexity, both algorithms share a Big-O notation of O(n), n being the number of unknown values in the puzzle. For each unknown value, there are a maximum of nine possible solutions, depending on givens. For each additional unknown value n, the runtime of the program increases. The algorithm does not attempt to make corrections to detected errors, and instead breaks out of the grid and ends the algorithm upon finding an incorrect guess. This means that the longest runtime of the algorithm will be a correctly guessed solution which makes it to the end of the grid rather than breaking out of the algorithm early. Since the algorithm is completely randomized, it keeps no record of guessed solutions, making it potentially infinite, as it can continue to make the same errors repeatedly without correcting itself. Because of this, the algorithm is NP, nondeterministic. 7. Stochastic Search The other randomized algorithm developed for solving the Sudoku problem was a stochastic search algorithm. The stochastic search algorithm runs through the given puzzle array and locates all empty ‘0’ cells. For each empty cell, it generates a random number that does not already correctly exist in the row and column for that given cell. After creating a randomized solution for the puzzle, the generated solution is then checked against the correct solution. All correct guesses are saved to the puzzle being solved, while all incorrect guesses are reset back to zero. This algorithm was run against a series of easy, medium, and hard level puzzles. While there was a minor positive correlation between the difficulty of the puzzle and the time and attempts needed, the increase was minimal. There was also enough variance in the results that a lower difficulty puzzle might not consistently run more efficiently than a higher level puzzle. Stochastic Search ResultsDifficultyEasyMediumHardAverage Attempts7.128.08.33Min/Max Attempts5/125/115/11Standard Deviation (Attempts)0.00760.006770.00894Average Time0.04196s0.04775s0.05917s The complexity for the Stochastic Search algorithm that we developed is also O(n). It also depends on random generation of numbers, and while it is unlikely, there is a worst case scenario in which the generator will continue to guess an incorrect solution infinitely. Because of this, the algorithm is also NP, nondeterministic, though less obviously so than the Brute Force algorithm. This algorithm is much more efficient than the brute force form of randomized search we developed, however, due the requirement of having a solution to compare the generated solution to, this algorithm is not very practical. A user would need to supply the puzzle’s solution, making this algorithm obsolete in real world and practical application.8. Iterative DFS (Depth First Search)The iterative DFS algorithm begins by creating a fixed list that holds the placement of the initially provided Sudoku entries and an empty list to hold what values were attempted for each empty square. It then starts iterating over the Sudoku squares, stepping over squares that are in the fixed list. When it finds a blank square it calls an outside method to determine the first possible entry that does not violate any constraints provided. That entry is returned, placed in the blank square, and that value is added to the tried list for that square. This is controlled by a while loop whose exit condition is the puzzle being solved. If the algorithm reaches a blank square ‘X’ which has no possible moves it will reset the previous entry ‘Y’ to blank, empty the tired entries for X and every entry past it, and start again from Y. This algorithm uses a depth first search technique to choose which values will be entered into the blank squares first. A tree is created whose branches are the possible entries for each blank square sorted in ascending order and the lowest possible entry is always chosen first.This algorithm was able to solve the easiest Sudoku puzzles in an average of 0.049123 seconds with an average of 2146.76 steps. However, when presented with medium or hard puzzles this algorithm performed much slower than the recursive backtracking algorithm requiring an average of 3.924969 seconds for the medium difficulty and 3.874782 for the hardest difficulty. This indicates that the algorithm’s runtime is not affected by the difficulty of the puzzle and rather the number of blank entries and location of the given entries. With a correlation between runtime and the number of fixed entries at the beginning of the puzzle. The time complexity of this algorithm has a worst case of O(0mm^n) where n is the number of blank entries in a given Sudoku puzzle and m is the number of possible entries for a blank square. Each entry can have a maximum of nine possible values. However, repetition is not allowed so the sum will go from zero to m.Figure 8.1Iterative DFS ResultsDifficultyEasyMediumHardAverage Attempts2146.76186451.2182351.4Min/Max Attempts116/8376725/2069883164/869566Average Time0.04912s3.924962s3.874782s8. Interpretation and conclusionsAll of our algorithms succeeded in meeting the goal of our problem statement, which was to solve a standard 9x9 Sudoku puzzle. The brute force algorithm was the most na?ve and was written directly from the problem statement. It is capable of solving any puzzle, but it is a NP solution and the least efficient algorithm we designed and implemented. It doesn’t keep up with any information about previous attempts it has made as it solves a puzzle. In contrast, the iterative DFS algorithm does a lot of book-keeping, tracking both possible moves for an entry and tried moves for that entry in the form of Python lists. The Iterative DFS algorithm also offers a structured approach to solving the puzzle, attempting entries in a DFS branching style. This improvement allowed for solving medium and hard level Sudoku puzzles, which the brute force algorithm was incapable of doing in a reasonable amount of time. The recursive backtracking algorithm was the overall most effective, solving hard level puzzles in an average of 0.2052 seconds, compared to the Iterative DFS algorithm which solved hard level puzzles in an average of 3.874782 seconds. This is because the recursive backtracking algorithm did no book keeping, other than the current layout of the board and was unencumbered by the lists the iterative DFS algorithm kept up with. It managed to iterate over the possible entries and did not require a list to store entries that were previously tried. The Stochastic algorithm was very effective at solving any level Sudoku puzzle. However, it had the advantage of using the solution to solve the problem. All of our algorithms we affected more by the number of given entries and the placement on the board of those givens rather than the difficulty of the puzzle. The more blank squares there were the more our algorithms iterate to fill them in. Also, the more blank entries towards the beginning of the puzzle resulted in longer runtimes which required more backtracking. This leads us to believe, in conclusion, that (at least in regards to a computer program,) the difficulty of a Sudoku puzzle to be computationally solved is directly correlated to the placement and number of provided entries, rather than the human techniques required solve said puzzle. This causes some easy puzzles to require less time to solve than some medium puzzles and some medium puzzles taking less time than certain hard puzzles. ?9. Future WorkOur project handled the most standard and universally known puzzle size, which is the 9x9 Sudoku puzzle. In future efforts towards this problem, we would aim to have our algorithms be applicable to a greater variety of puzzle sizes, such as 16x16 or 25x25 puzzles. We could use this information to study the impact that puzzle size has on the efficiency of the solver algorithms. We could also potentially look at solving modified, non-standard puzzles which do not require the square approach of an equal number of columns and rows. In regards to our testing, another addition we could also look into would be to add more factors to analyze the efficiency of our algorithms, such as measuring CPU usage. With this data we could then determine the correlation between CPU memory usage, algorithm runtime, and the puzzle’s given level of difficulty. For additional algorithms, we could work to apply more techniques, such as analyzing a more ‘human’ approach. One such example of this would be the grid (i.e. if in a 9x9 grid the number ‘3’ exists at grid positions (0,1) What is the Big-O notation of a Depth-First Search?O(V + E): V stands for the vertex’s and E represents the edges between them. 11. Sources (2, 7), through examination, the algorithm could determine that the last instance of ‘3’ within that column of subrectangles must be at index ‘1’ for the middle subrectangle, limiting the field of possibilities for the final ‘3’ to (1, 3-5)). There are a number of mathematical approaches and logic-based techniques that could be studied as possible algorithmic approaches in the future. 11. Questions For an MxM subrectangle of a Sudoku puzzle that is NxN, what is the value of M in relation to N?M = sqrt(N)Why does our Brute Force method of solving Sudoku result in such greatly varied runtimes and needed attempts?It uses minimal logic and depends entirely on the luck of the random generator’s guesses. What is the meaning of Stochastic?Stochastic means “randomly determined”.What solving technique do most humans used when faced with a “difficult” Sudoku puzzle?Brute Force. ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download