37日目(01-28-2021)

今日は個人学習の日です!今までのプリントをブラウズしました.特にNQueenでは大きな進歩がありました.友达の提案を通じて、多くのことを最適化して、またいくつかの問題を見つけて、テストの例を通じて20秒近くかかって、今は1秒余りか1秒未満で合格しました.何日か考えたNQueen...私も飽きた.しかし、私の知っている限りでは、さらに減らす方法はありますが、今まで、私の実力はまだ足りないようです.それは参考文献を参考にしてください
大きな改善があった.まず方法の改善です.まず、Queenの衝突チェック方法は、まず行、列、対角線、逆対角線の4つの衝突チェック方法を実現し、それからすべて加算して、最終的にQueen衝突を発生させることを説明します.行、列の競合チェック方法は、私が初めて作成したときに最も効果的な方法となり、二度と進展しませんでした.しかし、対角線、逆対角線は私が初めて書いたコードが非常に効率的ではないことを感じさせます.
まず対角線を探す方法を説明します.

絵はちょっと複雑ですが.例えば上に4 x 4板があり、1は上馬の状態0は下馬の状態です.回路基板を拡張したい場合は、(3,1)のインデックスから1行目の対角線に到達したカラム(COL)インデックスは4です.カラムインデックス4に到達する対角線上のプレート上のすべての座標から、(3,1)(2,2)(1,3)が見られ、ローインデックス+カラムインデックスは同じである.
最初は、1が存在する点の行と列の値を加算し、対角線衝突を比較的にチェックする2つの繰り返し文を作成しました.しかし、この方式は効率が低く、演算量が大きい.
友達からのヒントで、新しい方法で解答しました.

これは簡単な方法です.対角線を引くときに伸びる板の最大列の値は、行長+列長です.上の4 x 4板を基準に6ですが、ご覧のように0(0,0)と6(3,3)は対角線ではありません.最終的には、最初の行の1行目から5行目をチェックするだけです.
コードで説明します.

SlashConflictAt: function (SlashColumnIndexAtFirstRow) {
  let len = this.get('n')
  if (SlashColumnIndexAtFirstRow === 0 || SlashColumnIndexAtFirstRow === (len- 1) * 2) {
     return false;
  }
  let row = 0;
  let col = SlashColumnIndexAtFirstRow;
  let count = 0;
  while (row !== len) {
    if (this._isInBounds(row, col)) { // 좌표가 유효한 좌표인지?
      count += this.get(row)[col];
      if (count >= 2) {
         return true;
      }
    }
     row += 1;
     col -= 1;
   }
    return false; // fixme
   }

(貼り付け中にスペルが悪い.)
簡単に1行目のカラムインデックスから始まり、row+1 col-1、1がある場合count、countが2を超えると競合するためtrueを返します.この方法では0から行列までの和の最大値をパラメータとして回路基板全体を調べることができる.このようにして、反スラッシュも同様の機能を実現した.だから複雑さは少し減った.
解決策を探す方法はどのように実現されていますか.

findQueensSolution = function (n) {
  const solution = new Board({n: n}); // fixme
  let makeAsolution = (row) => {
    if (row > n - 1) {
      return true;
    }

    for (let i = 0; i < n; i += 1) {
      solution.togglePiece(row, i);
      if (!solution.hasAnyQueenConflictsOn(row, i)) {
        let result = makeAsolution(row + 1);
        if (result) {
          return true;
        }
      }
      solution.togglePiece(row, i);
    }
  }
  makeAsolution(0);
  return solution.rows();
};

最初の方法とあまり変わらないが、いくつかのキーワードが変わった.もとは.rows()という配列をロードするために多くの方法を用いたが,これは多くの演算を増加させることに気づいた.この方法を最大限に減らし,他のキーワードで置き換えた.また,衝突検査は回路基板全体の検査から特定のインデックスの検査まで,演算がやや減少した.ソリューションの数を探すのは、上記と何の違いもありません.
明日参考文献を参考に不足を補う.