スタックへの初期データの投入 (KATAMINOを解くプログラムを作成する)

★前回の記事

yucatio.hatenablog.com

スタックへデータを投入します。

スタックを使用するアルゴリズムについては以下の記事を参照してください。

yucatio.hatenablog.com

実装

フィールドと次に置くことができるピースをスタックへ投入します。 スタック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})
      })
    })
    // 追加ここまで
  },
}

ここまでで、スタックの内容は以下のようになっています。

f:id:yucatio:20190722090944p:plain

ここのままでも解けそうですが、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})  // 変更
      })
    })
  },
}

以上でスタックへの初期データの投入が完了しました。


★次回の記事

yucatio.hatenablog.com

★目次

yucatio.hatenablog.com