棋盘问题
Chess Board Problems
有一个尺寸为n * n
的棋盘。您在该板上有 2 个方块 S(x1,y1)
;M(x2,y2)
。 S
是不动点。 M
可以对角移动。它可以在 1 次移动中移动任意数量的步数或跳跃。找到达到 S
所需的最小步数 M
我的方法:我们可以只计算对角线块,但我对跳跃感到困惑。谁能解释一下他们所说的跳跃是什么意思?
我认为这里的跳是指棋子可以沿对角线移动超过1步的情况。例如,如果在 (1,1) 处,那么它可以一步到 (3,3)。
假设上述情况,我编写了一个回溯算法。
这里的基本思想是让所有可能的动作到达目的地 (x,y) co-ordinate。它检查给定位置的所有有效移动并打印到达此处所遵循的路径。 construct_candidates()
将为您提供当前职位的所有有效候选人 co-ordinate。它检查边界并验证我们之前没有访问过国际象棋块,如果满足这些条件,那么它是移动的有效候选者。
您可以轻松地对其进行修改,以跟踪可能遵循的最短路径。
#define N 4 /* Chess Board Dimension */
#define TRUE 1
#define FALSE 0
#define START_X 0
#define START_Y 0
#define TARGET_X 1
#define TARGET_Y 3
typedef short int bool;
typedef struct point_ {
int x;
int y;
} point_t;
bool is_candidate_valid (point_t *a, int k, int new_x, int new_y)
{
int i;
/* Check bounds */
if ((new_x < 0) || (new_x > (N-1)) ||
(new_y < 0) || (new_y > (N-1))) {
return FALSE;
}
/* Check if this new position is already in the path followed */
for (i = 0; i < k; i++) {
if (a[i].x == new_x && a[i].y == new_y) {
return FALSE;
}
}
return TRUE;
}
void construct_candidates (point_t *a, int k, point_t *candidates, int *n_candidates)
{
int delta;
*n_candidates = 0;
int new_x, new_y;
for (delta = 1; delta <= (N-1); delta++) {
new_x = a[k-1].x + delta;
new_y = a[k-1].y + delta;
if (is_candidate_valid (a, k, new_x, new_y) == TRUE) {
candidates[*n_candidates].x = new_x;
candidates[*n_candidates].y = new_y;
(*n_candidates)++;
}
new_x = a[k-1].x + delta;
new_y = a[k-1].y - delta;
if (is_candidate_valid (a, k, new_x, new_y) == TRUE) {
candidates[*n_candidates].x = new_x;
candidates[*n_candidates].y = new_y;
(*n_candidates)++;
}
new_x = a[k-1].x - delta;
new_y = a[k-1].y + delta;
if (is_candidate_valid (a, k, new_x, new_y) == TRUE) {
candidates[*n_candidates].x = new_x;
candidates[*n_candidates].y = new_y;
(*n_candidates)++;
}
new_x = a[k-1].x - delta;
new_y = a[k-1].y - delta;
if (is_candidate_valid (a, k, new_x, new_y) == TRUE) {
candidates[*n_candidates].x = new_x;
candidates[*n_candidates].y = new_y;
(*n_candidates)++;
}
}
}
bool is_a_solution (point_t *a, int k)
{
if (a[k-1].x == TARGET_X && a[k-1].y == TARGET_Y) {
return TRUE; /* Actual Solution found */
}
if (k == (N*N)) {
return TRUE; /* No Solution found */
}
return FALSE;
}
void process_solution (point_t *a, int k)
{
int i;
if (k == (N*N)) {
return; /* No solution Possible */
}
for (i = 0; i < k; i++) {
printf ("(%d, %d) ", a[i].x, a[i].y);
}
printf ("\n");
}
void backtrack (point_t *a, int k)
{
int i, n_candidates;
point_t candidates[4*(N-1)];
if (is_a_solution (a, k) == TRUE) {
process_solution (a, k);
return;
}
construct_candidates (a, k, candidates, &n_candidates);
for (i = 0; i < n_candidates; i++) {
a[k].x = candidates[i].x;
a[k].y = candidates[i].y;
backtrack (a, k + 1);
}
}
int main()
{
point_t a[N*N];
/* Fill up the initial position */
a[0].x = START_X;
a[0].y = START_Y;
backtrack (a, 1);
}
Output:
(0, 0) (1, 1) (2, 2) (3, 1) (2, 0) (0, 2) (1, 3)
(0, 0) (1, 1) (2, 2) (3, 1) (1, 3)
(0, 0) (1, 1) (2, 2) (1, 3)
(0, 0) (1, 1) (2, 0) (3, 1) (2, 2) (1, 3)
(0, 0) (1, 1) (2, 0) (3, 1) (1, 3)
(0, 0) (1, 1) (2, 0) (0, 2) (1, 3)
(0, 0) (1, 1) (0, 2) (1, 3)
(0, 0) (1, 1) (0, 2) (2, 0) (3, 1) (2, 2) (1, 3)
(0, 0) (1, 1) (0, 2) (2, 0) (3, 1) (1, 3)
(0, 0) (1, 1) (3, 3) (2, 2) (3, 1) (2, 0) (0, 2) (1, 3)
(0, 0) (1, 1) (3, 3) (2, 2) (3, 1) (1, 3)
(0, 0) (1, 1) (3, 3) (2, 2) (1, 3)
(0, 0) (2, 2) (3, 3) (1, 1) (2, 0) (3, 1) (1, 3)
(0, 0) (2, 2) (3, 3) (1, 1) (2, 0) (0, 2) (1, 3)
(0, 0) (2, 2) (3, 3) (1, 1) (0, 2) (1, 3)
(0, 0) (2, 2) (3, 3) (1, 1) (0, 2) (2, 0) (3, 1) (1, 3)
(0, 0) (2, 2) (3, 1) (2, 0) (1, 1) (0, 2) (1, 3)
(0, 0) (2, 2) (3, 1) (2, 0) (0, 2) (1, 3)
(0, 0) (2, 2) (3, 1) (1, 3)
(0, 0) (2, 2) (1, 3)
(0, 0) (2, 2) (1, 1) (2, 0) (3, 1) (1, 3)
(0, 0) (2, 2) (1, 1) (2, 0) (0, 2) (1, 3)
(0, 0) (2, 2) (1, 1) (0, 2) (1, 3)
(0, 0) (2, 2) (1, 1) (0, 2) (2, 0) (3, 1) (1, 3)
(0, 0) (3, 3) (2, 2) (3, 1) (2, 0) (1, 1) (0, 2) (1, 3)
(0, 0) (3, 3) (2, 2) (3, 1) (2, 0) (0, 2) (1, 3)
(0, 0) (3, 3) (2, 2) (3, 1) (1, 3)
(0, 0) (3, 3) (2, 2) (1, 3)
(0, 0) (3, 3) (2, 2) (1, 1) (2, 0) (3, 1) (1, 3)
(0, 0) (3, 3) (2, 2) (1, 1) (2, 0) (0, 2) (1, 3)
(0, 0) (3, 3) (2, 2) (1, 1) (0, 2) (1, 3)
(0, 0) (3, 3) (2, 2) (1, 1) (0, 2) (2, 0) (3, 1) (1, 3)
(0, 0) (3, 3) (1, 1) (2, 2) (3, 1) (2, 0) (0, 2) (1, 3)
(0, 0) (3, 3) (1, 1) (2, 2) (3, 1) (1, 3)
(0, 0) (3, 3) (1, 1) (2, 2) (1, 3)
(0, 0) (3, 3) (1, 1) (2, 0) (3, 1) (2, 2) (1, 3)
(0, 0) (3, 3) (1, 1) (2, 0) (3, 1) (1, 3)
(0, 0) (3, 3) (1, 1) (2, 0) (0, 2) (1, 3)
(0, 0) (3, 3) (1, 1) (0, 2) (1, 3)
(0, 0) (3, 3) (1, 1) (0, 2) (2, 0) (3, 1) (2, 2) (1, 3)
(0, 0) (3, 3) (1, 1) (0, 2) (2, 0) (3, 1) (1, 3)
有一个尺寸为n * n
的棋盘。您在该板上有 2 个方块 S(x1,y1)
;M(x2,y2)
。 S
是不动点。 M
可以对角移动。它可以在 1 次移动中移动任意数量的步数或跳跃。找到达到 S
M
我的方法:我们可以只计算对角线块,但我对跳跃感到困惑。谁能解释一下他们所说的跳跃是什么意思?
我认为这里的跳是指棋子可以沿对角线移动超过1步的情况。例如,如果在 (1,1) 处,那么它可以一步到 (3,3)。
假设上述情况,我编写了一个回溯算法。
这里的基本思想是让所有可能的动作到达目的地 (x,y) co-ordinate。它检查给定位置的所有有效移动并打印到达此处所遵循的路径。 construct_candidates()
将为您提供当前职位的所有有效候选人 co-ordinate。它检查边界并验证我们之前没有访问过国际象棋块,如果满足这些条件,那么它是移动的有效候选者。
您可以轻松地对其进行修改,以跟踪可能遵循的最短路径。
#define N 4 /* Chess Board Dimension */
#define TRUE 1
#define FALSE 0
#define START_X 0
#define START_Y 0
#define TARGET_X 1
#define TARGET_Y 3
typedef short int bool;
typedef struct point_ {
int x;
int y;
} point_t;
bool is_candidate_valid (point_t *a, int k, int new_x, int new_y)
{
int i;
/* Check bounds */
if ((new_x < 0) || (new_x > (N-1)) ||
(new_y < 0) || (new_y > (N-1))) {
return FALSE;
}
/* Check if this new position is already in the path followed */
for (i = 0; i < k; i++) {
if (a[i].x == new_x && a[i].y == new_y) {
return FALSE;
}
}
return TRUE;
}
void construct_candidates (point_t *a, int k, point_t *candidates, int *n_candidates)
{
int delta;
*n_candidates = 0;
int new_x, new_y;
for (delta = 1; delta <= (N-1); delta++) {
new_x = a[k-1].x + delta;
new_y = a[k-1].y + delta;
if (is_candidate_valid (a, k, new_x, new_y) == TRUE) {
candidates[*n_candidates].x = new_x;
candidates[*n_candidates].y = new_y;
(*n_candidates)++;
}
new_x = a[k-1].x + delta;
new_y = a[k-1].y - delta;
if (is_candidate_valid (a, k, new_x, new_y) == TRUE) {
candidates[*n_candidates].x = new_x;
candidates[*n_candidates].y = new_y;
(*n_candidates)++;
}
new_x = a[k-1].x - delta;
new_y = a[k-1].y + delta;
if (is_candidate_valid (a, k, new_x, new_y) == TRUE) {
candidates[*n_candidates].x = new_x;
candidates[*n_candidates].y = new_y;
(*n_candidates)++;
}
new_x = a[k-1].x - delta;
new_y = a[k-1].y - delta;
if (is_candidate_valid (a, k, new_x, new_y) == TRUE) {
candidates[*n_candidates].x = new_x;
candidates[*n_candidates].y = new_y;
(*n_candidates)++;
}
}
}
bool is_a_solution (point_t *a, int k)
{
if (a[k-1].x == TARGET_X && a[k-1].y == TARGET_Y) {
return TRUE; /* Actual Solution found */
}
if (k == (N*N)) {
return TRUE; /* No Solution found */
}
return FALSE;
}
void process_solution (point_t *a, int k)
{
int i;
if (k == (N*N)) {
return; /* No solution Possible */
}
for (i = 0; i < k; i++) {
printf ("(%d, %d) ", a[i].x, a[i].y);
}
printf ("\n");
}
void backtrack (point_t *a, int k)
{
int i, n_candidates;
point_t candidates[4*(N-1)];
if (is_a_solution (a, k) == TRUE) {
process_solution (a, k);
return;
}
construct_candidates (a, k, candidates, &n_candidates);
for (i = 0; i < n_candidates; i++) {
a[k].x = candidates[i].x;
a[k].y = candidates[i].y;
backtrack (a, k + 1);
}
}
int main()
{
point_t a[N*N];
/* Fill up the initial position */
a[0].x = START_X;
a[0].y = START_Y;
backtrack (a, 1);
}
Output: (0, 0) (1, 1) (2, 2) (3, 1) (2, 0) (0, 2) (1, 3) (0, 0) (1, 1) (2, 2) (3, 1) (1, 3) (0, 0) (1, 1) (2, 2) (1, 3) (0, 0) (1, 1) (2, 0) (3, 1) (2, 2) (1, 3) (0, 0) (1, 1) (2, 0) (3, 1) (1, 3) (0, 0) (1, 1) (2, 0) (0, 2) (1, 3) (0, 0) (1, 1) (0, 2) (1, 3) (0, 0) (1, 1) (0, 2) (2, 0) (3, 1) (2, 2) (1, 3) (0, 0) (1, 1) (0, 2) (2, 0) (3, 1) (1, 3) (0, 0) (1, 1) (3, 3) (2, 2) (3, 1) (2, 0) (0, 2) (1, 3) (0, 0) (1, 1) (3, 3) (2, 2) (3, 1) (1, 3) (0, 0) (1, 1) (3, 3) (2, 2) (1, 3) (0, 0) (2, 2) (3, 3) (1, 1) (2, 0) (3, 1) (1, 3) (0, 0) (2, 2) (3, 3) (1, 1) (2, 0) (0, 2) (1, 3) (0, 0) (2, 2) (3, 3) (1, 1) (0, 2) (1, 3) (0, 0) (2, 2) (3, 3) (1, 1) (0, 2) (2, 0) (3, 1) (1, 3) (0, 0) (2, 2) (3, 1) (2, 0) (1, 1) (0, 2) (1, 3) (0, 0) (2, 2) (3, 1) (2, 0) (0, 2) (1, 3) (0, 0) (2, 2) (3, 1) (1, 3) (0, 0) (2, 2) (1, 3) (0, 0) (2, 2) (1, 1) (2, 0) (3, 1) (1, 3) (0, 0) (2, 2) (1, 1) (2, 0) (0, 2) (1, 3) (0, 0) (2, 2) (1, 1) (0, 2) (1, 3) (0, 0) (2, 2) (1, 1) (0, 2) (2, 0) (3, 1) (1, 3) (0, 0) (3, 3) (2, 2) (3, 1) (2, 0) (1, 1) (0, 2) (1, 3) (0, 0) (3, 3) (2, 2) (3, 1) (2, 0) (0, 2) (1, 3) (0, 0) (3, 3) (2, 2) (3, 1) (1, 3) (0, 0) (3, 3) (2, 2) (1, 3) (0, 0) (3, 3) (2, 2) (1, 1) (2, 0) (3, 1) (1, 3) (0, 0) (3, 3) (2, 2) (1, 1) (2, 0) (0, 2) (1, 3) (0, 0) (3, 3) (2, 2) (1, 1) (0, 2) (1, 3) (0, 0) (3, 3) (2, 2) (1, 1) (0, 2) (2, 0) (3, 1) (1, 3) (0, 0) (3, 3) (1, 1) (2, 2) (3, 1) (2, 0) (0, 2) (1, 3) (0, 0) (3, 3) (1, 1) (2, 2) (3, 1) (1, 3) (0, 0) (3, 3) (1, 1) (2, 2) (1, 3) (0, 0) (3, 3) (1, 1) (2, 0) (3, 1) (2, 2) (1, 3) (0, 0) (3, 3) (1, 1) (2, 0) (3, 1) (1, 3) (0, 0) (3, 3) (1, 1) (2, 0) (0, 2) (1, 3) (0, 0) (3, 3) (1, 1) (0, 2) (1, 3) (0, 0) (3, 3) (1, 1) (0, 2) (2, 0) (3, 1) (2, 2) (1, 3) (0, 0) (3, 3) (1, 1) (0, 2) (2, 0) (3, 1) (1, 3)