The Sudoku Solver Problem

Problem statement

Write a program to verify whether an 9 x 9 2-dimensional array that represents a partially completed Sudoku is valid. Specifically, check that no row, column or 3 x 3 sub-array contains duplicates.

Here is an example of a partially completed valid Sudoku board (eq. your program should return true for this board):

An example of a partially solved valid Sudoku board

NOTE: A 0 value in the given Sudoku board indicates that entry is blank and every other entry is in 1 - 9.

Solution

Here is the actual code of the algorithm that implements a solution to verify whether a partially completed Sudoku board is valid or not:

/// Verifies whether Sudoku board is valid or not.
///
/// - Parameter: A instance of Sudoku board.
func valid(_ board: [[Int]]) -> Bool {
    // Prepare state of the algorithm
    let xx = board.count, size = sqrt(board.count)
    // Verify an every row has unique numbers only
    for rx in 0...xx - 1 {
        // Inspect the specified board slice
        let next = unique(board, (rx, rx + 1, 0, xx))
        // Should we evaluate the next slice? 
        if next == false { return false }
    }
    // Verify an every column has unique numbers only
    for cx in 0...xx - 1 {
        // Inspect the specified board slice
        let next = unique(board, (0, xx, cx, cx + 1))
        // Should we evaluate the next slice?
        if next == false { return false }
    }
    // Verify an every region (N x N) has unique numbers only
    for i in 0...size - 1 {
        for j in 0...size - 1 {
            // Calculate row coordinates
            let crx = size * i, nrx = crx + size
            // Calculate column coordinates
            let ccx = size * j, ncx = ccx + size
            // Inspect the specified board slice
            let next = unique(board, (crx, nrx, ccx, ncx))
            // Should we evaluate the next slice?
            if next == false { return false }
        }
    }
    // Here is the answer and it looks like the board is valid
    return true
}

Following is a helper function that implements an algorithm to verify whether or not the specified slice of Sudoku board has unique numbers only.

This helper leverages the fact that Sudoku board is symmetric and therefore every constraint to be verified (eq. row, column or 3 x 3 grid) can be represented as a flat array with 9 + 1 elements (to account for empty cells with 0 value):

/// A slice of Sudoku board.
typealias BoardSlice = (left: Int, right: Int, top: Int, bottom: Int)

/// Verifies whether the given slice has unique elements only.
///
/// - Parameter board: An instance of Sudoku board.
/// - Parameter slice: An instance of Soduku board's slice to validate.
func unique(_ board: [[Int]], _ slice: BoardSlice) -> Bool {
    // Prepare state of the validator
    var nn = [Bool](repeating: false, count: board.count + 1)
    // Evaluate board's slice, eq. left-to-right
    for i in slice.left...slice.right - 1 {
        // Evaluate board's slice, eq. top-to-bottom
        for j in slice.top...slice.bottom - 1 {
            // Query board's item number and its value 
            let cx = board[i][j], xv = nn[cx]
            // Seems this slice has a duplicate
            if cx != 0 && xv == true { return false }
            // Mark this non-empty entry as already seen
            nn[cx] = true
        }
    }
    // Seems this slice has only unique numbers
    return true
}

Following is an example that the code performs as advertised and establish a baseline for any improvement work in the future:

The Sudoku solver problem test assertions

Bits & pieces

This coding challenge makes use of an simple and effective technique to solve the large problem as a set of smaller problems calling to a special unique helper function to verify either a row, column or 3 x 3 grid.

Lets get started!

The first statement initializes xx and size variables that are used to represent either total or partial number of elements to process. Such that, xx represents number of elements to verify in every row and column cases and size to represent a partial number of elements in every nested grid:

// Prepare state of the algorithm
let xx = board.count, size = sqrt(board.count)

Here is an example how these variables would look like in case of a 9 x 9 board:

Number of elements

Next snippet, is a loop to inspect each row in the original Sudoku board, one-by-one and verify that all rows have unique elements only. We use next variable as a flag to break out from the loop when the current row does not meet the original constraint (eq. all rows must have unique numbers):

// Verify an every row has unique numbers only
for rx in 0...xx - 1 {
    // Inspect the specified board slice
    let next = unique(board, (rx, rx + 1, 0, xx))
    // Should we evaluate the next slice? 
    if next == false { return false }
}

Here is an example how the snippet above would inspect each and every row of a 9 x 9 Sudoku board:

Inspect each and every row of a Sudoku board

Following snippet, is a loop to inspect each column in the original Sudoku board, one-by-one and verify that all columns have unique elements only. Again, we use next variable as a flag to break out from the loop when the current column does not meet the original constraint (eq. all columns must have unique numbers):

// Verify an every column has unique numbers only
for cx in 0...xx - 1 {
    // Inspect the specified board slice
    let next = unique(board, (0, xx, cx, cx + 1))
    // Should we evaluate the next slice?
    if next == false { return false }
}

Here is an example how the snippet above would inspect each and every column of a 9 x 9 Sudoku board:

Inspect each and every column of a Sudoku board

This snippet, contains two loops (one nested into the other) and is used to inspect each 3 x 3 nested grid in the original Sudoku board, one-by-one and verify that all nested grids have unique elements only. Similar to previous snippets, we use next variable as a flag to break out from the loop when the current grid does not meet the original constraint (eq. all nested grids must have unique numbers):

// Verify an every region (N x N) has unique numbers only
for i in 0...size - 1 {
    for j in 0...size - 1 {
        // Calculate row coordinates
        let crx = size * i, nrx = crx + size
        // Calculate column coordinates
        let ccx = size * j, ncx = ccx + size
        // Inspect the specified board slice
        let next = unique(board, (crx, nrx, ccx, ncx))
        // Should we evaluate the next slice?
        if next == false { return false }
    }
}

Here is an example how the snippet above would inspect each and every 3 x 3 sub-grid of a 9 x 9 Sudoku board:

Inspect each and every 3 x 3 sub-grid of a Sudoku board

Finally, the last statement returns true, since the given Sudoku board has passed all validations we can claim that the boards meets all constraints and is a valid partially completed Soduku board:

// Here is the answer and it looks like the board is valid
return true

That’s all folks! 🤓

Here is a Swift playground for this article at Github: The Sudoku Solver Problem.