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

Asked 1 months ago, Updated 1 months ago, 3 views

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

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 4429
android x 1590
java x 1475
javascript x 1383
c x 903
c++ x 830
ruby-on-rails x 680
php x 678
python3 x 651
html x 631