How do I record a night tour on the n×n board?

Previous Questions (N×n board counting night tours)
I counted the night tours at .

How can I do the following two additional points for this code?
①A path satisfying the conditions is maintained.
②List them, name them, and save them as text files.

Especially regarding に,
I think it will be solved by simply adding a new variable (route log) to the search that I defined.
It's not going well.

ruby c algorithm

2022-09-30 11:18

2 Answers

I thought it would be normal to create a stack to store coordinates, push and record coordinates every time you enter search, and pop when you leave search, but this time you know the maximum depth of the path in advance, and you can't answer until the end.

Somewhere

structure Point {
  intx;
  inty;
};

structure Point path [36];

Define (arrange paths as needed or allocate dynamically),

in search

 int search(int x, int y, int w, int h, int depth, structure point * path) {

  // ...abbreviated...

  if(x<0||w<=x||y<0||h<=y||(used&(1<<(x+y*w)))>0)return0;
  path[depth-1].x=x; /* Record the x coordinates in the array */
  path[depth-1].y=y; /* Record y coordinates in array */
  if(depth==w*h){
      // The path contains the coordinates of the paths in order, so save them.
      return1;
  }

  // ...abbreviated...
}

I think it's good to have something like that.Remember to add path to the recursive search.

2022-09-30 11:18

(Middle progress)
For the time being, Ruby can write about に as follows.
(I didn't know how to write in C.)

When 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
    return1 
  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)
  }
  total
end

main

Run Results
(omitted)
[[4,4], [3,2], [2,4], [0,3], [1,1], [3,0], [4,2], [3,4], [1,3], [0,1], [4,1], [3,3], [3,4], [0,2], [2,2], [2,2], [3,3], [3,3], [3,3], [4,2], [3,1], [0,2,2], [3,1], [0,2,2,2,2,1,2,1,2,1,2,1,2,2,2,2,1,2,2,2,2,2,2,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2, [[4,4], [3,2], [2,4], [0,3], [1,1], [1,0], [2,2], [4,3], [3,1], [1,0], [0,2], [1,4], [3,3], [4,1], [2,1], [0,1], [1,3], [3,4], [4,2], [4,2,2], [0,2], [0,2,2], [0,2,2,2,2,2,2,2,2,2,0,2,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0, 1728

2022-09-30 11:18

If you have any answers or tips

Popular Tags

python x 4647

android x 1593

java x 1494

javascript x 1427

c x 927

c++ x 878

ruby-on-rails x 696

php x 692

python3 x 685

html x 656