How I Came Back to an Old Problem and Finally Wrote a Sudoku-Solving Algorithm

Several years ago, as a bright-eyed but inexperienced college student taking my first steps into the world of computer science, I encountered a programming assignment that would, for a time, thoroughly vanquish my coding aspirations. The task was deceptively straightforward: write a program in C++ to solve any given Sudoku puzzle.

At that point, my programming journey had just begun with an introductory Python course the previous semester. I had enrolled on a whim, with no real coding background, but quickly found myself enchanted by the power and potential of software. Intoxicated by early victories writing simple games and scripts, I decided to dive deeper into the CS curriculum.

The followup course on data structures and algorithms, however, served as a rude awakening. Taught in C++, a language we were expected to pick up independently over the summer, the class moved at a relentless pace. The professors made no secret that their aim was to separate the "real" computer scientists from the dabblers. By the semester‘s end, half the students had withdrawn or failed, and we had downsized from a large lecture hall to a modest classroom.

I stuck it out more through stubborn pride than any real understanding of the material. Late nights at the computer lab became my norm as I struggled to wrap my head around pointers, memory allocation, and recursive algorithms. The Sudoku solver assignment crystalized my difficulties. After innumerable caffeine-fueled hours, my submission worked for a handful of test cases but buckled under more complex inputs. The C+ grade I earned was generous.

Dejected and demoralized, I gave up on computer science after that semester. I resigned myself to focusing on my other academic interests, writing and politics, relegating coding to a brief failed experiment. Looking back, I‘m struck by how readily one challenging experience was able to derail my programming pursuits. It highlights some core issues with how we teach and gatekeep computer science, a topic I‘ll return to later.

As it turns out, my coding days were far from over. A few years after graduating, I found myself drawn back to the world of software, this time in the more pragmatic context of web development. I threw myself into learning JavaScript, HTML, CSS, and relevant frameworks, building a portfolio of small projects. In time, I landed my first developer role and began growing into the full-stack engineer I am today.

Recently, I decided to revisit the once insurmountable Sudoku challenge, both as a way to gauge my growth and exorcise old demons. Would the problem that haunted my college dreams still prove unassailable? Let‘s find out!

Sudoku 101

For the uninitiated, Sudoku is a logic-based number-placement puzzle, typically played on a 9×9 grid. The grid is subdivided into nine 3×3 boxes, with some cells pre-filled with digits from 1 to 9.

The goal is to fill the remaining cells such that each row, column, and 3×3 box contains the digits 1-9 exactly once. A well-formed puzzle has one unique solution that can be arrived at through logical deduction alone.

There are countless strategies and heuristics humans can employ to tackle Sudoku puzzles of varying difficulty. As programmers, however, our interest lies in developing generalized algorithms to solve any valid puzzle computationally.

The standard way to represent a Sudoku puzzle in code is as a nested array or matrix, where each inner array corresponds to a row in the grid. Blank cells are denoted by 0:

puzzle = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0], 
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],  
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
]

A solved puzzle replaces all the 0s with valid digits:

solution = [
    [5, 3, 4, 6, 7, 8, 9, 1, 2],
    [6, 7, 2, 1, 9, 5, 3, 4, 8],
    [1, 9, 8, 3, 4, 2, 5, 6, 7],
    [8, 5, 9, 7, 6, 1, 4, 2, 3], 
    [4, 2, 6, 8, 5, 3, 7, 9, 1],
    [7, 1, 3, 9, 2, 4, 8, 5, 6],
    [9, 6, 1, 5, 3, 7, 2, 8, 4],
    [2, 8, 7, 4, 1, 9, 6, 3, 5],
    [3, 4, 5, 2, 8, 6, 1, 7, 9]
]

Naïve First Approach

To ease back into the problem, my initial attempt focused on solving simpler puzzles using a basic deductive algorithm:

