1 // jumpsaround - jumper game
    2 // (c) 2011-2020 Alexander Kulbartsch
    3 // 
    4 // (slightly performace optimized version: valid jumpes checked bevore iteration.)
    5 
    6 #include <stdio.h>
    7 
    8 #define SIZEX 6
    9 #define SIZEY 5
   10 
   11 static signed int jump[8][2] = {{-1,-2}, {1,-2}, {-2,-1}, {2,-1}, {-2,1}, {2,1}, {-1,2}, {1,2}}; 
   12 
   13 char board[SIZEX][SIZEY];
   14 char iters[SIZEX*SIZEY];
   15 long int solutions; 
   16 long int roundtrips;
   17 
   18 void jumpto(signed char x, signed char y, int iter, char arity);
   19 void printboard();
   20 
   21 
   22 int main (int argc, const char * argv[]) {
   23     printf("Hello, Jumper!\n");
   24     
   25     // init
   26     for (int i = 0; i < SIZEX; i++) {
   27         for (int j = 0; j < SIZEY; j++) {
   28             board[i][j] = 0;
   29         }
   30     }
   31     for (int i = 0; i < (SIZEX*SIZEY); i++) iters[i] = 0;
   32     iters[0] = ' ';
   33 
   34     jumpto(0, 0, 1, 0);
   35     
   36     printf("I am done.\n");
   37     
   38     return 0;
   39 }
   40 
   41 
   42 void jumpto(signed char x, signed char y, int iter, char arity) {
   43 
   44     // ok - store position
   45     board[x][y] = iter;
   46     iters[iter] = arity + '0';
   47     
   48     // finished?
   49     if (iter >= SIZEX*SIZEY ) {
   50 
   51         // check for jumper roundtrips
   52         signed int round = 0;
   53         for (int i = 0; i < 8; i++) {
   54             signed char nx = x + jump[i][0]; 
   55             signed char ny = y + jump[i][1]; 
   56             // check if position is on the board
   57             if ( nx<0 || nx>(SIZEX-1) || ny<0 || ny>(SIZEY-1) ) continue;
   58             // detect roundtrip
   59             if ( board[nx][ny] == 1 ) { round = 1; roundtrips++; break; } // True
   60         }
   61 
   62         solutions++;
   63         printboard(round);
   64 
   65         board[x][y] = 0;
   66         iters[iter] = 0;
   67         return;
   68     }
   69     
   70     // try next jump
   71     for (int i = 0; i < 8; i++) {
   72         
   73         // new position
   74         signed char nx = x + jump[i][0]; 
   75         signed char ny = y + jump[i][1]; 
   76         
   77         // check if new position is on the board
   78         if ( nx<0 || nx>(SIZEX-1) || ny<0 || ny>(SIZEY-1) ) continue;
   79         
   80         //  check if new field position is still empty
   81         if ( board[nx][ny] != 0 ) continue;
   82         
   83         jumpto(nx, ny, iter + 1, i);
   84     }
   85     
   86     // this iteration is done
   87     board[x][y] = 0;
   88     iters[iter] = 0;
   89     
   90 }
   91 
   92 void printboard(int round) {
   93     printf("===== Solution # %ld - Roundtripps: %ld ====== ", solutions, roundtrips);
   94     if (round) printf(" *** Roundtrip *** ");
   95     printf("\n");
   96     for (int i = 0; i < SIZEY; i++) {
   97         for (int j = 0; j < SIZEX; j++) {
   98             printf("%2i:", board[j][i]);
   99         }
  100         printf("\n");
  101     }
  102     printf("\n");
  103 }
  104 
  105 // EOF