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