1. Iterate through each empty cell.
2. Determine the set of valid digits for that cell based on the values already present in its row, column, and 3×3 box.
3. If only one digit is possible, fill in the cell.
4. Repeat steps 1-3 until the grid is complete or no more cells can be filled.

This strategy leverages the most straightforward Sudoku rule – if a box, row, or column already contains a digit, that digit cannot appear elsewhere in the same grouping. By process of elimination, some cells will only have one permissible value.

Here‘s a barebones Python implementation:

class SudokuSolver:
    def __init__(self, puzzle):
        self.puzzle = puzzle

    def find_possibilities(self, row, col):
        used = set(self.get_row(row) + self.get_col(col) + self.get_box(row, col))
        return set(range(1, 10)) - used

    def solve(self):
        while True:
            changed = False
            for r, row in enumerate(self.puzzle):
                for c, val in enumerate(row):
                    if val == 0:
                        possible = self.find_possibilities(r, c) 
                        if len(possible) == 1:
                            self.puzzle[r][c] = possible.pop()
                            changed = True
            if not changed:
                break                        

    def get_row(self, r): return self.puzzle[r]
    def get_col(self, c): return [row[c] for row in self.puzzle]
    def get_box(self, r, c): ...

def sudoku(puzzle):    
    solver = SudokuSolver(puzzle)
    solver.solve()
    return solver.puzzle

This approach performed reasonably well on easy puzzles, but quickly hit a wall with more challenging ones. To understand why, let‘s analyze its efficiency.

The outer loop (while True) runs until no further changes can be made. In the worst case, this could mean visiting every cell, giving us O(n^2) iterations, where n is the grid size. Within each iteration, we inspect each unsolved cell again, adding another O(n^2) factor. Finally, find_possibilities() compares against the row, column, and box, each an O(n) operation.

All in all, we‘re looking at a time complexity of O(n^4) – quite inefficient for a 9×9 Sudoku with n = 81! Furthermore, this algorithm simply cannot handle puzzles where deduction alone doesn‘t suffice. We need a more robust technique.

Backtracking to the Rescue

The go-to algorithm for generalized Sudoku solving is backtracking, which emulates a depth-first search of the potential solution space. In essence:

1. Choose an empty cell.
2. Iterate through the possible digits for that cell.
3. Place a digit and recursively attempt to solve the modified grid.
4. If a solution is found, great! If not, undo that placement and try the next digit.
5. Repeat until the puzzle is solved or all possibilities are exhausted.

We can visualize this as exploring a solution tree, where each level represents a cell, each branch a digit, and each leaf a completed (but not necessarily correct) grid. The algorithm traverses this tree depth-first, backtracking whenever a branch proves fruitless.

Conceptually, it‘s quite intuitive – we‘re systematically trying all possible combinations until we find one that works or determine that no valid solution exists. The challenge lies in efficiently translating this to code.

Here‘s some pseudocode to illuminate the approach:

function solve_sudoku(puzzle):
    if puzzle is solved:
        return puzzle

    cell = find_empty_cell(puzzle)

    for digit in possible_digits(cell):
        place_digit(cell, digit)

        if is_valid(puzzle):
            result = solve_sudoku(puzzle)
            if result is not None:
                return result

        remove_digit(cell)

    return None

The key aspects are:

• The solve_sudoku function recursively calls itself after each digit placement to continue solving the modified grid.
• If a recursive call returns a valid solution, that result is propagated back up the call stack.
• If a recursive call returns None (indicating an invalid puzzle state), the algorithm backtracks by undoing the last placement and trying a different digit.

This logic can be directly translated into working Python code. I opted for an object-oriented implementation with separate Cell and Puzzle classes, but the core backtracking occurs in a solve method similar to the pseudocode.

After a few iterations of debugging (backtracking can get tricky!), I arrived at a complete solution capable of solving even the hardest Sudoku puzzles. Victory was mine at last!

Evaluating Efficiency

