エイト・クイーンの JavaScript 解法 (Eight queens puzzle)を読んで、既に確定した配列から次候補を生成してつなげていくやり方が、 JavaScript:配列の順列と組み合わせ でやったのと同じだなと思ったので、次候補を作るところをそれっぽくなるように置き換えてみました。
クイーンの位置は、n=8の場合[0,1,2,3,4,5,6,7] のように各index行の列位置を0~7の数字で表しています。
//確定配列から次候補にならない(確定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)しても [ ] 、というのを利用しています。
そんな大事なことは明示しろ!と怒られそうですね。ちゃんと明示して書くとこんな感じ:
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) から始めて、順次、関数を適用して変形していきます。
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()がかかっていますが、四つの要素の配列になりました。
この先長くなるので、それぞれ個別に追っていきます。
最初の要素：
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()
[]
空の配列になってしまいました。
二番目の要素：
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]]
解がひとつ出ました。
三番目の要素：
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]]
これも解がひとつ出ました。
最後の要素：
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()
[]
空の配列になりました。
まとめて：
この四つの結果を元の配列に適用します。
[ 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()で空の配列が消えて、解がふたつ残りました。