DFS demo: horse traverse the whole chessboard

HorseTraverse.c

#include <stdio.h>
#include <unistd.h>

static const int OFFSETS[8][2] = {
    {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}
};

static void print_board(int const board[8][8], long solution_num) {
    fputs("\033[10A\033[2K", stdout);
    if(solution_num != 0) {
        printf("Found solution \033[4m#%ld\033[24m:\n", solution_num);
    } else {
        puts("\033[37m\033[41mFinding a solution...\033[39m\033[49m");
    }
    fputs("\033[1m     0   1   2   3   4   5   6   7 \033[22m\n", stdout);
    for(int i = 0; i < 8; ++i) {
        printf("\033[1m %d \033[22m", i);
        for(int j = 0; j < 8; ++j) {
            if(board[i][j] == 64) {
                fputs("\033[37m\033[42m", stdout);
            } else if((i ^ j) & 1) {
                fputs("\033[37m\033[40m", stdout);
            } else {
                fputs("\033[30m\033[47m", stdout);
            }
            if(board[i][j]) {
                printf("%3d ", board[i][j]);
            } else {
                fputs("    ", stdout);
            }
        }
        puts("\033[39m\033[49m");
    }
    fflush(stdout);
    usleep(17000);
}

static void solve_board(int x, int y) {
    int solution_num = 0;
    int board[8][8] = {0};
    int history[65] = {0};
    int step = 1;
    long try_count = 0;

    puts("\n\n\n\n\n\n\n\n\n");
    print_board(board, 0);
    board[x][y] = 1;
    do {
        if(history[step] != 8) {
            int new_x = x + OFFSETS[history[step]][0];
            int new_y = y + OFFSETS[history[step]][1];
            if(new_x >= 0 && new_x < 8 &&
               new_y >= 0 && new_y < 8 &&
               board[new_x][new_y] == 0) {
                board[new_x][new_y] = ++step;
                history[step] = 0;
                x = new_x;
                y = new_y;
                if(step == 64) {
                    print_board(board, ++solution_num);
                    try_count = 0;
                } else if(++try_count == 16777215) {
                    print_board(board, 0);
                    try_count = 0;
                }
            } else {
                ++history[step];
            }
        } else {
            board[x][y] = 0;
            --step;
            x -= OFFSETS[history[step]][0];
            y -= OFFSETS[history[step]][1];
            ++history[step];
        }
    } while(step != 0);
    if(solution_num != 0) {
        puts("All solutions found.");
    } else {
        puts("No solutions found.");
    }
}

int main() {
    int x, y;
    printf("Input starting position X Y: \033[4m");
    scanf("%d%d", &x, &y);
    fputs("\033[24m", stdout);
    solve_board(x, y);
    return 0;
}

knight.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
 
typedef unsigned char cell;
int dx[] = { -2, -2, -1, 1, 2,  2,  1, -1 };
int dy[] = { -1,  1,  2, 2, 1, -1, -2, -2 };
 
void init_board(int w, int h, cell **a, cell **b)
{
    int i, j, k, x, y, p = w + 4, q = h + 4;
    /* b is board; a is board with 2 rows padded at each side */
    a[0] = (cell*)(a + q);
    b[0] = a[0] + 2;
 
    for (i = 1; i < q; i++) {
        a[i] = a[i-1] + p;
        b[i] = a[i] + 2;
    }
 
    memset(a[0], 255, p * q);
    for (i = 0; i < h; i++) {
        for (j = 0; j < w; j++) {
            for (k = 0; k < 8; k++) {
                x = j + dx[k], y = i + dy[k];
                if (b[i+2][j] == 255) b[i+2][j] = 0;
                b[i+2][j] += x >= 0 && x < w && y >= 0 && y < h;
            }
        }
    }
}
 
static void print_board(int *board, long solution_num, int w, int h) {
    printf("\033[%dA\033[2K", h+2);
    if(solution_num != 0) {
        printf("Found solution \033[4m#%ld\033[24m:\n", solution_num);
    } else {
        puts("\033[37m\033[41mFinding a solution...\033[39m\033[49m");
    }
    fputs("\033[1m     ", stdout);
    for(int i = 0; i < w; ++i) {
        printf("%3d ", i);
    }
    fputs("\033[22m\n", stdout);
    for(int i = 0; i < h; ++i) {
        printf("\033[1m %3d \033[22m", i);
        for(int j = 0; j < w; ++j) {
            if(board[i * w + j] == w*h) {
                fputs("\033[37m\033[42m", stdout);
            } else if((i ^ j) & 1) {
                fputs("\033[37m\033[40m", stdout);
            } else {
                fputs("\033[30m\033[47m", stdout);
            }
            if(board[i * w + j]) {
                printf("%3d ", board[i * w + j]);
            } else {
                fputs("    ", stdout);
            }
        }
        puts("\033[39m\033[49m");
    }
    fflush(stdout);
    usleep(17000);
}

int walk_board(int w, int h, int x, int y, cell **b)
{
    int i, nx, ny, least;
    int steps = 0;
    int board[h][w];
    memset(board, 0, h*w*sizeof (int));

    board[y][x] = steps+1;

    while (1) {
        /* occupy cell */
        b[y][x] = 255;
 
        /* reduce all neighbors' neighbor count */
        for (i = 0; i < 8; i++)
            b[ y + dy[i] ][ x + dx[i] ]--;
 
        /* find neighbor with lowest neighbor count */
        least = 255;
        for (i = 0; i < 8; i++) {
            if (b[ y + dy[i] ][ x + dx[i] ] < least) {
                nx = x + dx[i];
                ny = y + dy[i];
                least = b[ny][nx];
            }
        }
 
        if (least > 7) {
            return steps == w * h - 1;
        }
 
        x = nx, y = ny;
        ++steps;
        board[y][x] = steps+1;
        print_board(&board[0][0], 0, w, h);
    }
}
 
int main(void)
{
    int w, h;
    printf("Input w h: ");
    scanf("%d%d", &w, &h);
    int x = 0, y = 0;
    printf("Input x y: ");
    scanf("%d%d", &x, &y);
    for(int i = 0; i < h + 2; ++i) {
        puts("");
    }
    cell **a, **b;
    a = malloc((w + 4) * (h + 4) + sizeof(cell*) * (h + 4));
    b = malloc((h + 4) * sizeof(cell*));
 
    init_board(w, h, a, b);
    if (walk_board(w, h, x, y, b + 2)) {
        return 0;
    }
    printf("Failed to find a solution\n");
    return 1;
}