27. Knight Tour

Warnsdorff's algorithm

//---------------------------------------------------------------------------
# define DIR 8
struct Cood
{ int dx, dy;
};
struct Step
{ int x, y;
};
struct Move
{ struct Step pos;
int moves;
};
struct Cood offset[DIR];
//------------------ Set up the offset table for the knight moves
{ offset[0].dx = -2; offset[0].dy = 1; offset[1].dx = -1; offset[1].dy = 2;
offset[2].dx = 1; offset[2].dy = 2; offset[3].dx = 2; offset[3].dy = 1;
offset[4].dx = 2; offset[4].dy = -1; offset[5].dx = 1; offset[5].dy = -2;
offset[6].dx = -1; offset[6].dy = -2; offset[7].dx = -2; offset[7].dy = -1;
}
struct Move next[DIR]; // next is an array of 8 element with type struct Move
struct Step step;
int K[50][50];
int n;
struct Step nextMove(struct Step step, int k)
{ struct Step test;
test.x = step.x+offset[k].dx; test.y = step.y+offset[k].dy;
return test; // return the next step of the current step
}
bool InBoard(struct Step test) // check whether test is within the board
{ return (test.x >= 0 && test.x < n) && (test.y >= 0 && test.y < n);
}
bool Empty(struct Step test) // Check whether test is an empty cell
{ return (K[test.x][test.y]==0);
}
bool KnightTour(struct Step step)
{ int data, k, nSquare = n*n, cnt, p, min, i, j;
struct Step test;
K[step.x][step.y] = 1; // set the starting step
for (data=2; data <= nSquare; data++)
{ for (cnt=0, k=0; k<DIR; k++) // collect all legal next steps in next[]
{ test = nextMove(step, k);
if (InBoard(test) && Empty(test))
{ next[cnt].pos = test; // record test as a legal next move
next[cnt++].moves= 0; // init/reset the #moves
}
} // cnt counts the total number of legal moves of the current step
if (cnt == 0) break; // No solution!
for (p=0; p<cnt; p++) // compute each legal move's next moves
{ step = next[p].pos; // step.x = next[p].x; step.y = next[p].y;
for (k=0; k<DIR; k++)
{ test = nextMove(step, k);
if (InBoard(test) && Empty(test))
next[p].moves++;
// test is a legal move for step (one of the next moves)
}
} // all legal moves' next moves are computed
for (min=0, i=1; i<cnt; i++)
if (next[i].moves < next[min].moves) min = i;
// find the next move which has the minimum next moves
step = next[min].pos;
K[step.x][step.y] = data; // step is the next move
}
return (data > nSquare);
}
//------------------------------
n = Edit1->Text.ToInt();
for (i=0; i<n; i++)
for (j=0; j<n; j++)
K[i][j] = 0;
TabSheet3->Show();
start.x = (CheckBox2->Checked) ? rand()%n : Edit2->Text.ToInt();
start.y = (CheckBox2->Checked) ? rand()%n : Edit3->Text.ToInt();
bool tour = KnightTour(start);
printKnight(n);
if (tour)
Memo1->Lines->Add("(x, y) = ("+IntToStr(start.x)+", "+IntToStr(start.y)+") O");
else Memo1->Lines->Add("(x, y) = ("+IntToStr(start.x)+", "+IntToStr(start.y)+") X");

// ---- Using CodeBlocks (no usage of "struct" data type) ----

# define SIZE 20
# define DIR 8
# include <stdio.h>
# include <iostream>
using namespace std;

int K[SIZE][SIZE]; // K[n][n] is a global array
int move_x[SIZE], move_y[SIZE];
void init()
{ int i, j;
move_x[0] = -2; move_y[0] = 1;
move_x[1] = -1; move_y[1] = 2;
move_x[2] = 1; move_y[2] = 2;
move_x[3] = 2; move_y[3] = 1;
move_x[4] = 2; move_y[4] = -1;
move_x[5] = 1; move_y[5] = -2;
move_x[6] = -1; move_y[6] = -2;
move_x[7] = -2; move_y[7] = -1;
cout << "Please input board size n, and starting position (x, y)." << endl;
}

void kinghtTour(int n, int x, int y)
{ int next_x[DIR], next_y[DIR], next_moves[DIR];
int i, j, k, step, nSquare, tx, ty, sx, sy, cnt, min;
for (i=0; i<n; i++) //*(Kp+i) = 0;
for (j=0; j<n; j++) K[i][j] = 0;
K[x][y] = 1;
for (nSquare = n*n, sx=x, sy=y, step = 2; step <= nSquare; step++)
{ for (cnt = 0, k = 0; k < DIR; k++)
{ tx = sx+move_x[k]; ty = sy+move_y[k];
if ((tx>=0 && tx<n) && (ty>=0 && ty<n) && !K[tx][ty])
{ next_x[cnt] = tx; next_y[cnt++] = ty;
}
}
if (cnt == 0) break;
for (i = 0; i < cnt; i++)
{ sx = next_x[i]; sy = next_y[i]; next_moves[i] = 0;
for (k = 0; k < DIR; k++)
{ tx = sx+move_x[k]; ty = sy+move_y[k];
if ((tx>=0 && tx<n) && (ty>=0 && ty<n) && !K[tx][ty]) next_moves[i]++; }
}
for (min = 0, i = 1; i < cnt; i++)
if (next_moves[i] < next_moves[min]) min = i;
sx = next_x[min]; sy = next_y[min];
K[sx][sy] = step;

}
if (step > nSquare)
{ for (i = 0; i < n; i++)
{ for (j = 0; j < n; j++) printf("%7d", K[i][j]);
cout << endl;
}
}
else
cout << "No knight's tour from (" << x << ", " << y << ")!" << endl;
}

int main()
{ int n, x, y;
init();
while (cout<<"n = ", (cin >> n), n!=0)
{ cout<< "x y = ";
cin >> x >> y;
kinghtTour(n, x, y);
}
}