# Recursion tips and tricks

n/a

Make a function that translates 2D position on board into 1D position in the vector, e.g:
`def idx(x: Int, y: Int): Int = x + y * 9`
`x` is `>= 0` and `<= 8`. Same goes for `y`.

n/a

Recursively check? Didn’t you mean recursively fill? Checking is not needed to be done recursively.

First let’s define helper functions:

``````// convert from coordinates to index
def idx(x: Int, y: Int): Int = x + y * 9
// convert from index to coordinates
def coords(idx: Int): (Int, Int) = (idx % 9, idx / 9)
``````

Then if you have picked a value on position `(x, y)` and want to examine if board is still valid use:

``````// check if element on position (x, y) doesn't conflict with others
def checkElement(x: Int, y: Int): Boolean = {
val correct = true
val used = Array.ofDim[Boolean](9)
(0 to 8).foreach(i => used(i) = false)
for (x <- 0 to 8) { // check horizontal line
val elem = board(idx(x, y))
correct &= !used(elem)
used(elem) = true
}
(0 to 8).foreach(i => used(i) = false)
for (y <- 0 to 8) { // check vertical line
val elem = board(idx(x, y))
correct &= !used(elem)
used(elem) = true
}
(0 to 8).foreach(i => used(i) = false)
for { // check 3x3 tile
xp <- (x / 3 * 3) to (x / 3 * 3) + 2)
yp <- (y / 3 * 3) to (y / 3 * 3) + 2)
} {
val elem = board(idx(xp, yp))
correct &= !used(elem)
used(elem) = true
}
correct
}
``````

Picking next elemets can be done recursively, e.g:

``````val board = Array.fill(9 * 9)(0.toByte)
// I guess this function is totally wrong, but at least it's recursive :)
def solve() = {
if (board.nonFull) {
val (x, y) = pickNextElem()
for (value <- 1 to 9) {
board(idx(x, y)) = value
if (checkElement(x, y)) {
solve()
}
}
board(idx(x, y)) = 0
}
}
``````

Disclaimer: all the code is totally untested.