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.