以前の質問(n×n board におけるナイト・ツアーの数えあげについて)
でナイトツアーの数えあげを行いました。
このコードにさらに以下の二点を行うにはどうすればよろしいでしょうか?
①条件を満たす経路を保持する。
②これらをリスト化して名前をつけてテキストファイルとして保存する。
特に①については、
定義したsearchに対し、新たな変数(経路のログ)を加えるだけで解決しそうなのですが
上手くいっていません。
スタック・オーバーフローはプログラマーとプログラミングに熱心な人のためのQ&Aサイトです。すぐ登録できます。
登録してこのコミュニティに参加する以前の質問(n×n board におけるナイト・ツアーの数えあげについて)
でナイトツアーの数えあげを行いました。
このコードにさらに以下の二点を行うにはどうすればよろしいでしょうか?
①条件を満たす経路を保持する。
②これらをリスト化して名前をつけてテキストファイルとして保存する。
特に①については、
定義したsearchに対し、新たな変数(経路のログ)を加えるだけで解決しそうなのですが
上手くいっていません。
座標を格納するスタックを作って、search に入るたびに座標を push して記録し、search から出るときに pop するのが常道かとも思いましたが、今回は経路の最大の深さが、あらかじめ分かっていますし、最後まで行かなければ答えが出せないので、最大の深さの要素を入れられる配列を用意して記録していくのがいいと思います。
どこかに
struct Point {
int x;
int y;
};
struct Point path[36];
を定義して (path は必要に応じて配列にしたり、動的にアロケートしたりしてください ) 、
search の中では
int search(int x, int y, int w, int h, int depth, struct Point * path){
// ... 略 ...
if (x < 0 || w <= x || y < 0 || h <= y || (used & (1 << (x + y * w))) > 0) return 0;
path[depth-1].x = x; /* 配列に x 座標を記録 */
path[depth-1].y = y; /* 配列に y 座標を記録 */
if (depth == w * h) {
// path の中に経路の座標が順番に入っているので保存する
return 1;
}
// ... 略 ...
}
のような感じでいいと思います。search を再帰的に呼び出しているところにも path を追加するのをお忘れなく。
(途中経過)
とりあえず①についてはRubyなら以下のように書ける。
(Cではどう書くかわからなかった。)
w = 5 のとき
def search(x, y, w, h, used, depth, path)
return 0 if x < 0 || w <= x || y < 0 || h <= y || (used & (1 << (x + y * w))) > 0
if depth == w * h
path[depth - 1] = [x, y]
p path
return 1
end
path[depth - 1] = [x, y]
cnt = 0
used += 1 << (x + y * w)
cnt += search(x + 2, y - 1, w, h, used, depth + 1, path)
cnt += search(x + 2, y + 1, w, h, used, depth + 1, path)
cnt += search(x - 2, y - 1, w, h, used, depth + 1, path)
cnt += search(x - 2, y + 1, w, h, used, depth + 1, path)
cnt += search(x + 1, y - 2, w, h, used, depth + 1, path)
cnt += search(x + 1, y + 2, w, h, used, depth + 1, path)
cnt += search(x - 1, y - 2, w, h, used, depth + 1, path)
cnt += search(x - 1, y + 2, w, h, used, depth + 1, path)
used -= 1 << (x + y * w)
return cnt
end
def main
w = 5
total = 0
(0..w * w - 1).each{|i|
path = []
total += search(i % w, i / w, w, w, 0, 1, path)
}
p total
end
main
実行結果
(中略)
[[4, 4], [3, 2], [2, 4], [0, 3], [1, 1], [3, 0], [4, 2], [3, 4], [1, 3], [0, 1], [2, 0], [4, 1], [3, 3], [1, 4], [0, 2], [1, 0], [2, 2], [4, 3], [3, 1], [2, 3], [0, 4], [1, 2], [0, 0], [2, 1], [4, 0]]
[[4, 4], [3, 2], [2, 4], [0, 3], [1, 1], [3, 0], [2, 2], [4, 3], [3, 1], [1, 0], [0, 2], [1, 4], [3, 3], [4, 1], [2, 0], [0, 1], [1, 3], [3, 4], [4, 2], [2, 3], [0, 4], [1, 2], [0, 0], [2, 1], [4, 0]]
1728