n-queens.js

const drawBoard = (queens = []) => {
  let field = ''

  queens.forEach((queenColumn) => {
    queens.forEach((_, column) => {
      field += column === queenColumn ? 'Q' : '.'
    })
    field += '\n'
  })

  return field
}

const getRowSafePosition = (map, row, lastCheckedPosition = 0) => {
  for (let column = lastCheckedPosition + 1; column < map.columns.length; column++) {
    if (
      !map.columns[column] &&
      !map.rightDiag[row + column] &&
      !map.leftDiag[row - column + map.columns.length - 1]
    ) {
      return column
    }
  }

  return -1
}

const updateMap = (map, row, column, occupied = true) => {
  map.columns[column] = occupied
  map.rightDiag[row + column] = occupied
  map.leftDiag[row - column + map.columns.length - 1] = occupied
}

const backtrackSolveNQueens = (n, fixedQueen) => {
  if (n === 1) {
    return 'Q\n'
  }

  const fixedRow = fixedQueen.row
  const startQueens = new Array(n)
    .fill(-1)
    .map((x, index) => (index === fixedRow ? fixedQueen.col : x))

  const map = {
    columns: new Array(n).fill(false),
    rightDiag: Array.from(new Array(n * 2).fill(false)),
    leftDiag: Array.from(new Array(n * 2).fill(false)),
  }

  updateMap(map, fixedRow, fixedQueen.col)

  const queens = startQueens.slice()
  const firstLine = fixedRow ? 0 : 1
  const lastLine = fixedRow === queens.length - 1 ? queens.length - 2 : queens.length - 1
  let isFirstIteration = true

  let topRow = firstLine
  // let operations = 0

  while (
    (isFirstIteration || queens[firstLine] !== -1 || queens[lastLine] !== -1) &&
    topRow <= lastLine
    ) {
    isFirstIteration = false

    // top operation
    // operations++
    const currentTopColumn = queens[topRow]

    const nextTopColumn = getRowSafePosition(
      map,
      topRow,
      currentTopColumn, // currentPosition === -1 ? 0 : currentPosition,
    )

    if (currentTopColumn !== -1) {
      updateMap(map, topRow, currentTopColumn, false)
    }

    if (nextTopColumn !== -1) {
      updateMap(map, topRow, nextTopColumn)
    }

    queens[topRow] = nextTopColumn

    if (nextTopColumn === -1) {
      topRow--
      if (topRow === fixedRow) {
        topRow--
      }
    } else {
      topRow++
      if (topRow === fixedRow) {
        topRow++
      }
    }
  }

  return drawBoard(queens, fixedQueen)
}

// Systematic search
const addQueen = (map, row, column) => {
  map.rows[row] = column
  map.columns[column] = row
  const rightDiag = map.rightDiag[row + column]
  const leftDiag = map.leftDiag[row - column + map.rows.length - 1]

  rightDiag.push(row)
  leftDiag.push(row)

  const rightDiagQueens = map.rightDiag[row + column].length - 1
  const leftDiagQueens = map.leftDiag[row - column + map.rows.length - 1].length - 1

  rightDiag.forEach((attackRow) => {
    const attackColumn = map.rows[attackRow]
    const leftAttack = map.leftDiag[attackRow - attackColumn + map.rows.length - 1].length - 1
    map.attacks[attackRow] = rightDiagQueens + leftAttack
  })

  leftDiag.forEach((attackRow) => {
    const attackColumn = map.rows[attackRow]
    const rightAttack = map.rightDiag[attackRow + attackColumn].length - 1
    map.attacks[attackRow] = rightAttack + leftDiagQueens
  })

  map.attackSum = map.attacks.reduce((a, b) => a + b)
}

const removeQueen = (map, row) => {
  const column = map.rows[row]

  map.rows[row] = -1
  map.columns[column] = -1

  map.rightDiag[row + column] = map.rightDiag[row + column].filter((r) => r !== row)
  map.leftDiag[row - column + map.rows.length - 1] = map.leftDiag[
  row - column + map.rows.length - 1
    ].filter((r) => r !== row)

  const rightDiag = map.rightDiag[row + column]
  const leftDiag = map.leftDiag[row - column + map.rows.length - 1]

  const rightDiagQueens = map.rightDiag[row + column].length - 1
  const leftDiagQueens = map.leftDiag[row - column + map.rows.length - 1].length - 1

  rightDiag.forEach((attackRow) => {
    const attackColumn = map.rows[attackRow]
    const leftAttack = map.leftDiag[attackRow - attackColumn + map.rows.length - 1].length - 1
    map.attacks[attackRow] = rightDiagQueens + leftAttack
  })

  leftDiag.forEach((attackRow) => {
    const attackColumn = map.rows[attackRow]
    const rightAttack = map.rightDiag[attackRow + attackColumn].length - 1
    map.attacks[attackRow] = rightAttack + leftDiagQueens
  })

  map.attackSum = map.attacks.reduce((a, b) => a + b)
}

const swapRow = (map, rowA, rowB) => {
  const colA = map.rows[rowA]
  const colB = map.rows[rowB]

  removeQueen(map, rowA)
  removeQueen(map, rowB)
  addQueen(map, rowA, colB)
  addQueen(map, rowB, colA)
}