From a computational complexity standpoint, backtracking is a significant improvement over the naïve deduction approach. Since each empty cell expands the solution tree by a factor of up to 9, we can model the worst-case time complexity as O(9^m), where m is the number of missing digits. This is still exponential, but a marked upgrade over the O(n^4) of the basic algorithm.

Of course, backtracking is not the only way to attack Sudoku. Other common techniques include:

• Constraint propagation: Recursively applying the Sudoku rules to eliminate possibilities and infer cell values. More sophisticated than simple deduction.
• Exact cover: Transforming Sudoku into an exact cover problem and solving with Donald Knuth‘s Dancing Links algorithm. Highly efficient but more complex to implement.
• Stochastic search/optimization: Filling the grid randomly and iteratively refining via local search or evolutionary algorithms. Trades off guarantees for potential speed.

For a more comprehensive survey of Sudoku solving algorithms, I recommend the 2008 paper "A SAT-based Sudoku solver" by Tjark Weber, or the classic "Solving Every Sudoku Puzzle" by Peter Norvig.

Beyond Sudoku

Conquering Sudoku certainly provides a sense of intellectual satisfaction, but how relevant is it to practical software development? After all, most of us are not in the business of writing puzzle solvers.

I would argue that the value lies more in the problem-solving process than the specific algorithm. Decomposing a complex challenge into manageable steps, identifying edge cases, iterating on a suboptimal solution – these are all transferable skills that serve programmers well, regardless of domain.

Moreover, the ability to think algorithmically and analyze efficiency is crucial for writing performant, scalable code. While the vast majority of development work does not involve inSANE (Interview-SANE) dynamic programming brainteasers, a baseline competency in algorithmic reasoning goes a long way.

That said, an excessive fixation on abstract problem-solving ability, divorced from practical skills and experience, has unfortunately become a hallmark of many tech hiring processes. Whiteboard coding interviews that resemble algorithms class exams (with the added pressure of performing live) have proliferated, despite mounting evidence of their limited predictive value for on-the-job success.

As an interviewer, I‘ve seen firsthand how this approach can filter out talented candidates who simply haven‘t had the privilege of a traditional computer science education or extensive interviewing practice. It perpetuates the harmful notion that programming skill is innate rather than cultivated and disproportionately excludes already underrepresented groups.

When I reflect on my own journey, I‘m struck by how easily I could have been one of those rejected candidates, had my youthful Sudoku struggles permanently extinguished my coding aspirations. I was fortunate to find my way back to programming through the winding path of web development, where hands-on projects and practical abilities are emphasized over textbook knowledge.

In an alternate universe where puzzle-solving performance was the singular gatekeeper to a software career, I may have never found my way in.

A More Inclusive Future

My Sudoku odyssey has been a microcosm of the struggles faced by many aspiring programmers – initial discouragement, gradual mastery through perseverance, and eventual recognition of the flaws in how we evaluate and cultivate coding talent.

It‘s clear that traditional computer science education and hiring practices have deep-rooted accessibility issues. The prevailing "sink or swim" mentality and emphasis on abstract problem-solving weeds out potentially great programmers before they have a chance to develop. It‘s a systemic failure that we as an industry have a responsibility to address.

Bootcamps and other alternative education paths provide a promising model for a more inclusive tech workforce. By prioritizing hands-on experience, teamwork, and practical skills development, they demonstrate that programmers can be made, not just born.

On an individual level, those of us already established in our careers can push for change by advocating for more holistic hiring practices, serving as mentors, and supporting initiatives to expand access to coding education. We can share our own winding paths and false starts, demystifying the image of the effortless coding prodigy.

Looking ahead, I‘m hopeful that the rise of low-code/no-code tools, AI-assisted development, and other technological advancements will further democratize programming and chip away at the exclusionary culture. Our role as engineers is to build the future – let‘s make sure it‘s one where problem-solving ability is cultivated in all, not wielded as a barrier to entry.

In the end, writing a Sudoku solver is easy – solving the systemic issues in tech is the real challenge. Let‘s get to work!