README

DevQuiz のSlidingPuzzleを解くためのC++コードです。 
(C++といいつつclassでカプセル化と途中での宣言を使っている意外はCですが）

あらかじめproblems.txtを用意し、更にresultsフォルダを作っておく必要あり。
途中で止めて再開出来る機能もあり。
二重ループの値それぞれと、その時に出来てるresultsのNoを指定
（多分コードを読まないと何のことだか分からないだろうけど


アルゴリズムはIDDFSにマンハッタン距離による枝狩りと言う事になるんでしょうか？
オーダーを改善するのは早々に諦めて定数値側の削減をやってましてました。
MBA(1.6GHz Core2duo)で1千2百万試行/secぐらいの性能。
133cycle/tryぐらいでもう少し減るかなという気はする。
#最初は320cycle/tryぐらいかかってた。
コードが汚いのは仕様です。諦めて下さい＞＜

ついでに、Rubyで書いたのも付けときます。
こちらはC++の後でもうちょっと減るかなの部分を検討してみた物
・再帰の展開
・ボードの使い回し
・距離比較でテーブル引きしてる所を演算に。
・移動可能性をガードのみに
を適応してみた。
再帰の展開が割と複雑になってしまったので、これについてはC++に適応して速くなるか謎。
ただし、再帰の展開はスタックに保存してる情報を明示的に管理して
処理の途中で中断出来る為というのもあるのでやっぱ適応した方がいいんだろうな。

sliding.cxx

//
// you have to do `mkdir results` for create result folder
// written by tarui@prx.jp

#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<time.h>

typedef struct {
  char board[37];
}board_t;

class SlidingPuzzle{
  board_t start;
  board_t target;
  int width,height;
  int txpos[36];
  int typos[36];
  //int mini;
  long moves;
  int start_distance;
public:
  int step;
  char *result;
private:
  int result_pos;

  inline int c2index(char c){
    return c == '=' ? 0 :
      c > 64 ? c - 65 + 10 : c - 48;
  }

  inline bool _move(board_t &now,int &pos,int delta,int &n,int &distance){
    int npos =  pos + delta;
    int idx = c2index(now.board[npos]);
    int d;
    if(!idx)return false;
    now.board[pos]=now.board[npos];
    //comment out for reuse now area ( board_t now -> board_t &now )
    //now.board[npos]='0';
    if(delta == 1 || delta == -1){
      d = txpos[idx] - (npos % width);
      if ( d * delta < 0)
	return _solve(now,npos,n-1,delta,distance-1);
      else
	return _solve(now,npos,n-1,delta,distance+1);
    }else{
      d = typos[idx] - (npos / width);
      if ( d * delta < 0)
	return _solve(now,npos,n-1,delta,distance-1);
      else
	return _solve(now,npos,n-1,delta,distance+1);
    }
  }

  inline void print(board_t now){
    char buff[100];
    printf("-----------\n");
    for(int i=0;i<height;i++){
      strncpy(buff,now.board+i*width,width);
      buff[width]=0;
      printf("%s\n",buff);
    }
  }

  inline void add_result(int before){
    if(before == -1){
      result[result_pos++] = 'R';
    }else if(before == 1){
      result[result_pos++] = 'L';
    }else if(before < 0){
      result[result_pos++] = 'D';
    }else if(before > 1){
      result[result_pos++] = 'U';
    }else{
      result[result_pos] = 0;
    }
  }
    
  bool _solve(board_t now,int pos, int n,int before,int distance){
    //printf("%s : %d\n",now.board,n);
    //    printf(":%d\n",n);
    //    print(now);
    //    printf("%d:  %s -> %s\n",n,now.board,target.board);
    /*
    if(mini > distance){
      mini = distance;
      //printf("mini = %d\n",mini);
    }
    */
    if(n < distance) return false;
    if(distance == 0){
      result = new char[step+1];
      add_result(before);
      return true;
    }
    moves++;
    if(before != 1 &&
       pos % width >0 && 
       _move(now,pos,-1,n,distance)){
      add_result(before);
      return true;
    }
    if(before != -1 &&
       pos % width < width-1 &&
       _move(now,pos,+1,n,distance)){
      add_result(before);
      return true;
    }
    if(before != width &&
       pos >= width &&
       _move(now,pos,-width,n,distance)){
      add_result(before);
      return true;
    }
    if(before != -width &&
       pos + width < width*height &&
       _move(now,pos,+width,n,distance)){
      add_result(before);
      return true;
    }
    return false;
  }
public:
  int solve(void){
    time_t t0;
    int pos = strchr(start.board,'0') - start.board;
    for(;;){
      t0 = time(NULL);
      if(_solve(start,pos,step,0,start_distance)){
	return step;
      }
      printf("%d : time = %ld\n",step,time(NULL) - t0);
      step+=2;
    }
  }
  int solve_until(int limit){
    time_t t0;
    printf("%d, %dx%d %-36s : step %d ",
	   start_distance,width,height,
	   target.board,step);
    fflush(stdout);
    moves = 0;
    int pos = strchr(start.board,'0') - start.board;
    while(step<limit){
      t0 = time(NULL);
      if(_solve(start,pos,step,0,start_distance)){
	printf(": time %3ld : moves %10ld\n",time(NULL) - t0,moves);
	return step;
      }
      printf(": time %3ld : moves %10ld\n",time(NULL) - t0,moves);
      step+=2;
    }
    return 0;
  }
  ~SlidingPuzzle(){
    delete[] result;
  }
  SlidingPuzzle(int w,int h,char *t):width(w),height(h){
    int size=w*h;
    int pos=0;
    result_pos=0;
    result=NULL;

    strcpy(target.board,t);

    strncpy(start.board,"123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ",size);
    start.board[size]=0;
    for(int i=0;i<size;i++){
      if(t[i]=='='){
	start.board[i]='=';
      }else{
	pos=i;
      }
    }
    start.board[pos]='0';
    
    //calc txpos,typos
    for(int i=0;i<size;i++){
      int idx = c2index(t[i]);
      if(idx){
	txpos[idx] = i % width;
	typos[idx] = i / width;
      }
    }
    //calc distance;
    start_distance = 0;
    for(int i=0;i<width*height;i++){
      int idx = c2index(start.board[i]);
      if(idx){
	int d;	
	d = txpos[idx] - (i % width);
	start_distance += d > 0 ? d : - d;
	d = typos[idx] - (i / width);
	start_distance += d > 0 ? d : - d;
      }
    }
    //mini = start_distance;
    step = start_distance;

  }
};

int main(int argc,char *argv[]){
  FILE *fp,*wfp;
  int cstep = 40;
  int cnum = 0;
  if(argc > 1){
    if(argc != 4){
      printf("args : c_step c_num c_no\n");
      exit(-1);
    }
    cstep = atoi(argv[1]);
    cnum = atoi(argv[2]);

    printf("continue : step = %d , num = %d no=%s\n",cstep,cnum,argv[3]);
  }

  fp = fopen("problems.txt","rb");
  if(!fp){
    fprintf(stderr,"cannot open file\n");
    return -1;
  }
  int lx,rx,ux,dx;
  fscanf(fp,"%d %d %d %d",&lx,&rx,&ux,&dx);
  //fprintf(stdout,"%d,%d,%d,%d\n",lx,rx,ux,dx);
  int num;
  int w,h;
  char data[1000];
  int no=0;
  SlidingPuzzle **puzzles;
  fscanf(fp,"%d",&num);
  puzzles = new SlidingPuzzle *[num];
  for(int i=0;i<num;i++){
    fscanf(fp,"%d,%d,%s",&w,&h,data);
    //fprintf(stdout,"%d,%d,%s\n",w,h,data);
    puzzles[i] = new SlidingPuzzle(w,h,data);
  }

  if(argc >3){
    FILE *cfp;
    no = atoi(argv[3]);
    sprintf(data,"results/%d.txt",no++);
    cfp = fopen(data,"rb");
    for(int i=0;i<num;i++){
      fgets(data,sizeof(data),cfp);
      while(strlen(data) && data[strlen(data)-1] < 0x20){
	data[strlen(data)-1]=0;
      }
      if(strlen(data)){
	puzzles[i]->result = new char[strlen(data)+1];
	strcpy(puzzles[i]->result,data);
      }else{ 
	while(puzzles[i]->step < cstep-(i >= cnum ? 1 : 0)){
	  puzzles[i]->step +=2;
	}
      }
    }
    fclose(cfp);
  }
  

  for(int step=cstep;no < num;step++){
    for(int i=cnum;i<num;i++){
      SlidingPuzzle *p=puzzles[i];
      if(p->result || p->step >= step ) 
	continue;
      
      printf("no %4d(%d) : ",i,step);
      int r = p->solve_until(step);
      if(r){
	printf("%4d(%4d):result =%d %s\n",i,no,r,p->result);
	sprintf(data,"results/%d.txt",no++);
	wfp = fopen(data,"wb");
	if(!wfp){
	  printf("cannot open file for reuslt  : `%s'\n"
		 "maybe you have to do mkdir results\n",data);
	  exit(-1);
	}
	for(int j=0;j<num;j++){
	  if(puzzles[j]->result){
	    fprintf(wfp,"%s\n",puzzles[j]->result);
	  }else{
	    fprintf(wfp,"\n");
	  }
	}
	fclose(wfp);
      }
    }
    cnum = 0;
  }
  for(int i=0;i<num;i++){
    delete puzzles[i];
  }
  delete[] puzzles;
  fclose(fp);
  return 0;
}

sliding.rb

class SlidingPuzzle
  attr_reader :result,:step
  def c2id(c)
    n =
      c > 0x40 ? c - 0x41 + 10 : 
      c > 0x30 && c < 0x3a ? c - 0x30 : 0
    return 0 if n==0
    y,x = (n-1).divmod(@width)
    y*8 + x + 9
  end
  def calc_distance
    @board.map.with_index{|i,idx| 
      if i > 1
        y,x = idx.divmod(8)
        (i/8 - y).abs + (i%8 - x).abs
      else
        0
      end
    }.inject(:+)
  end
  def _solve # push,pop,L,U,D,R (0,1,2,3)
    move=[-5,0]
    distance=[@distance]
    loop do
#      p distance
      # do moving
      # can?
      delta = [-1,-8,8,1,0][move[-1]]
      npos = @pos + delta
      movable = move[-1]<4 &&
        @board[npos] > 0 &&
        move.size-2+distance[-1] <= @step && 
        move[-2] + move[-1] != 3
      if movable
        @moves +=1
        # move
        @board[@pos]=@board[npos]
        idx = @board[npos]
        if (delta == -1 || delta == 1) ? 
          ( (idx%8) - (npos%8) ) * delta < 0 :
          ( (idx/8) - (npos/8) ) * delta < 0 
          distance << distance[-1] - 1
        else
          distance << distance[-1] + 1
        end
        @pos = npos
        if distance[-1] == 0
          move.shift
          @result = move.map{|i| ["L","U","D","R"][i]}*""
          return true
        end
        # push
        move << 0
      else
        if move[-1] > 3 || move.size-2+distance[-1] > @step  #pop
          move.pop
          distance.pop
          return false if move.size == 1
          # rollback board
          delta = [-1,-8,8,1][move[-1]]
          npos = @pos - delta
          @board[@pos]=@board[npos]
          @pos = npos
        end
        #rotate
        move[-1]+=1
      end
    end
  end

  def solve_until(limit)
=begin
    p [@str,@distance,@pos.to_s(8)]
    8.times{|i|
      p @board[i*8,8].map{|i| "%03o" % i}*" "
    }
    puts "----"
=end
    t0 = Time.now
    @moves = 0
    while @step < limit
      r = _solve
      puts "time = %8.3f : moves = %10d" % [Time.now-t0,@moves]
      return @result.size if r
      @step+=2
    end
  end
  def status
    "%2d %dx%d %-36s step %2d" % [@distance,@width,@height,@data,@step]
  end
  def initialize(str)
    @str=str
    w,h,d = str.chomp.split(/,/)
    @data = d
    @width = w.to_i
    @height = h.to_i
    @board = Array.new(64){-1}
    d.size.times{|i|
      c = c2id(d[i].ord)
      y,x = i.divmod(@width)
      @board[y*8+x+9] = c
      if d[i]=="0"
        @pos=y*8+x+9
      end
    }
    @distance=calc_distance
    @result = nil
    @step = @distance
    @cur=0
  end
end

Dir.mkdir "results" rescue nil

@puzzles =[]
open("problems.txt","rb"){|io|
  @limits = io.gets.split.map{|i| i.to_i}
  @num = io.gets.to_i
  @num.times{|i|
    @puzzles << SlidingPuzzle.new(io.gets)
  }
}
step = 20
no = 0
while no < @num
  @puzzles.each_with_index{|puzzle,idx|
    next if puzzle.result || puzzle.step >= step
#    next if puzzle.instance_eval{@width}!=3
    print "no %4d(%d) : %s : " % [idx,step,puzzle.status]
    $stdout.flush
    r = puzzle.solve_until(step)
    if r
      puts "%4d(%4d):result = %d %s" % [ idx,no,r,puzzle.result ]
      open("results/#{no}.txt","wb"){|io|
        @puzzles.each{|i| io.puts i.result }
      }
      no+=1
    end
  }
  step +=1
end