test/knight.c

   1 /*
   2  * Knight's Tour - a brain game
   3  *
   4  * The original of this game was anonymous.  It had an unbelievably bogus
   5  * interface, you actually had to enter square coordinates!  Redesign by
   6  * Eric S. Raymond <esr@snark.thyrsus.com> July 22 1995.  Mouse support
   7  * added September 20th 1995.
   8  *
   9  * $Id: knight.c,v 1.18 2000/10/15 18:36:34 Brian.Raiter Exp $
  10  */
  11
  12 #include <test.priv.h>
  13
  14 #include <ctype.h>
  15 #include <signal.h>
  16 #include <string.h>
  17
  18 /* board size */
  19 #define BDEPTH  8
  20 #define BWIDTH  8
  21
  22 /* where to start the instructions */
  23 #define INSTRY  2
  24 #define INSTRX  35
  25
  26 /* corner of board */
  27 #define BOARDY  2
  28 #define BOARDX  0
  29
  30 /* notification line */
  31 #define NOTIFYY 21
  32
  33 /* virtual color values */
  34 #define TRAIL_COLOR     1
  35 #define PLUS_COLOR      2
  36 #define MINUS_COLOR     3
  37
  38 #define CX(x)   (2 + 4 * (x))
  39 #define CY(y)   (1 + 2 * (y))
  40 #define cellmove(y, x)  wmove(boardwin, CY(y), CX(x))
  41 #define CXINV(x)        (((x) - 1) / 4)
  42 #define CYINV(y)        (((y) - 2) / 2)
  43
  44 typedef struct {
  45     short x, y;
  46 } cell;
  47
  48 static short board[BDEPTH][BWIDTH];     /* the squares */
  49 static int rw, col;             /* current row and column */
  50 static int lastrow, lastcol;    /* last location visited */
  51 static cell history[BDEPTH * BWIDTH + 1];       /* choice history */
  52 static int movecount;           /* count of moves so far */
  53 static WINDOW *boardwin;        /* the board window */
  54 static WINDOW *helpwin;         /* the help window */
  55 static WINDOW *msgwin;          /* the message window */
  56 static chtype trail = '#';      /* trail character */
  57 static chtype plus = '+';       /* cursor hot-spot character */
  58 static chtype minus = '-';      /* possible-move character */
  59 static chtype oldch;
  60
  61 static void init(void);
  62 static void play(void);
  63 static void dosquares(void);
  64 static void drawmove(char, int, int, int, int);
  65 static bool evalmove(int, int);
  66 static bool chkmoves(void);
  67 static bool chksqr(int, int);
  68 static int iabs(int);
  69
  70 int
  71 main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
  72 {
  73     init();
  74
  75     play();
  76
  77     endwin();
  78     return EXIT_SUCCESS;
  79 }
  80
  81 static void
  82 init(void)
  83 {
  84     srand((unsigned) getpid());
  85     initscr();
  86     cbreak();                   /* immediate char return */
  87     noecho();                   /* no immediate echo */
  88     boardwin = newwin(BDEPTH * 2 + 1, BWIDTH * 4 + 1, BOARDY, BOARDX);
  89     helpwin = newwin(0, 0, INSTRY, INSTRX);
  90     msgwin = newwin(1, INSTRX - 1, NOTIFYY, 0);
  91     scrollok(msgwin, TRUE);
  92     keypad(boardwin, TRUE);
  93
  94     if (has_colors()) {
  95         int bg = COLOR_BLACK;
  96
  97         start_color();
  98 #if HAVE_USE_DEFAULT_COLORS
  99         if (use_default_colors() == OK)
 100             bg = -1;
 101 #endif
 102
 103         (void) init_pair(TRAIL_COLOR, COLOR_CYAN, bg);
 104         (void) init_pair(PLUS_COLOR, COLOR_RED, bg);
 105         (void) init_pair(MINUS_COLOR, COLOR_GREEN, bg);
 106
 107         trail |= COLOR_PAIR(TRAIL_COLOR);
 108         plus |= COLOR_PAIR(PLUS_COLOR);
 109         minus |= COLOR_PAIR(MINUS_COLOR);
 110     }
 111 #ifdef NCURSES_MOUSE_VERSION
 112     (void) mousemask(BUTTON1_CLICKED, (mmask_t *) NULL);
 113 #endif /* NCURSES_MOUSE_VERSION */
 114
 115     oldch = minus;
 116 }
 117
 118 static void
 119 help1(void)
 120 /* game explanation -- initial help screen */
 121 {
 122     (void) waddstr(helpwin, "Knight's move is a solitaire puzzle.  Your\n");
 123     (void) waddstr(helpwin, "objective is to visit each square of the  \n");
 124     (void) waddstr(helpwin, "chessboard exactly once by making knight's\n");
 125     (void) waddstr(helpwin, "moves (one square right or left followed  \n");
 126     (void) waddstr(helpwin, "by two squares up or down, or two squares \n");
 127     (void) waddstr(helpwin, "right or left followed by one square up or\n");
 128     (void) waddstr(helpwin, "down).  You may start anywhere.\n\n");
 129
 130     (void) waddstr(helpwin, "Use arrow keys to move the cursor around.\n");
 131     (void) waddstr(helpwin, "When you want to move your knight to the \n");
 132     (void) waddstr(helpwin, "cursor location, press <space> or Enter.\n");
 133     (void) waddstr(helpwin, "Illegal moves will be rejected with an  \n");
 134     (void) waddstr(helpwin, "audible beep.\n\n");
 135     (void) waddstr(helpwin, "The program will detect if you solve the\n");
 136     (void) waddstr(helpwin, "puzzle; also inform you when you run out\n");
 137     (void) waddstr(helpwin, "of legal moves.\n\n");
 138
 139     (void) mvwaddstr(helpwin, NOTIFYY - INSTRY, 0,
 140                      "Press `?' to go to keystroke help.");
 141 }
 142
 143 static void
 144 help2(void)
 145 /* keystroke help screen */
 146 {
 147     (void) waddstr(helpwin, "Possible moves are shown with `-'.\n\n");
 148
 149     (void) waddstr(helpwin, "You can move around with the arrow keys or\n");
 150     (void) waddstr(helpwin, "with the rogue/hack movement keys.  Other\n");
 151     (void) waddstr(helpwin, "commands allow you to undo moves or redraw.\n");
 152     (void) waddstr(helpwin, "Your mouse may work; try left-button to\n");
 153     (void) waddstr(helpwin, "move to the square under the pointer.\n\n");
 154
 155     (void) waddstr(helpwin, "x,q -- exit             y k u    7 8 9\n");
 156     (void) waddstr(helpwin, "r -- redraw screen       \\|/      \\|/ \n");
 157     (void) waddstr(helpwin, "bksp -- undo move       h-+-l    4-+-6\n");
 158     (void) waddstr(helpwin, "                         /|\\      /|\\ \n");
 159     (void) waddstr(helpwin, "                        b j n    1 2 3\n");
 160
 161     (void) waddstr(helpwin, "\nYou can place your knight on the selected\n");
 162     (void) waddstr(helpwin, "square with spacebar, Enter, or the keypad\n");
 163     (void) waddstr(helpwin, "center key.  You can quit with `x' or `q'.\n");
 164
 165     (void) mvwaddstr(helpwin, NOTIFYY - INSTRY, 0,
 166                      "Press `?' to go to game explanation");
 167 }
 168
 169 static void
 170 play(void)
 171 /* play the game */
 172 {
 173     bool keyhelp;               /* TRUE if keystroke help is up */
 174     int c, ny = 0, nx = 0;
 175     int i, j, count;
 176
 177     do {
 178         /* clear screen and draw board */
 179         werase(boardwin);
 180         werase(helpwin);
 181         werase(msgwin);
 182         dosquares();
 183         help1();
 184         wnoutrefresh(stdscr);
 185         wnoutrefresh(helpwin);
 186         wnoutrefresh(msgwin);
 187         wnoutrefresh(boardwin);
 188         doupdate();
 189
 190         for (i = 0; i < BDEPTH; i++)
 191             for (j = 0; j < BWIDTH; j++) {
 192                 board[i][j] = FALSE;
 193                 cellmove(i, j);
 194                 waddch(boardwin, minus);
 195             }
 196         memset(history, '\0', sizeof(history));
 197         history[0].y = history[0].x = -1;
 198         lastrow = lastcol = -2;
 199         movecount = 1;
 200         keyhelp = FALSE;
 201
 202         for (;;) {
 203             if (rw != lastrow || col != lastcol) {
 204                 if (lastrow >= 0 && lastcol >= 0) {
 205                     cellmove(lastrow, lastcol);
 206                     if (board[lastrow][lastcol])
 207                         waddch(boardwin, trail);
 208                     else
 209                         waddch(boardwin, oldch);
 210                 }
 211
 212                 cellmove(rw, col);
 213                 oldch = winch(boardwin);
 214
 215                 lastrow = rw;
 216                 lastcol = col;
 217             }
 218             cellmove(rw, col);
 219             waddch(boardwin, plus);
 220             cellmove(rw, col);
 221
 222             wrefresh(msgwin);
 223
 224             c = wgetch(boardwin);
 225
 226             werase(msgwin);
 227
 228             switch (c) {
 229             case 'k':
 230             case '8':
 231             case KEY_UP:
 232                 ny = rw + BDEPTH - 1;
 233                 nx = col;
 234                 break;
 235             case 'j':
 236             case '2':
 237             case KEY_DOWN:
 238                 ny = rw + 1;
 239                 nx = col;
 240                 break;
 241             case 'h':
 242             case '4':
 243             case KEY_LEFT:
 244                 ny = rw;
 245                 nx = col + BWIDTH - 1;
 246                 break;
 247             case 'l':
 248             case '6':
 249             case KEY_RIGHT:
 250                 ny = rw;
 251                 nx = col + 1;
 252                 break;
 253             case 'y':
 254             case '7':
 255             case KEY_A1:
 256                 ny = rw + BDEPTH - 1;
 257                 nx = col + BWIDTH - 1;
 258                 break;
 259             case 'b':
 260             case '1':
 261             case KEY_C1:
 262                 ny = rw + 1;
 263                 nx = col + BWIDTH - 1;
 264                 break;
 265             case 'u':
 266             case '9':
 267             case KEY_A3:
 268                 ny = rw + BDEPTH - 1;
 269                 nx = col + 1;
 270                 break;
 271             case 'n':
 272             case '3':
 273             case KEY_C3:
 274                 ny = rw + 1;
 275                 nx = col + 1;
 276                 break;
 277
 278 #ifdef NCURSES_MOUSE_VERSION
 279             case KEY_MOUSE:
 280                 {
 281                     MEVENT myevent;
 282
 283                     getmouse(&myevent);
 284                     if (myevent.y >= CY(0) && myevent.y <= CY(BDEPTH)
 285                         && myevent.x >= CX(0) && myevent.x <= CX(BWIDTH)) {
 286                         nx = CXINV(myevent.x);
 287                         ny = CYINV(myevent.y);
 288                         ungetch('\n');
 289                         break;
 290                     } else {
 291                         beep();
 292                         continue;
 293                     }
 294                 }
 295 #endif /* NCURSES_MOUSE_VERSION */
 296
 297             case KEY_B2:
 298             case '\n':
 299             case ' ':
 300                 if (evalmove(rw, col)) {
 301                     drawmove(trail,
 302                              history[movecount - 1].y,
 303                              history[movecount - 1].x,
 304                              rw, col);
 305                     history[movecount].y = rw;
 306                     history[movecount].x = col;
 307                     movecount++;
 308
 309                     if (!chkmoves())
 310                         goto dropout;
 311                 } else
 312                     beep();
 313                 break;
 314
 315             case KEY_REDO:
 316             case '\f':
 317             case 'r':
 318                 clearok(curscr, TRUE);
 319                 wnoutrefresh(stdscr);
 320                 wnoutrefresh(boardwin);
 321                 wnoutrefresh(msgwin);
 322                 wnoutrefresh(helpwin);
 323                 doupdate();
 324                 break;
 325
 326             case KEY_UNDO:
 327             case KEY_BACKSPACE:
 328             case '\b':
 329                 if (movecount == 1) {
 330                     ny = lastrow;
 331                     nx = lastcol;
 332                     waddstr(msgwin, "\nNo previous move.");
 333                     beep();
 334                 } else {
 335                     int oldy = history[movecount - 1].y;
 336                     int oldx = history[movecount - 1].x;
 337
 338                     board[oldy][oldx] = FALSE;
 339                     --movecount;
 340                     ny = history[movecount - 1].y;
 341                     nx = history[movecount - 1].x;
 342                     drawmove(' ', oldy, oldx, ny, nx);
 343
 344                     /* avoid problems if we just changed the current cell */
 345                     cellmove(lastrow, lastcol);
 346                     oldch = winch(boardwin);
 347                 }
 348                 break;
 349
 350             case 'q':
 351             case 'x':
 352                 goto dropout;
 353
 354             case '?':
 355                 werase(helpwin);
 356                 if (keyhelp) {
 357                     help1();
 358                     keyhelp = FALSE;
 359                 } else {
 360                     help2();
 361                     keyhelp = TRUE;
 362                 }
 363                 wrefresh(helpwin);
 364                 break;
 365
 366             default:
 367                 beep();
 368                 break;
 369             }
 370
 371             col = nx % BWIDTH;
 372             rw = ny % BDEPTH;
 373         }
 374
 375       dropout:
 376         count = 0;
 377         for (i = 0; i < BDEPTH; i++)
 378             for (j = 0; j < BWIDTH; j++)
 379                 if (board[i][j] != 0)
 380                     count += 1;
 381         if (count == (BWIDTH * BDEPTH))
 382             wprintw(msgwin, "\nYou won.  Care to try again? ");
 383         else
 384             wprintw(msgwin, "\n%d squares filled.  Try again? ", count);
 385     } while
 386         (tolower(wgetch(msgwin)) == 'y');
 387 }
 388
 389 static void
 390 dosquares(void)
 391 {
 392     int i, j;
 393
 394     mvaddstr(0, 20, "KNIGHT'S MOVE -- a logical solitaire");
 395
 396     move(BOARDY, BOARDX);
 397     waddch(boardwin, ACS_ULCORNER);
 398     for (j = 0; j < 7; j++) {
 399         waddch(boardwin, ACS_HLINE);
 400         waddch(boardwin, ACS_HLINE);
 401         waddch(boardwin, ACS_HLINE);
 402         waddch(boardwin, ACS_TTEE);
 403     }
 404     waddch(boardwin, ACS_HLINE);
 405     waddch(boardwin, ACS_HLINE);
 406     waddch(boardwin, ACS_HLINE);
 407     waddch(boardwin, ACS_URCORNER);
 408
 409     for (i = 1; i < BDEPTH; i++) {
 410         move(BOARDY + i * 2 - 1, BOARDX);
 411         waddch(boardwin, ACS_VLINE);
 412         for (j = 0; j < BWIDTH; j++) {
 413             waddch(boardwin, ' ');
 414             waddch(boardwin, ' ');
 415             waddch(boardwin, ' ');
 416             waddch(boardwin, ACS_VLINE);
 417         }
 418         move(BOARDY + i * 2, BOARDX);
 419         waddch(boardwin, ACS_LTEE);
 420         for (j = 0; j < BWIDTH - 1; j++) {
 421             waddch(boardwin, ACS_HLINE);
 422             waddch(boardwin, ACS_HLINE);
 423             waddch(boardwin, ACS_HLINE);
 424             waddch(boardwin, ACS_PLUS);
 425         }
 426         waddch(boardwin, ACS_HLINE);
 427         waddch(boardwin, ACS_HLINE);
 428         waddch(boardwin, ACS_HLINE);
 429         waddch(boardwin, ACS_RTEE);
 430     }
 431
 432     move(BOARDY + i * 2 - 1, BOARDX);
 433     waddch(boardwin, ACS_VLINE);
 434     for (j = 0; j < BWIDTH; j++) {
 435         waddch(boardwin, ' ');
 436         waddch(boardwin, ' ');
 437         waddch(boardwin, ' ');
 438         waddch(boardwin, ACS_VLINE);
 439     }
 440
 441     move(BOARDY + i * 2, BOARDX);
 442     waddch(boardwin, ACS_LLCORNER);
 443     for (j = 0; j < BWIDTH - 1; j++) {
 444         waddch(boardwin, ACS_HLINE);
 445         waddch(boardwin, ACS_HLINE);
 446         waddch(boardwin, ACS_HLINE);
 447         waddch(boardwin, ACS_BTEE);
 448     }
 449     waddch(boardwin, ACS_HLINE);
 450     waddch(boardwin, ACS_HLINE);
 451     waddch(boardwin, ACS_HLINE);
 452     waddch(boardwin, ACS_LRCORNER);
 453 }
 454
 455 static void
 456 mark_possibles(int prow, int pcol, chtype mark)
 457 {
 458     if (chksqr(prow + 2, pcol + 1)) {
 459         cellmove(prow + 2, pcol + 1);
 460         waddch(boardwin, mark);
 461     };
 462     if (chksqr(prow + 2, pcol - 1)) {
 463         cellmove(prow + 2, pcol - 1);
 464         waddch(boardwin, mark);
 465     };
 466     if (chksqr(prow - 2, pcol + 1)) {
 467         cellmove(prow - 2, pcol + 1);
 468         waddch(boardwin, mark);
 469     };
 470     if (chksqr(prow - 2, pcol - 1)) {
 471         cellmove(prow - 2, pcol - 1);
 472         waddch(boardwin, mark);
 473     };
 474     if (chksqr(prow + 1, pcol + 2)) {
 475         cellmove(prow + 1, pcol + 2);
 476         waddch(boardwin, mark);
 477     };
 478     if (chksqr(prow + 1, pcol - 2)) {
 479         cellmove(prow + 1, pcol - 2);
 480         waddch(boardwin, mark);
 481     };
 482     if (chksqr(prow - 1, pcol + 2)) {
 483         cellmove(prow - 1, pcol + 2);
 484         waddch(boardwin, mark);
 485     };
 486     if (chksqr(prow - 1, pcol - 2)) {
 487         cellmove(prow - 1, pcol - 2);
 488         waddch(boardwin, mark);
 489     };
 490 }
 491
 492 static void
 493 drawmove(char tchar, int oldy, int oldx, int row, int column)
 494 /* place the stars, update board & currents */
 495 {
 496     if (movecount <= 1) {
 497         int i, j;
 498
 499         for (i = 0; i < BDEPTH; i++)
 500             for (j = 0; j < BWIDTH; j++) {
 501                 cellmove(i, j);
 502                 if (winch(boardwin) == minus)
 503                     waddch(boardwin, movecount ? ' ' : minus);
 504             }
 505     } else {
 506         cellmove(oldy, oldx);
 507         waddch(boardwin, '\b');
 508         waddch(boardwin, tchar);
 509         waddch(boardwin, tchar);
 510         waddch(boardwin, tchar);
 511         mark_possibles(oldy, oldx, ' ');
 512     }
 513
 514     if (row != -1 && column != -1) {
 515         cellmove(row, column);
 516         waddch(boardwin, '\b');
 517         waddch(boardwin, trail);
 518         waddch(boardwin, trail);
 519         waddch(boardwin, trail);
 520         mark_possibles(row, column, minus);
 521         board[row][column] = TRUE;
 522     }
 523
 524     wprintw(msgwin, "\nMove %d", movecount);
 525 }
 526
 527 static bool
 528 evalmove(int row, int column)
 529 /* evaluate move */
 530 {
 531     if (movecount == 1)
 532         return (TRUE);
 533     else if (board[row][column] == TRUE) {
 534         waddstr(msgwin, "\nYou've already been there.");
 535         return (FALSE);
 536     } else {
 537         int rdif = iabs(row - history[movecount - 1].y);
 538         int cdif = iabs(column - history[movecount - 1].x);
 539
 540         if (!((rdif == 1) && (cdif == 2)) && !((rdif == 2) && (cdif == 1))) {
 541             waddstr(msgwin, "\nThat's not a legal knight's move.");
 542             return (FALSE);
 543         }
 544     }
 545
 546     return (TRUE);
 547 }
 548
 549 static bool
 550 chkmoves(void)
 551 /* check to see if valid moves are available */
 552 {
 553     if (chksqr(rw + 2, col + 1))
 554         return (TRUE);
 555     if (chksqr(rw + 2, col - 1))
 556         return (TRUE);
 557     if (chksqr(rw - 2, col + 1))
 558         return (TRUE);
 559     if (chksqr(rw - 2, col - 1))
 560         return (TRUE);
 561     if (chksqr(rw + 1, col + 2))
 562         return (TRUE);
 563     if (chksqr(rw + 1, col - 2))
 564         return (TRUE);
 565     if (chksqr(rw - 1, col + 2))
 566         return (TRUE);
 567     if (chksqr(rw - 1, col - 2))
 568         return (TRUE);
 569     return (FALSE);
 570 }
 571
 572 static int
 573 iabs(int num)
 574 {
 575     if (num < 0)
 576         return (-num);
 577     else
 578         return (num);
 579 }
 580
 581 static bool
 582 chksqr(int r1, int c1)
 583 {
 584     if ((r1 < 0) || (r1 > BDEPTH - 1))
 585         return (FALSE);
 586     if ((c1 < 0) || (c1 > BWIDTH - 1))
 587         return (FALSE);
 588     return ((!board[r1][c1]) ? TRUE : FALSE);
 589 }
 590
 591 /* knight.c ends here */