Algorithms of Logic: Sudoku

Sudoku is more than a game—it's a perfect playground for computer science. When I set out to build **Simply Sudoku**, I wanted to ensure that every puzzle was generated on-device, 100% unique, and guaranteed to be solvable with pure logic. This required moving beyond simple random placement and into the realm of formal algorithmic design.

The Core: Recursive Backtracking

At the heart of the app is a recursive backtracking algorithm. Sudoku is essentially a **Constraint Satisfaction Problem (CSP)**. The rules are simple: no repeating numbers in a row, column, or 3x3 grid. However, the search space for a 9x9 grid is massive.

The backtracking approach works by attempting to place a number in a cell and then recursively trying to fill the rest of the board. If it hits a dead end (where no valid number can be placed), it "backtracks" and changes the previous number. To optimize this for mobile, I implemented **Bitmasking**. By representing the "used" numbers in each row and column as bits in an integer, the engine can check the validity of a move in constant time ($O(1)$), allowing it to solve or generate boards in milliseconds.

Generating the Challenge

Generating a board is actually more difficult than solving one. To create a high-quality user experience, the generation process follows a two-step "Reductionist" workflow. First, we generate a "Perfect Board"—a fully solved, valid Sudoku grid using our backtracking engine with randomized seeds to ensure variety.

Then, we start the removal phase. Simply picking numbers to delete isn't enough; we must ensure that the resulting puzzle has **exactly one unique solution**. After every number is removed, the engine runs a dual-path solver check. If the solver finds that removing a specific digit creates multiple possible ways to finish the board, that digit is put back, and we try another. This ensures that the player never feels cheated by an "unsolvable" or "ambiguous" puzzle.

UI/UX Challenges in Logic Games

Technical logic is only half the battle. On Android, providing a fluid input method for Sudoku is notoriously difficult. In keeping with the "Simply" philosophy, I avoided the standard "floating keypad" which often obscures the board. Instead, Simply Sudoku uses a reactive selector that highlights the active constraints (row, column, and block) to help the player's brain process the logic faster.

By sticking to native Kotlin and modern Jetpack Compose, I ensured that these heavy recursive operations never cause a "jank" in the UI thread. The result is a utility that feels as fast as a system-native tool while providing the deep mental workout Sudoku fans expect.

Looking Ahead: Optimization

While the current engine is fast, there is always room for more efficiency. In future updates, I'm exploring **Knuth’s Algorithm X** (Dancing Links) to handle even larger grid sizes. My goal remains consistent: providing the most performant, battery-friendly logic games in the Gloucester development scene.