棋盤問題

Question

有一個尺寸爲n * n的棋盤。您在該板上獲得2個方格S(x1,y1); M(x2,y2)。 S是一個固定點。 M可以對角移動。它可以移動任意數量的步驟或跳躍。找到移動的最小數目M需要達到S

我的方法：我們算了算對角塊，但我很困惑與跳躍。任何人都可以解釋跳躍意味着什麼嗎？

Answer 1

我覺得這裏的跳棋是指棋子可以對角移動超過1步的情況。例如，如果在（1,1）處，那麼它可以在一步中轉到（3,3）。

假設上述情況，我編寫了一個bactracking算法。 這裏的基本想法是讓所有可能的動作到達目標（x，y）座標。它會檢查給定位置的所有有效移動並打印到達此處的路徑。 construct_candidates()會爲您提供當前位置的所有有效候選座標。它會檢查邊界，並驗證我們以前沒有訪問過國際象棋棋子，如果這些條件得到滿足，那麼它就是移動的有效候選者。

您可以輕鬆修改它以跟蹤最短路徑。

#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)