

以前の質問（[n×n board
におけるナイト・ツアーの数えあげについて](https://ja.stackoverflow.com/questions/16301/n%C3%97n-board-%E3%81%AB%E3%81%8A%E3%81%91%E3%82%8B%E3%83%8A%E3%82%A4%E3%83%88-%E3%83%84%E3%82%A2%E3%83%BC%E3%81%AE%E6%95%B0%E3%81%88%E3%81%82%E3%81%92%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6)）  
でナイトツアーの数えあげを行いました。

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

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


CC BY-SA 3.0
2015-09-08T22:31:16.710
16399
2015-09-10T13:22:16.407
2017-04-13T12:52:38.920
-1
5363
question
ruby c アルゴリズム
n×n board におけるナイト・ツアーを記録するには？


座標を格納するスタックを作って、search に入るたびに座標を push して記録し、search から出るときに pop
するのが常道かとも思いましたが、今回は経路の最大の深さが、あらかじめ分かっていますし、最後まで行かなければ答えが出せないので、最大の深さの要素を入れられる配列を用意して記録していくのがいいと思います。

どこかに

[code]

    struct Point {
      int x;
      int y;
    };
    
    struct Point path[36];
    
[/code]

を定義して (path は必要に応じて配列にしたり、動的にアロケートしたりしてください ) 、

search の中では

[code]

    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;
      }
    
      // ... 略 ...
    }
    
[/code]

のような感じでいいと思います。search を再帰的に呼び出しているところにも path を追加するのをお忘れなく。


CC BY-SA 3.0
2015-09-08T23:55:26.390
16402
2015-09-08T23:55:26.390
3605
16399
answer


（途中経過）  
とりあえず①についてはRubyなら以下のように書ける。  
（Cではどう書くかわからなかった。）

w = 5 のとき

[code]

    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
    
[/code]

実行結果  
（中略）  
[[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


CC BY-SA 3.0
2015-09-10T13:21:33.533
16477
2015-09-10T13:21:33.533
5363
16399
answer