n-queens problem

n-queens.js

const log = (...args) => {
  // console.log(...args)
  document.write(...args)
  document.write('<br />')
}

// get the print function (for printing the board)
const getPrint = (n) => (arr) => {
  const print = () => {
    let str = ''
    for (let i = 1; i <= n; i++) {
      for (let j = 1; j <= n; j++) {
        str += !!arr.find((o) => o.row === i && o.col === j) ? ' x' : ' o'
      }
      str += `<br />`
    }
    log(str)
  }

  print()
}

const head = (arr) => {
  return arr[0]
}

const tail = (arr) => {
  const [, ...a] = arr
  return a
}

const makePoint = ({ row, col }) => {
  return { row, col }
}

// check if 2 points attacking each other
const checkTwoPoint = (p1, p2) => {
  const { row: row1, col: col1 } = p1
  const { row: row2, col: col2 } = p2

  // check not attacking by same row or same col
  if (row1 === row2 || col1 === col2) {
    return false
  }

  // check not attacking by same diagonal line
  if (Math.abs(row1 - row2) === Math.abs(col1 - col2)) {
    return false
  }

  return true
}

// check if one point attacking any point in a list of points (assume list of points includes all points that not attacking each others)
const checkOnePointAndListPoint = (point, ls) => {
  if (ls.length === 0) {
    return true
  }

  return (
    checkTwoPoint(point, head(ls)) && checkOnePointAndListPoint(point, tail(ls))
  )
}
// check if a list of point is valid (no point attacking each others)
// const checkListPoint = (ls) => {
//   if (ls.length <= 1) {
//     return true
//   }
//   if (ls.length === 2) {
//     return checkTwoPoint(ls[0], ls[1])
//   }

//   return checkOnePointAndListPoint(car(ls), cdr(ls)) && checkListPoint(cdr(ls))
// }

const stackMaker = (printFn) => {
  const data = []
  return {
    push: (item) => {
      data.unshift(item)
      printFn(data)
    },
    remove: () => {
      const itemToRemove = data.shift()
      return itemToRemove
    },
    top: () => {
      return data[0]
    },
    listExceptTop: () => {
      return tail(data)
    },
    size: () => {
      return data.length
    },
  }
}

const queen = (n) => {
  const stack = stackMaker(getPrint(n))

  const back = () => {
    const isLastPointAtTheLastRow = () => {
      const lastPoint = stack.top()
      return lastPoint.row === n
    }

    if (!isLastPointAtTheLastRow()) {
      const lastPoint = stack.remove()
      place({ row: lastPoint.row + 1, col: lastPoint.col })
    } else {
      stack.remove()
      back()
    }
  }

  const checkValidBoard = () => {
    const lastPoint = stack.top()
    const remainder = stack.listExceptTop()
    const isValid = checkOnePointAndListPoint(lastPoint, remainder)

    if (isValid) {
      place({ row: 1, col: lastPoint.col + 1 })
    } else {
      back()
    }
  }

  const place = ({ row, col }) => {
    if (stack.size() === n) {
      log('done ')
      return 'done'
    }
    const point = makePoint({ col, row })
    stack.push(point)
    checkValidBoard()
  }

  place({ row: 1, col: 1 })
}

queen(4)