# The Sudoku Solver Problem

20 Sep 2018### 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*):

**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:

### 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:

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:

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:

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:

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.