test/knight.c

   1 /****************************************************************************
   2  * Copyright (c) 1998-2018,2019 Free Software Foundation, Inc.              *
   3  *                                                                          *
   4  * Permission is hereby granted, free of charge, to any person obtaining a  *
   5  * copy of this software and associated documentation files (the            *
   6  * "Software"), to deal in the Software without restriction, including      *
   7  * without limitation the rights to use, copy, modify, merge, publish,      *
   8  * distribute, distribute with modifications, sublicense, and/or sell       *
   9  * copies of the Software, and to permit persons to whom the Software is    *
  10  * furnished to do so, subject to the following conditions:                 *
  11  *                                                                          *
  12  * The above copyright notice and this permission notice shall be included  *
  13  * in all copies or substantial portions of the Software.                   *
  14  *                                                                          *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS  *
  16  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF               *
  17  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.   *
  18  * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,   *
  19  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR    *
  20  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR    *
  21  * THE USE OR OTHER DEALINGS IN THE SOFTWARE.                               *
  22  *                                                                          *
  23  * Except as contained in this notice, the name(s) of the above copyright   *
  24  * holders shall not be used in advertising or otherwise to promote the     *
  25  * sale, use or other dealings in this Software without prior written       *
  26  * authorization.                                                           *
  27  ****************************************************************************/
  28 /*
  29  * Knight's Tour - a brain game
  30  *
  31  * The original of this game was anonymous.  It had an unbelievably bogus
  32  * interface, you actually had to enter square coordinates!  Redesign by
  33  * Eric S. Raymond <esr@snark.thyrsus.com> July 22 1995.  Mouse support
  34  * added September 20th 1995.
  35  *
  36  * $Id: knight.c,v 1.46 2019/08/24 22:40:52 tom Exp $
  37  */
  38
  39 #include <test.priv.h>
  40
  41 /* board size */
  42 #define YLIMIT          8
  43 #define XLIMIT          8
  44 #define MAXMOVES        (ylimit * xlimit)
  45
  46 /* where to start the instructions */
  47 #define INSTRY          2
  48 #define INSTRX          35
  49
  50 /* corner of board */
  51 #define BOARDY          2
  52 #define BOARDX          0
  53
  54 /* notification line */
  55 #define NOTIFYY         21
  56
  57 /* virtual color values */
  58 #define TRAIL_COLOR     1
  59 #define PLUS_COLOR      2
  60 #define MINUS_COLOR     3
  61
  62 #define CX(x)           (2 + 4 * (x))
  63 #define CY(y)           (1 + 2 * (y))
  64 #define cellmove(y, x)  wmove(boardwin, CY(y), CX(x))
  65 #define CXINV(x)        (((x) - 1) / 4)
  66 #define CYINV(y)        (((y) - 2) / 2)
  67
  68 typedef struct {
  69     int x, y;
  70 } HISTORY;
  71
  72 typedef int SQUARES[YLIMIT][XLIMIT];
  73
  74 static WINDOW *boardwin;        /* the board window */
  75 static WINDOW *helpwin;         /* the help window */
  76 static WINDOW *msgwin;          /* the message window */
  77
  78 #if HAVE_USE_DEFAULT_COLORS
  79 static bool d_option;
  80 #endif
  81
  82 static chtype minus = '-';      /* possible-move character */
  83 static chtype oldch;
  84 static chtype plus = '+';       /* cursor hot-spot character */
  85 static chtype trail = '#';      /* trail character */
  86
  87 static int ylimit = YLIMIT;
  88 static int xlimit = XLIMIT;
  89 static int maxmoves = (YLIMIT * XLIMIT);
  90
  91 static int count_tries;         /* count of trials so far */
  92 static int test_test;           /* FIXME */
  93 /* *INDENT-OFF* */
  94 static const struct {
  95     int y;
  96     int x;
  97 } offsets[] = {
  98     {  2,  1 },
  99     {  1,  2 },
 100     { -1,  2 },
 101     { -2,  1 },
 102     { -2, -1 },
 103     { -1, -2 },
 104     {  1, -2 },
 105     {  2, -1 },
 106 };
 107 #define MAX_OFFSET      (unsigned)SIZEOF(offsets)
 108 /* *INDENT-ON* */
 109
 110 static void
 111 init_program(void)
 112 {
 113     setlocale(LC_ALL, "");
 114
 115     srand((unsigned) getpid());
 116     initscr();
 117     cbreak();                   /* immediate char return */
 118     noecho();                   /* no immediate echo */
 119
 120     maxmoves = MAXMOVES;
 121     boardwin = newwin(ylimit * 2 + 1, xlimit * 4 + 1, BOARDY, BOARDX);
 122     helpwin = newwin(0, 0, INSTRY, INSTRX);
 123     msgwin = newwin(1, INSTRX - 1, NOTIFYY, 0);
 124
 125     scrollok(msgwin, TRUE);
 126     keypad(boardwin, TRUE);
 127
 128     if (has_colors()) {
 129         int bg = COLOR_BLACK;
 130
 131         start_color();
 132 #if HAVE_USE_DEFAULT_COLORS
 133         if (d_option && (use_default_colors() == OK))
 134             bg = -1;
 135 #endif
 136
 137         (void) init_pair(TRAIL_COLOR, (short) COLOR_CYAN, (short) bg);
 138         (void) init_pair(PLUS_COLOR, (short) COLOR_RED, (short) bg);
 139         (void) init_pair(MINUS_COLOR, (short) COLOR_GREEN, (short) bg);
 140
 141         trail |= (chtype) COLOR_PAIR(TRAIL_COLOR);
 142         plus |= (chtype) COLOR_PAIR(PLUS_COLOR);
 143         minus |= (chtype) COLOR_PAIR(MINUS_COLOR);
 144     }
 145 #ifdef NCURSES_MOUSE_VERSION
 146     (void) mousemask(BUTTON1_CLICKED, (mmask_t *) NULL);
 147 #endif /* NCURSES_MOUSE_VERSION */
 148 #if defined(PDCURSES)
 149     mouse_set(BUTTON1_RELEASED);
 150 #endif
 151
 152     oldch = minus;
 153 }
 154
 155 static void
 156 help1(void)
 157 /* game explanation -- initial help screen */
 158 {
 159     (void) waddstr(helpwin, "Knight's move is a solitaire puzzle.  Your\n");
 160     (void) waddstr(helpwin, "objective is to visit each square of the  \n");
 161     (void) waddstr(helpwin, "chessboard exactly once by making knight's\n");
 162     (void) waddstr(helpwin, "moves (one square right or left followed  \n");
 163     (void) waddstr(helpwin, "by two squares up or down, or two squares \n");
 164     (void) waddstr(helpwin, "right or left followed by one square up or\n");
 165     (void) waddstr(helpwin, "down).  You may start anywhere.\n\n");
 166
 167     (void) waddstr(helpwin, "Use arrow keys to move the cursor around.\n");
 168     (void) waddstr(helpwin, "When you want to move your knight to the \n");
 169     (void) waddstr(helpwin, "cursor location, press <space> or Enter.\n");
 170     (void) waddstr(helpwin, "Illegal moves will be rejected with an  \n");
 171     (void) waddstr(helpwin, "audible beep.\n\n");
 172     (void) waddstr(helpwin, "The program will detect if you solve the\n");
 173     (void) waddstr(helpwin, "puzzle; also inform you when you run out\n");
 174     (void) waddstr(helpwin, "of legal moves.\n\n");
 175
 176     MvWAddStr(helpwin, NOTIFYY - INSTRY, 0,
 177               "Press `?' to go to keystroke help.");
 178 }
 179
 180 static void
 181 help2(void)
 182 /* keystroke help screen */
 183 {
 184     (void) waddstr(helpwin, "Possible moves are shown with `-'.\n\n");
 185
 186     (void) waddstr(helpwin, "You can move around with the arrow keys or\n");
 187     (void) waddstr(helpwin, "with the rogue/hack movement keys.  Other\n");
 188     (void) waddstr(helpwin, "commands allow you to undo moves or redraw.\n");
 189     (void) waddstr(helpwin, "Your mouse may work; try left-button to\n");
 190     (void) waddstr(helpwin, "move to the square under the pointer.\n\n");
 191
 192     (void) waddstr(helpwin, "x,q -- exit             y k u    7 8 9\n");
 193     (void) waddstr(helpwin, "r -- redraw screen       \\|/      \\|/ \n");
 194     (void) waddstr(helpwin, "bksp -- undo move       h-+-l    4-+-6\n");
 195     (void) waddstr(helpwin, "a -- autojump            /|\\      /|\\ \n");
 196     if (ylimit <= 6) {
 197         (void) waddstr(helpwin, "R -- solve (slow)       b j n    1 2 3\n");
 198     } else {
 199         (void) waddstr(helpwin, "                        b j n    1 2 3\n");
 200     }
 201
 202     (void) waddstr(helpwin, "\nYou can place your knight on the selected\n");
 203     (void) waddstr(helpwin, "square with spacebar, Enter, or the keypad\n");
 204     (void) waddstr(helpwin, "center key.  Use F/B to review the path.\n");
 205
 206     MvWAddStr(helpwin, NOTIFYY - INSTRY, 0,
 207               "Press `?' to go to game explanation");
 208 }
 209
 210 static void
 211 show_help(bool * keyhelp)
 212 {
 213     werase(helpwin);
 214     if (*keyhelp) {
 215         help1();
 216         *keyhelp = FALSE;
 217     } else {
 218         help2();
 219         *keyhelp = TRUE;
 220     }
 221     wrefresh(helpwin);
 222 }
 223
 224 static inline bool
 225 isValidYX(int y, int x)
 226 {
 227     return (y >= 0 && y < ylimit && x >= 0 && x < xlimit) ? TRUE : FALSE;
 228 }
 229
 230 static inline bool
 231 isUnusedYX(SQUARES squares, int y, int x)
 232 {
 233     return (isValidYX(y, x) && (!squares[y][x]) ? TRUE : FALSE);
 234 }
 235
 236 static bool
 237 boardIsFilled(SQUARES squares, int y, int x)
 238 {
 239     unsigned n;
 240
 241     for (n = 0; n < MAX_OFFSET; n++) {
 242         if (isUnusedYX(squares, y + offsets[n].y, x + offsets[n].x)) {
 243             return FALSE;
 244         }
 245     }
 246     return TRUE;
 247 }
 248
 249 static void
 250 drawBoard(void)
 251 {
 252     int i, j;
 253
 254     MvAddStr(0, 20, "KNIGHT'S MOVE -- a logical solitaire");
 255
 256     move(BOARDY, BOARDX);
 257     waddch(boardwin, ACS_ULCORNER);
 258     for (j = 0; j < (ylimit - 1); j++) {
 259         waddch(boardwin, ACS_HLINE);
 260         waddch(boardwin, ACS_HLINE);
 261         waddch(boardwin, ACS_HLINE);
 262         waddch(boardwin, ACS_TTEE);
 263     }
 264     waddch(boardwin, ACS_HLINE);
 265     waddch(boardwin, ACS_HLINE);
 266     waddch(boardwin, ACS_HLINE);
 267     waddch(boardwin, ACS_URCORNER);
 268
 269     for (i = 1; i < ylimit; i++) {
 270         move(BOARDY + i * 2 - 1, BOARDX);
 271         waddch(boardwin, ACS_VLINE);
 272         for (j = 0; j < xlimit; j++) {
 273             waddch(boardwin, ' ');
 274             waddch(boardwin, ' ');
 275             waddch(boardwin, ' ');
 276             waddch(boardwin, ACS_VLINE);
 277         }
 278         move(BOARDY + i * 2, BOARDX);
 279         waddch(boardwin, ACS_LTEE);
 280         for (j = 0; j < xlimit - 1; j++) {
 281             waddch(boardwin, ACS_HLINE);
 282             waddch(boardwin, ACS_HLINE);
 283             waddch(boardwin, ACS_HLINE);
 284             waddch(boardwin, ACS_PLUS);
 285         }
 286         waddch(boardwin, ACS_HLINE);
 287         waddch(boardwin, ACS_HLINE);
 288         waddch(boardwin, ACS_HLINE);
 289         waddch(boardwin, ACS_RTEE);
 290     }
 291
 292     move(BOARDY + i * 2 - 1, BOARDX);
 293     waddch(boardwin, ACS_VLINE);
 294     for (j = 0; j < xlimit; j++) {
 295         waddch(boardwin, ' ');
 296         waddch(boardwin, ' ');
 297         waddch(boardwin, ' ');
 298         waddch(boardwin, ACS_VLINE);
 299     }
 300
 301     move(BOARDY + i * 2, BOARDX);
 302     waddch(boardwin, ACS_LLCORNER);
 303     for (j = 0; j < xlimit - 1; j++) {
 304         waddch(boardwin, ACS_HLINE);
 305         waddch(boardwin, ACS_HLINE);
 306         waddch(boardwin, ACS_HLINE);
 307         waddch(boardwin, ACS_BTEE);
 308     }
 309     waddch(boardwin, ACS_HLINE);
 310     waddch(boardwin, ACS_HLINE);
 311     waddch(boardwin, ACS_HLINE);
 312     waddch(boardwin, ACS_LRCORNER);
 313 }
 314
 315 static void
 316 mark_possibles(SQUARES squares, int y, int x, chtype mark)
 317 {
 318     unsigned n;
 319
 320     for (n = 0; n < MAX_OFFSET; n++) {
 321         if (isUnusedYX(squares, y + offsets[n].y, x + offsets[n].x)) {
 322             cellmove(y + offsets[n].y, x + offsets[n].x);
 323             waddch(boardwin, mark);
 324         }
 325     }
 326 }
 327
 328 static bool
 329 find_next_move(SQUARES squares, HISTORY * doneData, int doneSize, int *y, int *x)
 330 {
 331     bool result = FALSE;
 332
 333     if (doneSize > 1) {
 334         unsigned j;
 335         int oldy = doneData[doneSize - 1].y;
 336         int oldx = doneData[doneSize - 1].x;
 337         int found = -1;
 338         int first = -1;
 339         int next = -1;
 340
 341         for (j = 0; j < MAX_OFFSET * 2; j++) {
 342             unsigned k = j % MAX_OFFSET;
 343             int newy = oldy + offsets[k].y;
 344             int newx = oldx + offsets[k].x;
 345             if (isUnusedYX(squares, newy, newx)) {
 346                 if (first < 0)
 347                     first = (int) k;
 348                 if (newy == *y
 349                     && newx == *x) {
 350                     found = (int) k;
 351                 } else if (found >= 0) {
 352                     next = (int) k;
 353                     break;
 354                 }
 355             }
 356         }
 357         if (found < 0)
 358             next = first;
 359         if (next >= 0) {
 360             *y = oldy + offsets[next].y;
 361             *x = oldx + offsets[next].x;
 362         }
 363         result = TRUE;
 364     }
 365     return result;
 366 }
 367
 368 static void
 369 count_next_moves(SQUARES squares, int count_moves, int y, int x)
 370 {
 371     int count = 0;
 372     unsigned j;
 373
 374     wprintw(msgwin, "\nMove %d", count_moves);
 375     for (j = 0; j < MAX_OFFSET; j++) {
 376         int newy = y + offsets[j].y;
 377         int newx = x + offsets[j].x;
 378         if (isUnusedYX(squares, newy, newx)) {
 379             ++count;
 380         }
 381     }
 382     wprintw(msgwin, ", gives %d choices", count);
 383     wclrtoeol(msgwin);
 384 }
 385
 386 static void
 387 unmarkcell(int row, int column)
 388 {
 389     cellmove(row, column);
 390     waddch(boardwin, '\b');
 391     waddch(boardwin, ' ');
 392     waddch(boardwin, minus);
 393     waddch(boardwin, ' ');
 394 }
 395
 396 static void
 397 markcell(chtype tchar, int row, int column)
 398 {
 399     cellmove(row, column);
 400     waddch(boardwin, '\b');
 401     waddch(boardwin, tchar);
 402     waddch(boardwin, tchar);
 403     waddch(boardwin, tchar);
 404 }
 405
 406 static void
 407 drawMove(SQUARES squares, int count_moves, chtype tchar, int oldy, int oldx, int
 408          row, int column)
 409 /* place the stars, update board & currents */
 410 {
 411     if (count_moves <= 1) {
 412         int i, j;
 413
 414         for (i = 0; i < ylimit; i++) {
 415             for (j = 0; j < xlimit; j++) {
 416                 if (count_moves == 0) {
 417                     unmarkcell(i, j);
 418                 } else {
 419                     cellmove(i, j);
 420                     if (winch(boardwin) == minus)
 421                         waddch(boardwin, ' ');
 422                 }
 423             }
 424         }
 425     } else {
 426         markcell(tchar, oldy, oldx);
 427         mark_possibles(squares, oldy, oldx, ' ');
 428     }
 429
 430     if (row >= 0 && column >= 0) {
 431         markcell(trail, row, column);
 432         mark_possibles(squares, row, column, minus);
 433         squares[row][column] = TRUE;
 434     }
 435
 436     wprintw(msgwin, "\nMove %d", count_moves);
 437     if (count_tries != count_moves)
 438         wprintw(msgwin, " (%d tries)", count_tries);
 439     wclrtoeol(msgwin);
 440 }
 441
 442 static int
 443 iabs(int num)
 444 {
 445     if (num < 0)
 446         return (-num);
 447     else
 448         return (num);
 449 }
 450
 451 static bool
 452 evaluate_move(SQUARES squares, HISTORY * doneData, int doneSize, int row, int column)
 453 {
 454     if (doneSize <= 1)
 455         return (TRUE);
 456     else if (squares[row][column] == TRUE) {
 457         waddstr(msgwin, "\nYou've already been there.");
 458         return (FALSE);
 459     } else {
 460         int rdif = iabs(row - doneData[doneSize - 1].y);
 461         int cdif = iabs(column - doneData[doneSize - 1].x);
 462
 463         if (!((rdif == 1) && (cdif == 2)) && !((rdif == 2) && (cdif == 1))) {
 464             waddstr(msgwin, "\nThat's not a legal knight's move.");
 465             return (FALSE);
 466         }
 467     }
 468
 469     return (TRUE);
 470 }
 471
 472 static int
 473 completed(SQUARES squares)
 474 {
 475     int i, j, count = 0;
 476
 477     for (i = 0; i < ylimit; i++) {
 478         for (j = 0; j < xlimit; j++) {
 479             if (squares[i][j] != 0) {
 480                 count += 1;
 481             }
 482         }
 483     }
 484     return ((count == maxmoves) ? -1 : count);
 485 }
 486
 487 static void
 488 no_previous_move(void)
 489 {
 490     waddstr(msgwin, "\nNo previous move.");
 491     beep();
 492 }
 493
 494 /* Recursively try all possible moves, starting from (y,x) */
 495 static int
 496 recurBack(SQUARES squares, int y, int x, int total)
 497 {
 498     int longest = total;
 499     int best_x = x;
 500     int best_y = y;
 501     int result;
 502
 503     if (total < maxmoves) {
 504         unsigned k;
 505
 506         for (k = 0; k < MAX_OFFSET; k++) {
 507             int try_x = x + offsets[k].x;
 508             int try_y = y + offsets[k].y;
 509             if (isUnusedYX(squares, try_y, try_x)) {
 510                 ++test_test;
 511                 squares[try_y][try_x] = total + 1;
 512                 result = recurBack(squares, try_y, try_x, total + 1);
 513                 if (result > longest) {
 514                     longest = result;
 515                     best_x = try_x;
 516                     best_y = try_y;
 517                 }
 518                 if (result >= maxmoves)
 519                     break;
 520                 squares[try_y][try_x] = 0;      /* allow retry... */
 521             }
 522         }
 523     }
 524
 525     result = total;
 526     if (longest > total) {
 527         result = longest;
 528         squares[best_y][best_x] = total + 1;
 529         (void) recurBack(squares, best_y, best_x, total + 1);
 530         if (result < maxmoves)
 531             squares[best_y][best_x] = 0;
 532     }
 533
 534     return result;
 535 }
 536
 537 /*
 538  * Solve the Knight Tour problem using backtracking, returning the length of
 539  * the resulting solution.  If this is invoked from a point where the remaining
 540  * choices cannot complete the tour, the result will fall short.
 541  */
 542 static int
 543 useBacktracking(SQUARES result, HISTORY * doneData, int doneSize)
 544 {
 545     int y = 0, x = 0, n;
 546     SQUARES squares;
 547     int total;
 548     int actual = doneSize - 1;
 549
 550     memset(squares, 0, sizeof(squares));
 551     for (n = 1; n <= actual; ++n) {
 552         y = doneData[n].y;
 553         x = doneData[n].x;
 554         squares[y][x] = n;
 555     }
 556
 557     total = recurBack(squares, y, x, actual);
 558     if (total > actual) {
 559         for (y = 0; y < ylimit; ++y) {
 560             for (x = 0; x < xlimit; ++x) {
 561                 result[y][x] = squares[y][x];
 562                 if ((n = squares[y][x]) != 0) {
 563                     doneData[n].y = y;
 564                     doneData[n].x = x;
 565                 }
 566             }
 567         }
 568     }
 569     return total;
 570 }
 571
 572 static int
 573 reviewHistory(HISTORY * history, int count_moves, int review, int *ny, int *nx)
 574 {
 575     if (review < 0) {
 576         beep();
 577         review = 0;
 578     } else if (review > count_moves - 2) {
 579         beep();
 580         review = count_moves - 2;
 581     } else {
 582         *ny = history[count_moves - review - 1].y;
 583         *nx = history[count_moves - review - 1].x;
 584         wprintw(msgwin, "\nReview %d:%d.", count_moves - review - 1,
 585                 count_moves - 1);
 586         wrefresh(msgwin);
 587     }
 588     return review;
 589 }
 590
 591 static void
 592 play(void)
 593 /* play the game */
 594 {
 595     bool keyhelp;               /* TRUE if keystroke help is up */
 596     int i, j, count;
 597     int lastcol = 0;            /* last location visited */
 598     int lastrow = 0;
 599     int ny = 0, nx = 0;
 600     int review = 0;             /* review history */
 601     int test_size;
 602     int rw = 0, col = 0;        /* current row and column */
 603
 604     do {
 605         SQUARES squares;
 606         HISTORY history[(YLIMIT * XLIMIT) + 1];
 607         int count_moves = 0;    /* count of moves so far */
 608
 609         /* clear screen and draw board */
 610         werase(boardwin);
 611         werase(helpwin);
 612         werase(msgwin);
 613         drawBoard();
 614         help1();
 615         wnoutrefresh(stdscr);
 616         wnoutrefresh(helpwin);
 617         wnoutrefresh(msgwin);
 618         wnoutrefresh(boardwin);
 619         doupdate();
 620
 621         for (i = 0; i < ylimit; i++) {
 622             for (j = 0; j < xlimit; j++) {
 623                 squares[i][j] = FALSE;
 624                 unmarkcell(i, j);
 625             }
 626         }
 627         memset(history, 0, sizeof(history));
 628         history[0].y = history[0].x = -1;
 629         history[1].y = history[1].x = -1;
 630         lastrow = lastcol = -2;
 631         count_moves = 1;
 632         count_tries = 1;
 633         keyhelp = FALSE;
 634         show_help(&keyhelp);
 635
 636         for (;;) {
 637             if (rw != lastrow || col != lastcol) {
 638                 if (lastrow >= 0 && lastcol >= 0) {
 639                     cellmove(lastrow, lastcol);
 640                     if (squares[lastrow][lastcol])
 641                         waddch(boardwin, trail);
 642                     else
 643                         waddch(boardwin, oldch);
 644                 }
 645
 646                 cellmove(rw, col);
 647                 oldch = winch(boardwin);
 648
 649                 lastrow = rw;
 650                 lastcol = col;
 651             }
 652             cellmove(rw, col);
 653             waddch(boardwin, plus);
 654             cellmove(rw, col);
 655
 656             wrefresh(msgwin);
 657
 658             switch (wgetch(boardwin)) {
 659             case 'k':
 660             case '8':
 661             case KEY_UP:
 662                 ny = rw + ylimit - 1;
 663                 nx = col;
 664                 break;
 665             case 'j':
 666             case '2':
 667             case KEY_DOWN:
 668                 ny = rw + 1;
 669                 nx = col;
 670                 break;
 671             case 'h':
 672             case '4':
 673             case KEY_LEFT:
 674                 ny = rw;
 675                 nx = col + xlimit - 1;
 676                 break;
 677             case 'l':
 678             case '6':
 679             case KEY_RIGHT:
 680                 ny = rw;
 681                 nx = col + 1;
 682                 break;
 683             case 'y':
 684             case '7':
 685             case KEY_A1:
 686                 ny = rw + ylimit - 1;
 687                 nx = col + xlimit - 1;
 688                 break;
 689             case 'b':
 690             case '1':
 691             case KEY_C1:
 692                 ny = rw + 1;
 693                 nx = col + xlimit - 1;
 694                 break;
 695             case 'u':
 696             case '9':
 697             case KEY_A3:
 698                 ny = rw + ylimit - 1;
 699                 nx = col + 1;
 700                 break;
 701             case 'n':
 702             case '3':
 703             case KEY_C3:
 704                 ny = rw + 1;
 705                 nx = col + 1;
 706                 break;
 707
 708 #ifdef KEY_MOUSE
 709             case KEY_MOUSE:
 710 #ifdef NCURSES_MOUSE_VERSION
 711                 {
 712                     MEVENT myevent;
 713
 714                     getmouse(&myevent);
 715                     if (myevent.y >= CY(0) && myevent.y <= CY(ylimit)
 716                         && myevent.x >= CX(0) && myevent.x <= CX(xlimit)) {
 717                         nx = CXINV(myevent.x);
 718                         ny = CYINV(myevent.y);
 719                         ungetch('\n');
 720                         break;
 721                     } else {
 722                         beep();
 723                         continue;
 724                     }
 725                 }
 726 #endif /* NCURSES_MOUSE_VERSION */
 727 #ifdef PDCURSES
 728                 {
 729                     int test_y, test_x;
 730                     request_mouse_pos();
 731                     test_y = MOUSE_Y_POS + 0;
 732                     test_x = MOUSE_X_POS + 1;
 733                     if (test_y >= CY(0) && test_y <= CY(ylimit)
 734                         && test_x >= CX(0) && test_x <= CX(xlimit)) {
 735                         ny = CYINV(test_y);
 736                         nx = CXINV(test_x);
 737                         wmove(helpwin, 0, 0);
 738                         wrefresh(helpwin);
 739                         ungetch('\n');
 740                     }
 741                     break;
 742                 }
 743 #endif /* PDCURSES */
 744 #endif /* KEY_MOUSE */
 745
 746             case KEY_B2:
 747             case '\n':
 748             case ' ':
 749                 review = 0;
 750                 if (evaluate_move(squares, history, count_moves, rw, col)) {
 751                     drawMove(squares,
 752                              count_moves,
 753                              trail,
 754                              history[count_moves - 1].y,
 755                              history[count_moves - 1].x,
 756                              rw, col);
 757                     history[count_moves].y = (short) rw;
 758                     history[count_moves].x = (short) col;
 759                     count_moves++;
 760                     count_tries++;
 761
 762                     if (boardIsFilled(squares, rw, col)) {
 763                         if (completed(squares) < 0) {
 764                             waddstr(msgwin, "\nYou won.");
 765                         } else {
 766                             waddstr(msgwin,
 767                                     "\nNo further moves are possible.");
 768                         }
 769                     }
 770                 } else {
 771                     beep();
 772                 }
 773                 break;
 774
 775             case KEY_UNDO:
 776             case KEY_BACKSPACE:
 777             case '\b':
 778                 review = 0;
 779                 if (count_moves <= 0) {
 780                     no_previous_move();
 781                 } else if (count_moves <= 1) {
 782                     ny = history[count_moves].y;
 783                     nx = history[count_moves].x;
 784                     if (nx < 0 || ny < 0) {
 785                         ny = (lastrow >= 0) ? lastrow : 0;
 786                         nx = (lastcol >= 0) ? lastcol : 0;
 787                     }
 788                     count_moves = 0;
 789                     squares[ny][nx] = FALSE;
 790                     oldch = minus;
 791                     drawMove(squares, count_moves, ' ', ny, nx, -1, -1);
 792                     count_moves = 1;
 793                     count_tries = 1;
 794                     no_previous_move();
 795                 } else {
 796                     int oldy = history[count_moves - 1].y;
 797                     int oldx = history[count_moves - 1].x;
 798
 799                     if (!squares[rw][col]) {
 800                         cellmove(rw, col);
 801                         waddch(boardwin, ' ');
 802                     }
 803
 804                     squares[oldy][oldx] = FALSE;
 805                     --count_moves;
 806                     ny = history[count_moves - 1].y;
 807                     nx = history[count_moves - 1].x;
 808                     if (nx < 0 || ny < 0) {
 809                         ny = oldy;
 810                         nx = oldx;
 811                     }
 812                     drawMove(squares, count_moves, ' ', oldy, oldx, ny, nx);
 813
 814                     /* avoid problems if we just changed the current cell */
 815                     cellmove(lastrow, lastcol);
 816                     oldch = winch(boardwin);
 817                 }
 818                 break;
 819
 820             case 'a':
 821                 nx = col;
 822                 ny = rw;
 823                 if (find_next_move(squares, history, count_moves, &ny, &nx))
 824                     count_next_moves(squares, count_moves, ny, nx);
 825                 else
 826                     beep();
 827                 break;
 828
 829             case 'F':
 830                 review = reviewHistory(history, count_moves, review - 1,
 831                                        &ny, &nx);
 832                 break;
 833
 834             case 'B':
 835                 review = reviewHistory(history, count_moves, review + 1,
 836                                        &ny, &nx);
 837                 break;
 838
 839             case 'R':
 840                 if (ylimit <= 6) {
 841                     wprintw(msgwin, "\nworking...");
 842                     wrefresh(msgwin);
 843                     test_test = 0;
 844                     test_size = useBacktracking(squares, history, count_moves);
 845                     wprintw(msgwin, "\nOk %d:%d (%d tests)",
 846                             test_size, maxmoves, test_test);
 847                     review = 0;
 848                     while (count_moves <= test_size) {
 849                         markcell(trail,
 850                                  ny = history[count_moves].y,
 851                                  nx = history[count_moves].x);
 852                         count_moves++;
 853                     }
 854                 } else {
 855                     wprintw(msgwin, "\nBoard is too large.");
 856                 }
 857                 wrefresh(msgwin);
 858                 break;
 859
 860 #if HAVE_CURSCR
 861             case KEY_REDO:
 862             case '\f':
 863             case 'r':
 864                 clearok(curscr, TRUE);
 865                 wnoutrefresh(stdscr);
 866                 wnoutrefresh(boardwin);
 867                 wnoutrefresh(msgwin);
 868                 wnoutrefresh(helpwin);
 869                 doupdate();
 870                 break;
 871 #endif
 872
 873             case 'q':
 874             case 'x':
 875                 goto dropout;
 876
 877             case HELP_KEY_1:
 878                 show_help(&keyhelp);
 879                 break;
 880
 881             default:
 882                 beep();
 883                 break;
 884             }
 885
 886             col = nx % xlimit;
 887             rw = ny % ylimit;
 888         }
 889
 890       dropout:
 891         if ((count = completed(squares)) < 0)
 892             wprintw(msgwin, "\nYou won.  Care to try again? ");
 893         else
 894             wprintw(msgwin, "\n%d squares filled.  Try again? ", count);
 895         wclrtoeol(msgwin);
 896     } while
 897         (tolower(wgetch(msgwin)) == 'y');
 898 }
 899
 900 static void
 901 usage(void)
 902 {
 903     static const char *msg[] =
 904     {
 905         "Usage: knight [options]"
 906         ,""
 907         ,"Options:"
 908 #if HAVE_USE_DEFAULT_COLORS
 909         ," -d       invoke use_default_colors"
 910 #endif
 911         ," -n NUM   set board-size to NUM*NUM (default 8x8)"
 912     };
 913     size_t n;
 914
 915     for (n = 0; n < SIZEOF(msg); n++)
 916         fprintf(stderr, "%s\n", msg[n]);
 917
 918     ExitProgram(EXIT_FAILURE);
 919 }
 920
 921 int
 922 main(int argc, char *argv[])
 923 {
 924     int ch;
 925
 926     while ((ch = getopt(argc, argv, "dn:")) != -1) {
 927         switch (ch) {
 928 #if HAVE_USE_DEFAULT_COLORS
 929         case 'd':
 930             d_option = TRUE;
 931             break;
 932 #endif
 933         case 'n':
 934             ch = atoi(optarg);
 935             if (ch < 3 || ch > 8) {
 936                 fprintf(stderr, "board size %d is outside [3..8]\n", ch);
 937                 usage();
 938             }
 939             xlimit = ylimit = ch;
 940             break;
 941         default:
 942             usage();
 943             /* NOTREACHED */
 944         }
 945     }
 946     if (optind < argc)
 947         usage();
 948
 949     init_program();
 950
 951     play();
 952
 953     endwin();
 954     ExitProgram(EXIT_SUCCESS);
 955 }