It's a question that shows the movement path of the chess piece knight using a stack. In chess, knight moves in an L shape. The coordinates of the chess board are horizontally represented by a to b and vertically represented by 8 to 1. If I enter the starting and arriving positions, the program should operate so that knight shows the coordinates that have passed.
But contrary to what I expected, the path that knight passed is not properly output. If I enter b7 as the starting point and e2 as the ending point, it should be output as follows:
b7 c2 e6 g7 h5 g3 e2
But it's printed out like this:
b7 e2
---
3
e2
I don't know what's wrong with it. I'd be very grateful if you could correct the code.
Next is the code I made. (I hope you don't modify the code in the gstack.c and gstack.h files.)
<gstack.h>
typedef
struct {
void * buffer ;
int unit ;
int capacity ;
int size ;
}
gstack_t ;
gstack_t *
create_stack (int capacity, int unit) ;
void
delete_stack (gstack_t * stack) ;
int
push (gstack_t * stack, void * elem) ;
int
pop (gstack_t * stack, void * elem) ;
int
is_empty (gstack_t * stack) ;
int
is_full (gstack_t * stack) ;
int
get_size (gstack_t * stack) ;
int
get_element (gstack_t * stack, int index, void * elem) ;
gstack.c
#include <stdlib.h>
#include <string.h>
#include "gstack.h"
gstack_t *
create_stack (int capacity, int unit)
{
gstack_t * st = malloc(sizeof(gstack_t)) ;
st->capacity = capacity ;
st->unit = unit ;
st->size = 0 ;
st->buffer = calloc(capacity, unit) ;
return st ;
}
void
delete_stack (gstack_t * st)
{
if (st->buffer != 0x0)
free(st->buffer) ;
free(st) ;
}
int
push (gstack_t * st, void * elem)
{
if (is_full(st))
return 0 ;
// memcpy: memory + copy(메모리의 값 복사.)
// void* memcpy(*(복사받을데), *(복사할데), size(바이트단위));
memcpy(st->buffer + ((st->size) * (st->unit)), elem, st->unit) ;
st->size += 1 ;
return 1 ;
}
int
pop (gstack_t * st, void * elem)
{
if (is_empty(st))
return 0 ;
memcpy(elem, st->buffer + (st->size - 1) * st->unit, st->unit) ;
st->size -= 1 ;
return 1 ;
}
int
is_empty (gstack_t * st)
{
return (st->size == 0) ;
}
int
is_full (gstack_t * st)
{
return (st->size == st->capacity) ;
}
int
get_size (gstack_t * st)
{
return st->size ;
}
int
get_element (gstack_t * st, int index, void * elem)
{
if (st->size <= index)
return 0 ;
memcpy(elem, st->buffer + index * st->unit, st->unit) ;
return 1 ;
}
knight.c
#include <stdio.h>
#include <stdlib.h>
#include "gstack.h"
int visited[8][8] = {0,};
typedef
enum {
// e.g U2R1: a kinght moves 2 squares Upward and 1 squares Right.
U2R1, U2L1, L2U1, L2D1, D2L1, D2R1, R2D1, R2U1
}
dir;
char departure_h;
int departure_v;
char arrival_h;
int arrival_v;
void depart_to_arrival() {
scanf(" %c %d", &departure_h, &departure_v); // input departure coordinate
scanf(" %c %d", &arrival_h, &arrival_v); // input arrival coordinate;
printf("---\n");
}
void search() {
gstack_t * hs = create_stack(64, sizeof(char)); // about horizontal coordinate (X, char a~b)
gstack_t * vs = create_stack(64, sizeof(int)); // about vertical coordinate (Y, integer 8~1)
gstack_t * ds = create_stack(64, sizeof(dir)); // about diretion ( U2R1, U2L1, ... R2U1)
int found = 0; // 목적지에 도달했는지를 나타냄.
char h = departure_h; // horizon(x)
int v = departure_v; // vertical(y)
dir d = U2R1; // direction
visited[v-1][h-'a'] = 1;
push(hs, &h);
push(vs, &v);
push(ds, &d);
while(is_empty(hs) == 0 && !found) {
pop(hs, &h); pop(vs, &v); pop(ds, &d);
if(h == arrival_h && v == arrival_v) { // check arrivial
found = 1;
push(hs, &h); push(vs, &v);
break; // end of search
}
for(dir i=d; i<=R2U1; i++) {
char nh=h;
int nv=v;
switch(i) {
case U2R1: {
nh = h+1;
nv = v+2;
break ;
}
case U2L1: {
nh = h-1;
nv = v+2;
break ;
}
case L2U1: {
nh = h-2;
nv = v+1;
break ;
}
case L2D1: {
nh = h-2;
nv = v-1;
break ;
}
case D2L1: {
nh = h-1;
nv = v-2;
break ;
}
case D2R1: {
nh = h+1;
nv = v-2;
break ;
}
case R2D1: {
nh = h+2;
nv = v-1;
break ;
}
case R2U1: {
nh = h+2;
nv = v+1;
d = U2R1;
break ;
}
default: {
continue;
}
}
if ('a'<=nh && nh <='h' && 1<=nv && nv <=8 && !visited[nv-1][nh-'a']) {
visited[nv-1][nh-'a']=1;
push(hs, &nh); push(vs, &nv);
push(ds, &i);
break;
}
}
}
if(found) {
for(int i=get_size(hs); i>=0; i--) {
char h;
int v;
get_element(hs, i, &h); get_element(vs, i, &v);
printf("%c%d\n", h, v);
}
}
else {
printf("failed.\n");
}
}
int main(void) {
depart_to_arrival();
search();
return EXIT_SUCCESS;
}
I deleted (L 43) pop() from the while statement in the search function and modified the code to pop if it doesn't meet the condition with the else statement for the if statement (L 101), i.e. pop if it's off the chessboard. But it's not working properly. I know the push isn't working properly, but I really don't know... Coding masters, please save me. Please.
The main issue is your algorithm logic: the stacks will never have more than one element. The stacks start each with one element, and then the main loop starts: in each iteration of the main loop you pop one item from each stack, and push one item on each stack. So there is no way these stacks will ever get more than one item.
It is not clear to me which algorithm you intended to implement, but as an 8x8 board only has 64 squares I would do this without stack. Instead use a visited array to indicate not only whether a square was visited, but also what the number of steps was to reach that square. You can start with the given square and apply the knight jumps to find the squares that have the next distance. As now you have not stored these results in a stack, you'll scan the visited array to locate those again, and extend them with yet another move, ...etc.
For printing the path, you'd follow the path backwards, always looking for a move that will decrease the distance. As this would print the path backwards, it is helpful to perform the first phase from end to start.
This really is a breadth-first search where the queue is replaced by scanning the board. But it guarantees you find a shortest path.
Not essential, but it may be easier to work in 1 dimension (0..63) instead of two ('a'..'h', 1..8).
Here is an implementation:
#include <stdio.h>
#include <stdlib.h>
int pair_to_square(char h, int v) {
return (h - 'a') + 8 * (v - 1);
}
void depart_to_arrival(int * departure, int * arrival) {
// Avoid globals
char departure_h;
int departure_v;
char arrival_h;
int arrival_v;
scanf(" %c %d", &departure_h, &departure_v); // input departure coordinate
scanf(" %c %d", &arrival_h, &arrival_v); // input arrival coordinate;
printf("---\n");
*departure = pair_to_square(departure_h, departure_v);
*arrival = pair_to_square(arrival_h, arrival_v);
}
int apply_jump(int square, int i) {
static int jumps[8] = {-17, -15, -10, -6, 6, 10, 15, 17};
int newsquare = square + jumps[i];
int coldiff = abs(square % 8 - newsquare % 8);
if (newsquare >= 64 || coldiff > 2) return -1;
return newsquare;
}
void search(int departure, int arrival) {
int visited[64] = {0,};
visited[arrival] = 1; // Start from the end
int distance = 1;
while (!visited[departure]) {
// Scan the board to find the squares with the current distance
for (int square = 0; square < 64; square++) {
if (visited[square] != distance) continue;
for (int i = 0; i < 8; i++) {
int newsquare = apply_jump(square, i);
if (newsquare >= 0 && !visited[newsquare]) {
// Mark the distance at the target of the played move
visited[newsquare] = distance + 1;
}
}
}
distance++;
}
// Traverse the path in opposite direction, and print it
while (distance-- > 0) {
printf("%c%d\n", 'a' + (departure % 8), (departure / 8) + 1);
for (int i = 0; i < 8; i++) {
int newsquare = apply_jump(departure, i);
if (newsquare >= 0 && visited[newsquare] == distance) {
departure = newsquare;
break;
}
}
}
}
int main(void) {
int departure, arrival;
depart_to_arrival(&departure, &arrival);
search(departure, arrival);
return EXIT_SUCCESS;
}