const isSwapOk = (map, rowA, rowB, swapHistory) => {
  const colA = map.rows[rowA]
  const colB = map.rows[rowB]
  const emptySwaps = swapHistory.filter((x) => x.length === 0).length

  if (colA === -1) {
    return false
  }

  const prevDiagonals = {
    rightA: rowA + colA,
    leftA: rowA - colA + map.rows.length - 1,
    rightB: rowB + colB,
    leftB: rowB - colB + map.rows.length - 1,
  }

  const newDiagonals = {
    rightA: rowA + colB,
    leftA: rowA - colB + map.rows.length - 1,
    rightB: rowB + colA,
    leftB: rowB - colA + map.rows.length - 1,
  }

  const prevAttacks =
    map.rightDiag[prevDiagonals.rightA].length +
    map.rightDiag[prevDiagonals.rightB].length +
    map.leftDiag[prevDiagonals.leftA].length +
    map.leftDiag[prevDiagonals.leftB].length -
    4

  const newAttacks =
    map.rightDiag[newDiagonals.rightA].length +
    map.rightDiag[newDiagonals.rightB].length +
    map.leftDiag[newDiagonals.leftA].length +
    map.leftDiag[newDiagonals.leftB].length

  if (newAttacks >= prevAttacks + emptySwaps) {
    return false
  }

  let isRowsSelfAttacked = false

  if (map.rightDiag[newDiagonals.rightA].length >= 1) {
    isRowsSelfAttacked =
      map.rightDiag[newDiagonals.rightA].filter((row) => {
        const col = map.rows[row]
        return map.leftDiag[row - col + map.rows.length - 1].length === 1
      }).length >= 2
  }

  if (map.rightDiag[newDiagonals.rightB].length >= 1 && !isRowsSelfAttacked) {
    isRowsSelfAttacked =
      map.rightDiag[newDiagonals.rightB].filter((row) => {
        const col = map.rows[row]
        return map.leftDiag[row - col + map.rows.length - 1].length === 1
      }).length >= 2
  }

  if (map.leftDiag[newDiagonals.leftA].length >= 1 && !isRowsSelfAttacked) {
    isRowsSelfAttacked =
      map.leftDiag[newDiagonals.leftA].filter((row) => {
        const col = map.rows[row]
        return map.rightDiag[row + col].length === 1
      }).length >= 2
  }

  if (map.leftDiag[newDiagonals.leftB].length >= 1 && !isRowsSelfAttacked) {
    isRowsSelfAttacked =
      map.leftDiag[newDiagonals.leftB].filter((row) => {
        const col = map.rows[row]
        return map.rightDiag[row + col].length === 1
      }).length >= 2
  }

  return !isRowsSelfAttacked
}

const findSwap = (map, swapHistory, fixedRow) => {
  const attackValues = Array.from(new Set(map.attacks)).sort((a, b) => b - a)

  const rowsByAttackValues = attackValues.map((attacks) =>
    map.attacks.reduce((acc, rowAttacks, row) => {
      if (rowAttacks === attacks && row !== fixedRow) {
        acc.push(row)
      }
      return acc
    }, []),
  )

  for (const attackedRows of rowsByAttackValues) {
    for (const rowA of attackedRows) {
      for (const rowB of map.columns.filter((x) => x !== -1)) {
        const isPairExcluded = swapHistory.some(
          ([a, b]) => (a === rowA && b === rowB) || (b === rowA && a === rowB),
        )
        if (rowB !== rowA && rowB !== fixedRow && !isPairExcluded && map.attackSum !== 0) {
          if (isSwapOk(map, rowA, rowB, swapHistory)) {
            swapRow(map, rowA, rowB)
            return [rowA, rowB].sort()
          }
        }
      }
    }
  }

  return []
}

const putRowOnTheBestPosition = (map, fixedRow) => {
  const row = map.rows.indexOf(-1)
  const rowAttacks = new Array(map.rows.length).fill(Infinity).map((x, column) => {
    if (map.columns[column] !== -1) {
      return x
    }

    const rightDiagAttacks = map.rightDiag[row + column].length
    const leftDiagAttacks = map.leftDiag[row - column + map.rows.length - 1].length

    return rightDiagAttacks + leftDiagAttacks
  })

  const minAttackValue = Math.min(...rowAttacks)
  const minAttackColumn = rowAttacks.indexOf(minAttackValue)

  addQueen(map, row, minAttackColumn)

  if (minAttackValue > 0) {
    findSwap(map, [], fixedRow)
  }
}

const solveNQueens = (n, fixedQueen) => {
  // basic setup

  const fixedRow = fixedQueen.row
  const fixedCol = fixedQueen.col
  const maxChecksAmount = n * n * 1000

  const map = {
    rows: new Array(n).fill(-1),
    columns: new Array(n).fill(-1),
    rightDiag: new Array(n * 2).fill(1).map(() => []),
    leftDiag: new Array(n * 2).fill(1).map(() => []),
    attacks: new Array(n).fill(0),
    attackSum: 0,
  }

  addQueen(map, fixedRow, fixedCol)

  // generate field
  for (let row = 0; row < n; row++) {
    if (row === fixedRow) {
      // eslint-disable-next-line no-continue
      continue
    }

    putRowOnTheBestPosition(map, fixedRow)
  }


  // balancing map
  let checks = 0
  const swapHistory = []

  while (map.attackSum !== 0 && checks < maxChecksAmount) {
    checks++

    const swapped = findSwap(map, swapHistory, fixedRow)

    swapHistory.push(swapped)
    if (swapHistory.length > 16) {
      swapHistory.splice(0, 1)
    }
  }

  if (map.attackSum) {
    return ''
  }

  return drawBoard(map.rows)
}

console.time('solveNQueens')
solveNQueens(1000, { row: 1, col: 2 })
console.timeEnd('solveNQueens')