I believe that one of the first things a new programmer has to come to terms with is the idea that many of the tasks that we can do automatically, or with little thought, are much more complicated when trying to "teach" a program. If it can be likened to anything, I think it might be the struggle of helping a blindfolded individual navigate a room. We can see so clearly where they need to go, but the real task is explaining it to someone who can't see, doesn't know what their task is, or how they will know when they get there.
In 2015, I was helping some of our student employees to learn PHP. While they were working on learning the fundamentals of recursion with a maze solver, I was looking for a project of my own. As I sometimes use sudoku as a way to keep my mind engaged while I mull over problems I decided to create a solver. Part way into the project the prime minister of Singapore, Lee Hsien Loong, received recognition for posting his C++ code to solve sudoku puzzles (BBC link). Although I glanced at his code, I had already decided to work through the problem on my own.
My goal was to create a solver that would approach solving the puzzles much the way I do. Rather than using all of the available computing power, I wanted something that would not just find the solution but would work through the problem and be able to show its work. As I made progress I also wrote a version that would use only brute force and recursion to solve the same puzzle. Surprising to me at the time, using the first method was usually much faster.
I have to be honest here, the program was probably limited by my own ability to solve the more difficult puzzles, but it works very well on easy and medium difficulty puzzles. The core idea is that unless a value is predetermined, each square has nine potential values. Most easy puzzles are solvable by simple elimination. If a value is already in the same row, column, or sector, it can no longer be a possibility for that square. Once there is only one possibility, that value becomes fixed and the process continues until all squares are fixed. As I said though, this only works for the easier puzzles. Although this same elimination strategy helps with more complex puzzles, a new method is needed. In this mode, the solver looks also at the intersection of possibilities. If you remember your set theory from math... well, then you have a better memory than me. The idea is that it rather than just looking for values that are already used, it now looks for values that can only exist in one location. If a square can be 1, 2 or 3 and no other square has the possibility of being a 3, then that square must be 3. By combining these two methods the solver can now solve many more puzzles. The problem is that for some puzzles, even that is not enough, and for that, the only solution I could find was to use brute force.
I'm not trying to say that this method is perfect, far from it. However, it was an interesting project and gave me a chance to talk to some of my friends and colleagues and ask them to vocalize how they would proceed to solve the puzzles.