Eight queens

module eightQueens

def boardSize = 8

-- A partial solution is the column of the queen in each row placed so far.
-- A new queen is safe if no earlier queen shares its column or a diagonal.
def isSafe: (list(int), int) -> bool = { queens, col ->
  queens
    \reverse
    \zip(1..)
    \all { q, distance -> q != col and q != col - distance and q != col + distance }
}

def solve: list(int) -> #some(list(int)) | #noSolution = { queens ->
  if queens.length == boardSize then #some(queens)
  else
    rec tryColumns = {
      | [] -> #noSolution
      | [col, ...rest] ->
        if isSafe(queens, col) then
          match solve([...queens, col])
            | #some(solution) -> #some(solution)
            | #noSolution -> tryColumns(rest)
        else tryColumns(rest)
    }

    tryColumns((0..(boardSize - 1)) \toList)
}

def render: list(int) -> string = { queens ->
  queens
    \map { q -> (0..(boardSize - 1)) \map { c -> if c == q then "Q " else ". " } \String.join("") }
    \String.join("\n")
}

@entry
def main = {
  match solve([])
    | #some(queens) -> println(render(queens))
    | #noSolution -> println("No solution for a {boardSize}x{boardSize} board")
}

This program lives in the repository as examples/eightQueens.nyx.