NQueenのロジックを研究してます。NQueenを別のアプローチから検証するためにアルゴリズムの勉強をはじめました。まずは基礎からで経路探索へ向かいたいと考えています。試行錯誤したことを備忘録として日記に追加することにしました。 10月12日 今マージソートを勉強しているのですが難しいので日記をつけて整理することにしました。 プログラムソースは以下です。 https://github.com/suzukiiichiro/Algorithms-And-Data-Structures/blob/master/Bash/05_1MergeSort.sh ロジ…
NQueenのロジックを研究してます。NQueenを別のアプローチから検証するためにアルゴリズムの勉強をはじめました。まずは基礎からで経路探索へ向かいたいと考えています。試行錯誤したことを備忘録として日記に追加することにしました。 9月29日 今日はバイナリサーチでツリーの中身を表示するメソッドを作成します。 こんな感じでルートノードから下に向かってツリーの中身を出力します…
NQueenのロジックを研究してます。NQueenを別のアプローチから検証するためにアルゴリズムの勉強をはじめました。まずは基礎からで経路探索へ向かいたいと考えています。試行錯誤したことを備忘録として日記に追加することにしました。 9月27日 アルゴリズムの勉強を始めました。 まずは基礎から。 バイナリサーチからスタートします。 それまでのものは鈴木先生が作成している以下のgi…
NQueenのロジックを研究してます。日々NQueenで試行錯誤したことを備忘録として日記に追加することにしました。 9月15日 グラフ理論を使ってエイトクイーンを解く方法があるらしい。 NetworkXを使ってエイト・クイーンパズルを解く https://analytics-note.xyz/graph-theory/networkx-eight-queens-puzzle/ まず、すべて効き筋同…
NQueenのロジックを研究してます。日々NQueenで試行錯誤したことを備忘録として日記に追加することにしました。 9月9日 数が合わない点はsymmetryOps内での単純なコードの間違えだったため修正して数が合った。 ただ、速度が過去のロジックより２０％遅…
NQueenのロジックを研究してます。日々NQueenで試行錯誤したことを備忘録として日記に追加することにしました。 9月5日 n13でsymmetryOps v2 とv1での違いを調査する。 正確な回答 v1の方が数が多いのでv1だけsymmetryOpsを突破したも…
NQueenのロジックを研究してます。日々NQueenで試行錯誤したことを備忘録として日記に追加することにしました。 9月2日 正しい結果と間違った結果のtop,left,bottom,rightの値を比較してみる。 間違った結果の方が数が多いので、間違っている…
NQueenのロジックを研究してます。日々NQueenで試行錯誤したことを備忘録として日記に追加することにしました。 8月30日 枝刈りを追加した。 追加前よりなぜか遅くなった。 symmetryOpsのロジックを変えると速くなるだろうか。 枝刈りを追加することによ…
NQueenのロジックを研究してます。日々NQueenで試行錯誤したことを備忘録として日記に追加することにしました。 8月29日 ミラー処理を入れてみた。 ミラー処理は1行目については右側半分だけクイーンを置くというもの 奇数の場合は真ん中もやる。 ミラー処理を適用…
NQueenのロジックを研究してます。日々NQueenで試行錯誤したことを備忘録として日記に追加することにしました。 8月18日 調べたところ、2辺が同じ場合は3辺目を比較する処理をコメントしていた コメントを外して実行したところ旧ロジックと同じ結果になった。 旧…
NQueenのロジックを研究してます。日々NQueenで試行錯誤したことを備忘録として日記に追加することにしました。 8月17日 新旧ロジックでn2,n4,n8判定の差分をロギングして比較してみた。 以下が新ロジックだとn4だったが、旧ロジックだとn8だった t0:3,t1:5,l0:4,l1:2,b0:3,b1:5,r0:4,r1:6 t0:2,t1:6,l0:6,l1:2,b0:2,b1:6,r0:6,r1:4…
NQueenのロジックを研究してます。日々NQueenで試行錯誤したことを備忘録として日記に追加することにしました。 8月12日 この前と同じようにn10について新旧ロジックを比較して見た。 新ロジックだけのルートは以下の2つだけだった。 どちらも正解にはならなか…
NQueenのロジックを研究してます。日々NQueenで試行錯誤したことを備忘録として日記に追加することにしました。 8月10日 比較して同じだった場合は反時計回りに90度回転させたもの同士を比較するようにしてみた。 例えば 上2行と右2列が同じだった場合はそれぞ…
NQueenのロジックを研究してます。日々NQueenで試行錯誤したことを備忘録として日記に追加することにしました。 8月9日 抽出した新ロジックだけのルートの中から、クイーン数に影響のあるもの、 symmetryOpsのあとで、NQueenをして最終行に到達す…
NQueenのロジックを研究してます。日々NQueenで試行錯誤したことを備忘録として日記に追加することにしました。 8月8日 先日抽出した、新ロジックだけsymmetryOpsを突破した組み合わせのクイーンの配置を出力してみた。 t0:1,t1:3,l0:4,l1:7,b0:1,b1:3,r0:2,r1:7 7 6 5 4 3 2 1 0 ============================= 0| 00000010 1| 00001000 2|…
NQueenのロジックを研究してます。日々NQueenで試行錯誤したことを備忘録として日記に追加することにしました。 8月5日 N8でsymmetryOps直後の新旧ロジックのクイーンの配置を比較してみた。 N8だとユニーク数の正しい数は12 新ロジックだとユニー…
NQueenのロジックを研究してます。日々NQueenで試行錯誤したことを備忘録として日記に追加することにしました。 いままでのNQueenは NQueenは、ひとつの解には、盤面を90度・180度・270度回転、及びそれらの鏡像の合計8個の対称解が存在します…
pythonを勉強しながらNQueen（エイトクイーン）問題を解いていきます。今回は第9回目。対象解除法が正しいことの検証をしてみたいと思います。プログラムを改造してクイーンの配置を出力するようにします。 対象解除法が正しいか検証してみよう 今回は対象解除法が正しいかどうかを検証するためプログラムを改造してクイーンを設置した場所を出力するようにし…
pythonを勉強しながらNQueen（エイトクイーン）問題を解いていきます。今回は第8回目。今回から対象解除法が登場します。解を見てみると左右反転だったり90度、180度回転すると同じものがあります。この性質を利用して探索回数を減らそうというアルゴリズムです。今回は対象解除法の概要を説明します。 対象解除法 今回から対象解除法を取り扱います。 解を見てみると左右反転だったり90度、180度回転すると同じものがあります。この性質を利用して探…
pythonを勉強しながらNQueen（エイトクイーン）問題を解いていきます。今回は第7回目。今回はバックトラックについて図で示しながら詳細な動きを説明します。バックトラックは上下左右対角線上のフラグをチェックするので探索がより効率よくなっています。 バックトラック 今回も引き続きバックトラックを説明していきたいと思います。 前回はプログラムの概要を説明しましたが、今回はnqueenメソッドの…