A Hamiltonian Snake in a Three-Dimensional Box
National Olympiad — National round (2023 season)
Submission name: snake.cpp
Problem summary
Construct a face-adjacent closed route visiting every N×M×K cell once before returning to (1,1,1). Print No if impossible.
Input
N M K.
Output
Yes and NMK+1 coordinate triples, or No. Any valid route is accepted.
Constraints
1≤N,M,K≤100; at least one dimension exceeds 1.
Worked example
Input and output for the worked example discussed below.
Input
2 2 1
Output
Yes 1 1 1 1 2 1 2 2 1 2 1 1 1 1 1
Solution analysis
- Colour cells by parity of x+y+z. Every step switches colour, so odd volume is impossible. A one-dimensional box is also impossible unless it has exactly two cells: the output definition allows traversing their edge out and back.
- Choose an even dimension A. Snake through the other two dimensions to obtain a face-adjacent path of L cells. The box contains A copies of this path and can therefore be treated as an A×L rectangular grid.
- Reserve position 0 of every copy as a return corridor. Start at (0,0), snake through positions 1…L−1 across successive copies, then use the corridor to return to the origin. Since A is even, the final snake end lies next to the corridor.
- For 2×2×1, the route follows the four square corners and returns to (1,1,1). Restore original axes when printing. Streaming the route avoids storing a million triples.
Why it works
Odd volume fails the checkerboard parity condition, and a line longer than two cannot close without repeating an interior cell. Otherwise the row snakes visit every noncorridor cell once, and the final corridor visits each reserved cell once. All consecutive positions share a face and the final position is the origin.
Watch out. Handle the two-cell special case. Include the repeated origin. Even volume alone does not suffice for a longer one-dimensional line.
Commented C++17 solution
An independently written complete program with standard headers.
#include<array>
#include<iostream>
#include<vector>
using namespace std;
int main(){
int dimensions[3];
cin>>dimensions[0]>>dimensions[1]>>dimensions[2];
int volume=dimensions[0]*dimensions[1]*dimensions[2];
int axis=-1;
for(int i=0;i<3;i++){
if(dimensions[i]%2==0){
axis=i;
break;
}
}
if(axis==-1){
cout<<"No\n";
return 0;
}
int b=(axis+1)%3;
int c=(axis+2)%3;
int length=dimensions[b]*dimensions[c];
if(length==1&&volume!=2){
cout<<"No\n";
return 0;
}
vector<array<int,2>>plane;
for(int row=0;row<dimensions[b];row++){
for(int j=0;j<dimensions[c];j++){
int column=row%2==0?j:dimensions[c]-1-j;
plane.push_back({row,column});
}
}
auto print=[&](int a,int position){
int point[3];
point[axis]=a+1;
point[b]=plane[position][0]+1;
point[c]=plane[position][1]+1;
cout<<point[0]<<' '<<point[1]<<' '<<point[2]<<'\n';
};
cout<<"Yes\n";
print(0,0);
if(length==1){
print(1,0);
print(0,0);
return 0;
}
// Reserve position zero in each copy for the return corridor.
for(int a=0;a<dimensions[axis];a++){
for(int j=1;j<length;j++){
int position=a%2==0?j:length-j;
print(a,position);
}
}
for(int a=dimensions[axis]-1;a>=0;a--){
print(a,0);
}
}