Sudoku Logic: A Guide for Android Engineers

Sudoku is a classic logic-based puzzle that challenges both casual enthusiasts and seasoned programmers. Beyond entertainment, solving Sudoku programmatically can improve an engineer's problem-solving and algorithmic thinking. In this article, we explore two popular LeetCode challenges — Valid Sudoku and Sudoku Solver — along with efficient solutions in Kotlin, tailored for Android engineers.

---

1. Understanding Sudoku Rules

A Sudoku puzzle is a 9x9 grid divided into 3x3 sub-grids. The objective is to fill the grid so that:

1. Each row contains numbers 1-9 without repetition.
2. Each column contains numbers 1-9 without repetition.
3. Each 3x3 sub-grid contains numbers 1-9 without repetition.

---

Challenge 1: Valid Sudoku

Problem: Check whether a partially filled Sudoku board is valid, without requiring it to be solvable.

Kotlin Solution

fun isValidSudoku(board: Array<CharArray>): Boolean {
    val rows = Array(9) { mutableSetOf<Char>() }
    val cols = Array(9) { mutableSetOf<Char>() }
    val grids = Array(9) { mutableSetOf<Char>() }

    for (i in 0 until 9) {
        for (j in 0 until 9) {
            val num = board[i][j]
            if (num == '.') continue
            
            val gridIndex = (i / 3) * 3 + j / 3
            if (num in rows[i] || num in cols[j] || num in grids[gridIndex]) {
                return false
            }

            rows[i].add(num)
            cols[j].add(num)
            grids[gridIndex].add(num)
        }
    }
    return true
}

Explanation

1. Tracking Numbers:

   • Use three arrays of sets to store numbers seen in rows, columns, and sub-grids.
   • Each array has 9 sets (one for each row, column, or grid).

2. Grid Mapping:

   • Map each cell to its corresponding sub-grid using the formula:
     gridIndex = (i / 3) * 3 + j / 3.

3. Validation:

   • For every non-empty cell, check if the number already exists in the corresponding row, column, or grid. If so, return false.

4. Time Complexity:

   • $O(81)$: Iterating over the fixed 9x9 board.

5. Space Complexity:

   • $O(27)$: Using three arrays of 9 sets.

---

Challenge 2: Sudoku Solver

Problem: Write a program to solve a given Sudoku puzzle by filling empty cells.

Kotlin Solution

fun solveSudoku(board: Array<CharArray>) {
    solve(board)
}

private fun solve(board: Array<CharArray>): Boolean {
    for (row in 0 until 9) {
        for (col in 0 until 9) {
            if (board[row][col] == '.') {
                for (num in '1'..'9') {
                    if (isValidPlacement(board, row, col, num)) {
                        board[row][col] = num
                        if (solve(board)) return true
                        board[row][col] = '.' // Backtrack
                    }
                }
                return false // Trigger backtracking
            }
        }
    }
    return true // Puzzle is solved
}

private fun isValidPlacement(board: Array<CharArray>, row: Int, col: Int, num: Char): Boolean {
    for (i in 0 until 9) {
        if (board[row][i] == num || board[i][col] == num || 
            board[(row / 3) * 3 + i / 3][(col / 3) * 3 + i % 3] == num) {
            return false
        }
    }
    return true
}

Explanation

1. Backtracking Approach:

   • Identify the first empty cell ('.').
   • Try placing numbers from '1' to '9'.
   • Check if the placement is valid. If yes:
     • Place the number and proceed to the next empty cell recursively.
     • If the board cannot be solved with the current placement, backtrack by resetting the cell.

2. Validation:

   • Ensure the number does not conflict with the row, column, or 3x3 grid.

3. Time Complexity:

   • In the worst case, $O(9^m)$, where $m$ is the number of empty cells.

4. Space Complexity:

   • $O(m)$ for the recursion stack.

---

How Does This Relate to Android?

1. Logic Implementation:

   • The same backtracking and validation techniques can be applied to game development in Android (e.g., building a Sudoku app).

2. Data Structures:

   • Kotlin's Array and Set are essential in Android development for handling collections efficiently.

3. Performance Optimization:

   • Reducing space and time complexity is vital for smooth Android app performance.

4. UI Updates:

   • Integrate this logic with Jetpack Compose or RecyclerView to dynamically update the Sudoku board UI based on user interaction.

---

Conclusion

Mastering Sudoku logic teaches key programming concepts:

• Data Validation: Ensuring correctness in user input or data processing.
• Backtracking: A versatile approach for solving constraint-based problems.
• Efficiency: Balancing complexity with performance.

For Android engineers, these problems also highlight Kotlin's expressiveness and its suitability for crafting efficient algorithms.

---

Whether you are preparing for a coding interview or building a Sudoku app, these solutions provide a foundation to tackle complex challenges with confidence.