JavaScript:N-Queensを関数で解く

[エイト・クイーンの JavaScript 解法 (Eight queens puzzle)](https://qiita.com/oosha/items/0f2782cf145b5004db8c)を読んで、既に確定した配列から次候補を生成してつなげていくやり方が、 [JavaScript:配列の順列と組み合わせ](https://qiita.com/ttatsf/items/200fe1ba765108ba502f) でやったのと同じだなと思ったので、次候補を作るところをそれっぽくなるように置き換えてみました。

クイーンの位置は、n=8の場合```[0,1,2,3,4,5,6,7]``` のように各index行の列位置を0~7の数字で表しています。

```js:
//確定配列から次候補にならない(確定Qの効き筋で新しいQが置けない)場所の配列を求める関数
const nextBadCols = pres => 
  pres.flatMap((e, i, ar)=>[ e, e-(ar.length-i), e+(ar.length-i)]);

//nと確定配列から次候補の配列を求める関数
const nextGoodCols = n => pres =>
  [...Array(n).keys()].filter(e=>!nextBadCols(pres).includes(e));

//再帰的にQの位置の配列の配列を求める関数
const innerQ = n => k => pres =>
  (k===0)? [pres]
  : nextGoodCols(n)(pres).flatMap(e=>[...innerQ(n)(k-1)([...pres,e])]);

//nからN-Queensの解を全て求める関数
const nQueens = n =>innerQ(n)(n)([]);
```
```nQueens(8)``` とやると解が92個ずらっと返ってきます。

```innerQ```の引数は クイーンの総数を n 、未確定のクイーンの数を k 、既に確定したクイーンの位置の配列を pres ということにしてます。
次候補からひとつを確定配列の最後部に加える、というのを再帰的に繰り返し、n個並べられたら探査成功、その前に次候補がなくなったら探査失敗という流れです。
次候補は ```nextGoodCols``` で求めます。0 から n-1 までの整数のうち```nextBadCols```に含まれてないものということです。
```nextBadCols```では確定配列 pres から 次の行でのクイーンの効き筋を求めます。簡単にするため範囲外も重複もokということにしてます。
 
実は```innerQ```には再帰の終了条件がふたつある、というのが肝です。

+ k===0 なら 探査成功。返り値は [pres]
+ k>0 かつ nextGoodCols(n)(pres)が 空の配列 [ ] なら 探査失敗。返り値は [ ]

[ ] に何をmap(またはflatMap)しても [ ] 、というのを利用しています。
そんな大事なことは明示しろ!と怒られそうですね。ちゃんと明示して書くとこんな感じ:

```js:
const innerQ = n => k => pres =>{
  if(k===0) return [pres];
  const xs = nextGoodCols(n)(pres);
  return (xs.length === 0 )? []
    : xs.flatMap( e=>[ ...innerQ( n )( k-1 )( [...pres,e] ) ] );
};
```


# nQueens(4)を例に
項書き換え的に何が起きているか見ていきます。

※ .flatMap( hoge )は、適宜 .map( hoge ).flat()に置き換えています。
※ 見やすくするためにちょっとはしょってるところがあります。

nQueens(4) から始めて、順次、関数を適用して変形していきます。

```js:
nQueens(4)
//const nQueens = n =>innerQ(n)(n)([]) を適用
innerQ(4)(4)([])
// k>0なので
//const innerQ = n => k => pres => 
//  nextGoodCols(n)(pres).flatMap(e=>[...innerQ(n)(k-1)([...pres,e])])
nextGoodCols(4)([]).flatMap(e=>[...innerQ(4)(3)([e])])
//nextGoodCols(4)([])
//=>[0,1,2,3].filter(e=>!nextBadCols([]).includes(e))
//=>[0,1,2,3].filter(e=>![].flatMap((e, i, ar)=>[ e, e-(ar.length-i), e+(ar.length-i)]).includes(e))
//=>[0,1,2,3].filter(e=>![].includes(e))
//=>[0,1,2,3]
[0,1,2,3].flatMap(e=>[...innerQ(4)(3)([e])])
//=>[0,1,2,3].map(e=>[...innerQ(4)(3)([e])]).flat()
[ innerQ(4)(3)([0])
  ,innerQ(4)(3)([1])
  ,innerQ(4)(3)([2])
  ,innerQ(4)(3)([3])
].flat()
```
flat()がかかっていますが、四つの要素の配列になりました。
この先長くなるので、それぞれ個別に追っていきます。
## 最初の要素：

```js:
innerQ(4)(3)([0])

nextGoodCols(4)([0]).flatMap(e=>[...innerQ(4)(2)([0,e])])

[2,3].flatMap(e=>[...innerQ(4)(2)([0,e])])

[ innerQ(4)(2)([0,2])
  ,innerQ(4)(2)([0,3])
].flat()

[ nextGoodCols(4)([0,2]).flatMap(e=>[...innerQ(4)(1)([0,2,e])])
  ,nextGoodCols(4)([0,3]).flatMap(e=>[...innerQ(4)(1)([0,3,e])])
].flat()

[ [].flatMap(e=>[...innerQ(4)(1)([0,2,e])])
  ,[1].flatMap(e=>[...innerQ(4)(1)([0,3,e])])
].flat()

[ []
  ,[ innerQ(4)(1)([0,3,1]) ].flat()
].flat()

[ []
  ,[ nextGoodCols(4)([0,3,1]).flatMap(e=>[...innerQ(4)(0)([0,3,1,e])]) ].flat()
].flat()

[ []
  ,[ [].flatMap(e=>[...innerQ(4)(1)([0,3,1,e])]) ].flat()
].flat()

[ []
  ,[ [] ].flat()
].flat()

[ []
  ,[]
].flat()

[]
```
空の配列になってしまいました。
## 二番目の要素：

```js:
innerQ(4)(3)([1])

nextGoodCols(4)([1]).flatMap(e=>[...innerQ(4)(2)([1,e])])

[3].flatMap(e=>[...innerQ(4)(2)([1,e])])

[ innerQ(4)(2)([1,3]) ].flat()

[ nextGoodCols(4)([1,3]).flatMap(e=>[...innerQ(4)(1)([1,3,e])]) ].flat()

[ [0].flatMap(e=>[...innerQ(4)(1)([1,3,e])]) ].flat()

[ [ innerQ(4)(1)([1,3,0]) ].flat() ].flat()

[ [ nextGoodCols(4)([1,3,0]).flatMap(e=>[...innerQ(4)(0)([1,3,0,e])]) ].flat() ].flat()

[ [ [2].flatMap(e=>[...innerQ(4)(0)([1,3,0,e])]) ].flat() ].flat()

[ [ [ innerQ(4)(0)([1,3,0,2]) ].flat() ].flat() ].flat()

[ [ [ [[1,3,0,2]] ].flat() ].flat() ].flat()

[[1,3,0,2]]
```
解がひとつ出ました。
## 三番目の要素：

```js:
innerQ(4)(3)([2])

nextGoodCols(4)([2]).flatMap(e=>[...innerQ(4)(2)([2,e])])

[0].flatMap(e=>[...innerQ(4)(2)([2,e])])

[ innerQ(4)(2)([2,0]) ].flat()

[ nextGoodCols(4)([2,0]).flatMap(e=>[...innerQ(4)(1)([2,0,e])]) ].flat()

[ [3].flatMap(e=>[...innerQ(4)(1)([2,0,e])]) ].flat()

[ [ innerQ(4)(1)([2,0,3]) ].flat() ].flat()

[ [ nextGoodCols(4)([2,0,3]).flatMap(e=>[...innerQ(4)(0)([2,0,3,e])]) ].flat() ].flat()

[ [ [1].flatMap(e=>[...innerQ(4)(0)([2,0,3,e])]) ].flat() ].flat()

[ [ [ innerQ(4)(0)([2,0,3,1]) ].flat() ].flat() ].flat()

[ [ [ [[2,0,3,1]] ].flat() ].flat() ].flat()

[[2,0,3,1]]
```
これも解がひとつ出ました。
## 最後の要素：

```js:
innerQ(4)(3)([3])

nextGoodCols(4)([3]).flatMap(e=>[...innerQ(4)(2)([3,e])])

[0,1].flatMap(e=>[...innerQ(4)(2)([3,e])])

[ innerQ(4)(2)([3,0])
  ,innerQ(4)(2)([3,1])
].flat()

[ nextGoodCols(4)([3,0]).flatMap(e=>[...innerQ(4)(1)([3,0,e])])
  ,nextGoodCols(4)([3,1]).flatMap(e=>[...innerQ(4)(1)([3,1,e])])
].flat()

[ [2].flatMap(e=>[...innerQ(4)(1)([3,0,e])])
  ,[].flatMap(e=>[...innerQ(4)(1)([3,1,e])])
].flat()

[ [ innerQ(4)(1)([3,0,2]) ].flat()
  ,[]
].flat()

[ [ nextGoodCols(4)([3,0,2]).flatMap(e=>[...innerQ(4)(0)([3,0,2,e])]) ].flat()
  ,[]
].flat()

[ [ [].flatMap(e=>[...innerQ(4)(0)([3,0,2,e])]) ].flat()
  ,[]
].flat()

[ [ [] ].flat()
  ,[]
].flat()

[ []
  ,[]
].flat()

[]
```
空の配列になりました。
## まとめて：
この四つの結果を元の配列に適用します。

```js:
[ innerQ(4)(3)([0])
  ,innerQ(4)(3)([1])
  ,innerQ(4)(3)([2])
  ,innerQ(4)(3)([3])
].flat()

[ []
  ,[[1,3,0,2]]
  ,[[2,0,3,1]]
  ,[]
].flat()

[ [1,3,0,2]
  ,[2,0,3,1]
]
```
flat()で空の配列が消えて、解がふたつ残りました。