★前回の記事
スタックへデータを投入します。
スタックを使用するアルゴリズムについては以下の記事を参照してください。
実装
フィールドと次に置くことができるピースをスタックへ投入します。
スタックsolverStack
を定義します。解く対象のピースtargetPiece
の各スピンをスタックに投入します。
js/solver.js
const solver = { solverStack : [], // 追加 init : (targetPiece) => { let kataminoField = new Array(5).fill().map(() => ( new Array(targetPiece.length).fill(-1) } // 追加ここから solver.solverStack = [] targetPiece.forEach((pieceId) => { KATAMINO_ARR[pieceId].forEach((spin) => { solver.solverStack.push({kataminoField, spin}) }) }) // 追加ここまで }, }
ここまでで、スタックの内容は以下のようになっています。
ここのままでも解けそうですが、1つ問題点があります。例えば1番のピースの1番のスピンがフィールドに置けたとき、1番のピースはもうこれ以上置くことはできません。しかしピース番号が分からないため、1番のピース以外を次に置く候補としてスタックに入れることができません。
そこでピース番号pieceId
とまだ置かれていないピースの配列unPlacedPiece
をスタックに入れる情報に追加します。ピースをフィールドに置いた時に、置いたピースの番号をunPlacedPiece
から削除することで同じピースを重複して置くことを防ぎます。また、デバッグのために、spinId
もスタックに入れます(STEP2でspinId
も使用します)。
js/solver.js
const solver = { solverStack : [], init : (targetPiece) => { let kataminoField = new Array(5).fill().map(() => ( new Array(targetPiece.length).fill(-1) } solver.solverStack = [] targetPiece.forEach((pieceId) => { KATAMINO_ARR[pieceId].forEach((spin, spinId) => { // 変更 solver.solverStack.push({kataminoField, pieceId, spinId, spin, unPlacedPiece: targetPiece}) // 変更 }) }) }, }
ところで、スタックから取り出した後に、1番番号が小さい(左上の)空白を埋めるようにピースを置いてみるのでした。 毎回スタックから取り出すごとに計算するのも面倒なので、フィールドの状態ごとに計算してスタックに入れておくことにしましょう。
const solver = { solverStack : [], init : (targetPiece) => { let kataminoField = new Array(5).fill().map(() => ( new Array(targetPiece.length).fill(-1) } solver.solverStack = [] const minEmpty = {x:0, y:0} // 追加 targetPiece.forEach((pieceId) => { KATAMINO_ARR[pieceId].forEach((spin, spinId) => { solver.solverStack.push({kataminoField, minEmpty, pieceId, spinId, spin, unPlacedPiece: targetPiece}) // 変更 }) }) }, }
以上でスタックへの初期データの投入が完了しました。
★次回の記事
★目次