![]() ![]() If Conflicts(Squares, Item(c, z)) = False Then ' do a check with the ' proposed number Next Next Do Until c = 81 ' we want to fill every square object with values If Not Available(c).Count = 0 Then ' if every number has been tried ' and failed then backtrack Dim i As Integer = GetRan( 0, Available(c).Count - 1) ![]() For this example, I used an arraylist of generic lists.ĭim Squares( 80) As Square ' an arraylist of squares: see line 86 Dim Available( 80) As List( Of Integer) ' an arraylist of generic lists (nested lists) ' we use this to keep track of what numbers we can still use in what squares Dim c As Integer = 0 ' use this to count the square we are up to For x As Integer = 0 To Available.Length - 1 The most important part of backtracking is, logically, keeping track of what has already been tried and where, or, in this case, what hasn't been tried where. Changing the 6 to a 1 would fix this problem. Therefore we have to backtrack, in this case back to the 6. every number bar 1 has been used on this line, but 1 has been used above, in the same column and the same region. We've been going fine so far for the first 17 numbers, but when it comes to finding a valid fit for the 18th number there are no valid options. There is only one rule to Sudoku, every number form 1 to 9 must be placed once, and once only, in every row, column and 3x3 region. Just in case you have forgotten or are unsure. Below is a basic diagram showing the general flow of the algorithm: Sudoku It is fast, effective and reliable if done correctly. Backtracking best works in a linear method. Likewise, backtracking with a random placement method is equally ineffective (trust me I've tried both). ![]() It's nearly impossible to produce a valid Sudoku by randomly plotting numbers and trying to make them fit. Essentially it's like walking through a maze with some golden thread and going back and forth down dead ends until you find the right way out. When a problem occurs, the algorithm takes itself back one step and tries a different path. The basic principle of a backtracking algorithm, in regards to Sudoku, is to work forwards, one square at a time to produce a working Sudoku grid. That was impressive enough but thanks to Keith B., Imperiatus and Spirch, now the generator can now produce a Sudoku at an average of 0.018 seconds. A Sudoku generator that does not make a mistake, is less than 300 lines of code and makes a Sudoku in 0.07 seconds. The result of this combination and application of the backtracking technique has resulted in exactly what I aimed for. To do this, I used three main parts a specialized structure, array lists and generic lists. The aim of this project was to create a fast, short and reliable Sudoku algorithm. Little did I know I'd reduce my all time best 5 second algorithm to a mere 0.07 second algorithm. No, this project was about testing myself that little bit further to learn new ways of dealing with things and, overall, improving my previous code with the new things I had learnt. For all intents and purposes, I had already achieved this in a previous project. Those are tough to find! Also, sometimes the 2-2-2 type Swordfish can be really tricky to find in a puzzle.When I designed the project this article is based on, it was much less about producing a fast algorithm for Sudoku generation. Especially when there's a 2-2-2-2 Naked Quad wrapping a 2-2-2 Hidden Triple. My record on this level one minute 58 seconds. With "Hard" level on Andoku 3 you need to be an expert in X-Chains, Naked Quads, XY-Wings, and Swordfish. Hodoku considers a Sashimi X-Wing as "Hard" which most other sources would consider it as "Extreme."ĪIC Nice Loops and XY-Chains make it extreme. And Hodoku's hard level puzzles would be classified as extreme in other sources. Many people would characterized Hodoku's medium puzzles as hard puzzles. For example, on Hodoku, medium puzzles can require hidden pairs and hidden triples. What defines a puzzle's difficulty level are the puzzling solving techniques needed to solve it. I think labeling a puzzle's difficulty level is completely the wrong approach. What is considered easy, medium, hard, and extreme is not consistent. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |