Best Score in Ten Moves
National Olympiad — National round
Submission name: game2048.cpp
Problem summary
On a 3×3 board, slide all tiles in one of four directions. Equal consecutive tiles merge toward that edge, adding their combined value to the score. A tile produced by a merge cannot merge again during that move. Empty cells are 0 and no new tiles appear. Among sequences of at most ten moves, maximize the total score; among those, minimize the number of moves.
Input
The nine board values, row by row.
Output
Maximum score and minimum number of moves attaining it.
Constraints
Each initial cell is 0, 2, 4, 8, or 16; at most 10 moves.
Worked example
An independently prepared example for this explanation.
Input
2 2 0 0 0 0 0 0 0
Output
4 1
Solution analysis
- Enumerate the four choices at each depth up to ten. Extract each row or column starting from the chosen edge, remove zeros, and merge adjacent equal values once.
- Update the best score at every state, not only at depth ten; break equal-score ties by smaller depth. Ignore moves that leave the board unchanged.
Why it works
The line operation reproduces the slide rule exactly. Every useful sequence of at most ten moves appears in the search; removing an unchanged move cannot reduce score and improves the tie-break.
Watch out. This maximizes accumulated merge points, not the largest tile. Do not repeatedly merge a newly formed tile.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<array>
using namespace std;
using B=array<int,9>;
int best=0,steps=0;
void dfs(B a,int depth,int score){
if(score>best||(score==best&&depth<steps)){
best=score;
steps=depth;
}
if(depth==10){
return;
}
for(int dir=0;dir<4;dir++){
B b{};
int gain=0;
for(int line=0;line<3;line++){
vector<int>ids,v,out;
for(int k=0;k<3;k++){
int r,c;
if(dir<2){
r=line;
c=dir==0?k:2-k;
}
else{
r=dir==2?k:2-k;
c=line;
}
ids.push_back(r*3+c);
if(a[r*3+c]){
v.push_back(a[r*3+c]);
}
}
// Consume both source tiles: the result cannot merge again this turn.
for(int k=0;k<(int)v.size();k++){
if(k+1<(int)v.size()&&v[k]==v[k+1]){
out.push_back(2*v[k]);
gain+=2*v[k];
k++;
}
else{
out.push_back(v[k]);
}
}
for(int k=0;k<(int)out.size();k++){
b[ids[k]]=out[k];
}
}
if(b!=a){
dfs(b,depth+1,score+gain);
}
}
}
int main(){
B a;
for(int&x:a){
cin>>x;
}
dfs(a,0,0);
cout<<best<<' '<<steps<<'\n';
}