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 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |