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.
When I designed the project this article is based on, it was much less about producing a fast algorithm for Sudoku generation.
0 kommentar(er)
