# 6.24 騎士的旅程Knight tour

//https://liuxiaozhu.github.io/algorithm-test/AlgorithmGossip/KnightTour.htm
#include <stdio.h>
#define N 8
int travel(int x, int y);
int board[N][N] = {0}; 
int main(void) {
    travel(5, 6); //起始點
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++)
            printf("%3d", board[i][j]);
        putchar('\n');
    }
} 
int travel(int x, int y) {
    // 騎士可走的八個方向
    int ktmove1[N] = {-2, -1, 1, 2, 2, 1, -1, -2};
    int ktmove2[N] = {1, 2, 2, 1, -1, -2, -2, -1};

    // 測試下一步的出路
    int nexti[N] = {0};
    int nextj[N] = {0};

    int i=x, j=y, k, m, l;
    int tmpi, tmpj;
    int count, min, tmp;
    board[i][j] = 1; //起點為1

    for(m = 2; m < 65; m++) { //m步數. 總步數64.
        l = 0;

        // 試探八個方向
        for(k = 0; k < N; k++) {
            tmpi = i + ktmove1[k];
            tmpj = j + ktmove2[k];

            // 如果是邊界了，不可走
            if (tmpi < 0 || tmpj < 0 || tmpi > 7 || tmpj > 7) continue;

            // 如果這個方向可走，記錄下來
            if (board[tmpi][tmpj] == 0) {
                nexti[l] = tmpi;
                nextj[l] = tmpj;
                l++; // 可走的方向加一個
            }
        }
        count = l;

        // 如果可走的方向為0個，返回
        if (count == 0) return 0;
        else if (count == 1) {
            // 只有一個可走的方向
            // 所以直接是最少出路的方向
            min = 0;
        }
        else {
            int exists[N]={0}; // 記錄出路的個數
            // 找出下一個位置的出路數
            for(l = 0; l < count; l++) {
                for(k = 0; k < N; k++) {
                    tmpi = nexti[l] + ktmove1[k];
                    tmpj = nextj[l] + ktmove2[k];

                    if (tmpi < 0 || tmpj < 0 || tmpi > 7 || tmpj > 7) continue;
                    if (board[tmpi][tmpj] == 0) exists[l]++;
                }
            }

            tmp = exists[0];
            min = 0;

            // 從可走的方向中尋找最少出路的方向
            for(l = 1; l < count; l++) {
                if(exists[l] < tmp) {
                    tmp = exists[l];
                    min = l;
                }
            }
        }

        // 走最少出路的方向
        i = nexti[min];
        j = nextj[min];
        board[i][j] = m;
    }
    return 1;
} 

# 方法二

//https://openhome.cc/zh-tw/algorithm/basics/knight-tour/
#include <stdio.h> 
#define N 8
typedef struct {
    int x; 
    int y;
} Step;

Step step(int, int);
void travel(int[][N], Step);
void possible(int[][N], Step, int*);
int count(int*);
Step get(Step, int*, int);
Step hard(int[][N], Step, int*);
int isVisitable(int[][N], Step);

