-1

以前の質問(n×n board におけるナイト・ツアーの数えあげについて
でナイトツアーの数えあげを行いました。

このコードにさらに以下の二点を行うにはどうすればよろしいでしょうか?
①条件を満たす経路を保持する。
②これらをリスト化して名前をつけてテキストファイルとして保存する。

特に①については、
定義したsearchに対し、新たな変数(経路のログ)を加えるだけで解決しそうなのですが
上手くいっていません。

2 件の回答 2

1

座標を格納するスタックを作って、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 を追加するのをお忘れなく。

2
  • (経路を表す構造体を準備するところは理解したのですが、)「search の中では」以降のコードで、条件を満たす経路だけ保存されているのでしょうか?
    – TOM
    2015年9月9日 11:40
  • 1
    @Manyama はい。search は depth == 1 のとき path[0] に、depth == 2 のとき path[1] に、...、depth == 36 のとき path[35] に座標を保存します。ただし、if 文の後なので、保存するのは条件を満たすときだけです。条件を満たしているときは以前の探索を上書きして保存するので、path には常に最新の探索結果だけが保存されています。
    – Hideki
    2015年9月9日 15:01
0

(途中経過)
とりあえず①については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

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。