Lessons I learned while developing a Sudoku solver application
First lesson: do not rush into writing source code
Photo by Richard Bell on Unsplash
First lesson: do not rush into writing source code
Before commencing work on your algorithms, ensure that you have a clear understanding of what your application is intended to accomplish.
Upon initiating the development of my Sudoku solver, my primary objective was to acquaint myself with the Swift programming language. My sole focus was on devising an algorithm that would accept an unsolved grid as an input and generate a solved one in return.
Only after I had successfully completed this challenge did I consider creating an application
Upon examining the offerings of my competitors, I believed it would be advantageous to develop an application capable of not just resolving Sudoku puzzles, but also elucidating the process through which this was accomplished, step by step.
The problem lay in the fact that my algorithm had not been engineered to provide explanations, and modifying it to do so would have posed a significant challenge due to its heavy reliance on brute force.
Therefore, I was compelled to initiate the process anew, commencing from the ground up. Rather than having the algorithm generate the ultimate grid as its output, I needed to devise a mechanism for returning an explanation object.
We differentiate between value setting techniques and candidate removing ones.
For the former ones, we ascertain that a cell should hold a specific value. In the later ones we establish that a cell is not permitted to contain a particular value.
The explanation object that we create consists of a list, which may contain zero or one candidate removal techniques and exactly one value setting technique.
Using those data, I was subsequently capable of generating human-readable instructions for resolving a Sudoku grid, on step at a time.
The second lesson: Discovering simple optimization techniques that can be easily implemented.
Upon initiating the development of a grid generation component, I sought to ensure its execution was both expeditious and efficient. In order to accomplish this objective, certain optimizations were implemented within my application. The subsequent discussion outlines several techniques employed during this process.
Lookup tables
In my algorithms, I frequently require converting from cell index positions to grid coordinates — specifically, determining the corresponding row and column numbers for a given cell index.
I began employing division and modulo operations for this purpose, yet I subsequently discovered that utilizing lookup tables proved to be far more efficient.
A lookup table (LUT), also referred to as a data lookup table or a reference table, is an organized collection of pre-calculated values. The role of this table is to facilitate the retrieval of specific information by converting input parameters into the position of an element within the array and subsequently returning the corresponding value.
For instance, one of my lookup tables (LUT) is an array where the index used is the cell position in the row (i.e., the index of the column being referenced), and the value returned is that of the corresponding column.
Reserve the capacity for an array prior to using it
When introducing new elements into an array, a verification process takes place to guarantee that the allotted memory block remains sufficient. In case it does not, a larger memory block is identified and the existing array content is transferred into it. Subsequently, the previously allocated memory block is released.
Pre-reserving the capacity of an array enables a reduction in the time expense of operations that enlarge the size of the array.
The candidate set structure
In order to implement my algorithms, it’s essential to maintain a record of potential values for cells lacking a definitive value. Initially, I opted for utilizing a Set
It appears that it wasn’t particularly effective.
I have substituted those sets with a class, employing a binary mask technique. An unsigned integer in this approach serves as the mask, with its first nine bits representing potential candidate values. If a bit is set to zero, the corresponding value is no longer an option; if it’s set to one, the candidate remains possible.
In order to decrease the time required to replace every occurrence of Set
To conclude
I have learned a lot from this project and I hope reading this article may inspire you for your current or future projets.
Side projects can be an excellent means for us to test our abilities and enhance our technical expertise.
That’s all folks!
PS: this article was not written using ChatGPT, but a Mistral 7b instruct model was indeed used to help rewrite sentences into proper English.