int main() {
    int board[N][N] = {0};
    travel(board, step(5, 6)); //起始點(5,6)
    
    for(int i = 0; i<N; i++) {
        for(int j = 0; j<N; j++)
            printf("%3d", board[i][j]);
        printf("\n");
    }
} 
Step step(int x, int y) { //回傳位置
    Step s = {x, y};
    return s;
}
void travel(int board[][N], Step start) {
    board[start.x][start.y] = 1;
    Step current = start;
    
    for(int s=2; s<65; s++) { //s步數. 總步數64.
        int possibleSteps[N] = {0};
        possible(board, current, possibleSteps); //計算possibleSteps陣列
        
        int c = count(possibleSteps); //計算總共幾個位置可走
        if(c == 0) break; //遊歷失敗
        if(c == 1) //只有一步可走
            current = get(current, possibleSteps, 1);
        //找出下一步出路最少的格子。如果出路值相同，則選第一個遇到的出路。
        //走最少出路的格子，記錄騎士的新位置。
        else
            current = hard(board, current, possibleSteps);
        board[current.x][current.y] = s; //紀錄走的順序
    }
}
void possible(int board[][N], Step current, int* possibleSteps) {
     int dirs[8][2] = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, 
                       	  {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
     for(int i=0; i<N; i++) {
         Step s = step(current.x + dirs[i][0], current.y + dirs[i][1]);
         if(isVisitable(board, s)) possibleSteps[i] = 1;
     }
}
int isVisitable(int board[][N], Step step) {
    return step.x > -1 && step.x < N &&
           step.y > -1 && step.y < N &&
           !board[step.x][step.y];
}
int count(int* possibleSteps) {
    int c=0, i=0;
    for (; i<N; i++) 
    	if (possibleSteps[i]) c++;
    return c;
}
//得到下一步要走的位置
Step get(Step current, int* possibleSteps, int number) {
    //騎士可走的八個方向
    int dirs[8][2] = {{-2, 1}, {-1, 2}, {1, 2},   {2, 1}, 
                      {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
    int c=0, i=0;
    for (; i<N; i++) {
        if (possibleSteps[i]) c++;
        if (c == number) break;
    }
    return step(current.x + dirs[i][0], current.y + dirs[i][1]);
}
Step hard(int board[][N], Step current, int* possibleSteps) {
    int minPossibleSteps[N] = {0};
    possible(board, get(current, possibleSteps, 1), minPossibleSteps);

    int minIndex=0, i=1;
    for(; i < count(possibleSteps); i++) {
        int nextPossibleSteps[N] = {0};
        Step s = get(current, possibleSteps, i+1);
        possible(board, s, nextPossibleSteps);
        if(count(nextPossibleSteps) < count(minPossibleSteps)) {
            minIndex = i;
            for(int j=0; j<N; j++)
                minPossibleSteps[j] = nextPossibleSteps[j];
        }
    }
    return get(current, possibleSteps, minIndex + 1);
}
/*(5,6)
 56 11 58 31 54 13 18 33
 47 30 55 12 59 32 53 14
 10 57 48 63 50 17 34 19
 29 46 41 60 39 62 15 52
 42  9 64 49 16 51 20 35
 25 28 45 40 61 38  1  4
  8 43 26 23  6  3 36 21
 27 24  7 44 37 22  5  2
 
 (5,5)
 63 48  9 50 19 22 11 24
  8 51 64 47 10 25 18 21
 59 62 49 34 43 20 23 12
 52  7 58 61 46 35 26 17
 57 60 53 42 33 44 13 36
  6 41 32 45 54  1 16 27
 31 56 39  4 29 14 37  2
 40  5 30 55 38  3 28 15
 
 (5,4)X
 34 31 10  0 26 29  8  5
 11  0 33 30  9  6 23 28
 32 35  0 25 48 27  4  7
  0 12 59 36 53 24 49 22
 60 43 54 47 58 37 18  3
 13 46 57 52  1 50 21 38
 42 55 44 15 40 19  2 17
 45 14 41 56 51 16 39 20
 
 (5,3)
 29 26 11 62 55 24  9  6
 12 63 28 25 10  7 54 23
 27 30 59 56 61 50  5  8
 64 13 48 43 58 53 22 37
 31 44 57 60 49 38 51  4
 14 47 42  1 52 19 36 21
 41 32 45 16 39 34  3 18
 46 15 40 33  2 17 20 35
 
 (5,2)
 34 61  6 45 36 49  8 47
  5 44 35 62  7 46 27 38
 64 33 60 41 50 37 48  9
 43  4 63 54 59 28 39 26
 32 55 42 51 40 53 10 19
  3 14  1 58 29 20 25 22
 56 31 16 13 52 23 18 11
 15  2 57 30 17 12 21 24
 
 (5,1)
 31 28 13 48 43 26 11  8
 14 53 30 27 12  9 44 25
 29 32 49 54 47 42  7 10
 52 15 56 63 50 45 24 41
 33 62 51 46 55 58 37  6
 16  1 64 57 36 21 40 23
 61 34  3 18 59 38  5 20
  2 17 60 35  4 19 22 39
  
  (5,0)
 14 29 10 41 24 27  8 45
 11 42 13 28  9 44 23 26
 30 15 60 43 40 25 46  7
 59 12 31 52 57 48 39 22
 16 53 58 61 32 51  6 47
  1 64 33 54 49 56 21 38
 34 17 62  3 36 19 50  5
 63  2 35 18 55  4 37 20
 
 (5,-1)X
 23  8 45 40 25 10 29 50
 44 41 24  9 46 51 26 11
  7 22 43 58 39 28 49 30
 42 59 38 47 52 57 12 27
 21  6 61 56 37 48 31  1
 60  3 36 53 62 55 16 13
  5 20  0 34 15 18 63 32
  2 35  4 19 54 33 14 17
*/