8クイーン

問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考

これの8クイーンをtypescriptで実装してみた。

・自分の頭であまり考えられてない
そんなに難しくないはずなのに、考えるのが面倒だと思ってしまう。
致命的な問題な気がする。

・意味をまとめる
元はpythonだからforとかで書かれてたが、someとかeveryで書き直すとだいぶ意味がわかりやすい。
パット見分かりづらい条件分岐は、ifにそのまま書くより一度変数に入れたほうが若干見やすいかも。

・その他
配列を渡して書き換えちゃってるのは良くない

// [start..end]の配列を作る
const range = (start: number, end: number) =>
  Array.from({ length: end - start }, (v, k) => k + start)

function noConflicts(board: number[], current: number): boolean {
  return range(0, current).every(i => {
    // trueならクイーンを置ける
    let horiCheck = board[i] != board[current]
    let diagCheck = current - i != Math.abs(board[current] - board[i])
    return horiCheck && diagCheck
  })
}

function rQueens(board: number[], current: number, size: number) {
  if (current == size) return true
  return range(0, size).some(i => {
    board[current] = i
    if (noConflicts(board, current)) {
      return rQueens(board, current + 1, size)
    }
  })
}

function nQueens(n) {
  let board = new Array(n).fill(-1)
  rQueens(board, 0, n)
  console.log(board)
}