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