test/knight.c

   1 /****************************************************************************
   2  * Copyright (c) 1998-2013,2017 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.43 2017/09/10 00:13:02 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 static bool d_option;
  79
  80 static chtype minus = '-';      /* possible-move character */
  81 static chtype oldch;
  82 static chtype plus = '+';       /* cursor hot-spot character */
  83 static chtype trail = '#';      /* trail character */
  84
  85 static int ylimit = YLIMIT;
  86 static int xlimit = XLIMIT;
  87 static int maxmoves = (YLIMIT * XLIMIT);
  88
  89 static int count_tries;         /* count of trials so far */
  90 static int test_test;           /* FIXME */
  91 /* *INDENT-OFF* */
  92 static const struct {
  93     int y;
  94     int x;
  95 } offsets[] = {
  96     {  2,  1 },
  97     {  1,  2 },
  98     { -1,  2 },
  99     { -2,  1 },
 100     { -2, -1 },
 101     { -1, -2 },
 102     {  1, -2 },
 103     {  2, -1 },
 104 };
 105 #define MAX_OFFSET      (unsigned)SIZEOF(offsets)
 106 /* *INDENT-ON* */
 107
 108 static void
 109 init_program(void)
 110 {
 111     setlocale(LC_ALL, "");
 112
 113     srand((unsigned) getpid());
 114     initscr();
 115     cbreak();                   /* immediate char return */
 116     noecho();                   /* no immediate echo */
 117
 118     maxmoves = MAXMOVES;
 119     boardwin = newwin(ylimit * 2 + 1, xlimit * 4 + 1, BOARDY, BOARDX);
 120     helpwin = newwin(0, 0, INSTRY, INSTRX);
 121     msgwin = newwin(1, INSTRX - 1, NOTIFYY, 0);
 122
 123     scrollok(msgwin, TRUE);
 124     keypad(boardwin, TRUE);
 125
 126     if (has_colors()) {
 127         int bg = COLOR_BLACK;
 128
 129         start_color();
 130 #if HAVE_USE_DEFAULT_COLORS
 131         if (d_option && (use_default_colors() == OK))
 132             bg = -1;
 133 #endif
 134
 135         (void) init_pair(TRAIL_COLOR, (short) COLOR_CYAN, (short) bg);
 136         (void) init_pair(PLUS_COLOR, (short) COLOR_RED, (short) bg);
 137         (void) init_pair(MINUS_COLOR, (short) COLOR_GREEN, (short) bg);
 138
 139         trail |= (chtype) COLOR_PAIR(TRAIL_COLOR);
 140         plus |= (chtype) COLOR_PAIR(PLUS_COLOR);
 141         minus |= (chtype) COLOR_PAIR(MINUS_COLOR);
 142     }
 143 #ifdef NCURSES_MOUSE_VERSION
 144     (void) mousemask(BUTTON1_CLICKED, (mmask_t *) NULL);
 145 #endif /* NCURSES_MOUSE_VERSION */
 146 #if defined(PDCURSES)
 147     mouse_set(BUTTON1_RELEASED);
 148 #endif
 149
 150     oldch = minus;
 151 }
 152
 153 static void
 154 help1(void)
 155 /* game explanation -- initial help screen */
 156 {
 157     (void) waddstr(helpwin, "Knight's move is a solitaire puzzle.  Your\n");
 158     (void) waddstr(helpwin, "objective is to visit each square of the  \n");
 159     (void) waddstr(helpwin, "chessboard exactly once by making knight's\n");
 160     (void) waddstr(helpwin, "moves (one square right or left followed  \n");
 161     (void) waddstr(helpwin, "by two squares up or down, or two squares \n");
 162     (void) waddstr(helpwin, "right or left followed by one square up or\n");
 163     (void) waddstr(helpwin, "down).  You may start anywhere.\n\n");
 164
 165     (void) waddstr(helpwin, "Use arrow keys to move the cursor around.\n");
 166     (void) waddstr(helpwin, "When you want to move your knight to the \n");
 167     (void) waddstr(helpwin, "cursor location, press <space> or Enter.\n");
 168     (void) waddstr(helpwin, "Illegal moves will be rejected with an  \n");
 169     (void) waddstr(helpwin, "audible beep.\n\n");
 170     (void) waddstr(helpwin, "The program will detect if you solve the\n");
 171     (void) waddstr(helpwin, "puzzle; also inform you when you run out\n");
 172     (void) waddstr(helpwin, "of legal moves.\n\n");
 173
 174     MvWAddStr(helpwin, NOTIFYY - INSTRY, 0,
 175               "Press `?' to go to keystroke help.");
 176 }
 177
 178 static void
 179 help2(void)
 180 /* keystroke help screen */
 181 {
 182     (void) waddstr(helpwin, "Possible moves are shown with `-'.\n\n");
 183
 184     (void) waddstr(helpwin, "You can move around with the arrow keys or\n");
 185     (void) waddstr(helpwin, "with the rogue/hack movement keys.  Other\n");
 186     (void) waddstr(helpwin, "commands allow you to undo moves or redraw.\n");
 187     (void) waddstr(helpwin, "Your mouse may work; try left-button to\n");
 188     (void) waddstr(helpwin, "move to the square under the pointer.\n\n");
 189
 190     (void) waddstr(helpwin, "x,q -- exit             y k u    7 8 9\n");
 191     (void) waddstr(helpwin, "r -- redraw screen       \\|/      \\|/ \n");
 192     (void) waddstr(helpwin, "bksp -- undo move       h-+-l    4-+-6\n");
 193     (void) waddstr(helpwin, "a -- autojump            /|\\      /|\\ \n");
 194     if (ylimit <= 6) {
 195         (void) waddstr(helpwin, "R -- solve (slow)       b j n    1 2 3\n");
 196     } else {
 197         (void) waddstr(helpwin, "                        b j n    1 2 3\n");
 198     }
 199
 200     (void) waddstr(helpwin, "\nYou can place your knight on the selected\n");
 201     (void) waddstr(helpwin, "square with spacebar, Enter, or the keypad\n");
 202     (void) waddstr(helpwin, "center key.  Use F/B to review the path.\n");
 203
 204     MvWAddStr(helpwin, NOTIFYY - INSTRY, 0,
 205               "Press `?' to go to game explanation");
 206 }
 207
 208 static void
 209 show_help(bool * keyhelp)
 210 {
 211     werase(helpwin);
 212     if (*keyhelp) {
 213         help1();
 214         *keyhelp = FALSE;
 215     } else {
 216         help2();
 217         *keyhelp = TRUE;
 218     }
 219     wrefresh(helpwin);
 220 }
 221
 222 static inline bool
 223 isValidYX(int y, int x)
 224 {
 225     return (y >= 0 && y < ylimit && x >= 0 && x < xlimit) ? TRUE : FALSE;
 226 }
 227
 228 static inline bool
 229 isUnusedYX(SQUARES squares, int y, int x)
 230 {
 231     return (isValidYX(y, x) && (!squares[y][x]) ? TRUE : FALSE);
 232 }
 233
 234 static bool
 235 boardIsFilled(SQUARES squares, int y, int x)
 236 {
 237     unsigned n;
 238
 239     for (n = 0; n < MAX_OFFSET; n++) {
 240         if (isUnusedYX(squares, y + offsets[n].y, x + offsets[n].x)) {
 241             return FALSE;
 242         }
 243     }
 244     return TRUE;
 245 }
 246
 247 static void
 248 drawBoard(void)
 249 {
 250     int i, j;
 251
 252     MvAddStr(0, 20, "KNIGHT'S MOVE -- a logical solitaire");
 253
 254     move(BOARDY, BOARDX);
 255     waddch(boardwin, ACS_ULCORNER);
 256     for (j = 0; j < (ylimit - 1); j++) {
 257         waddch(boardwin, ACS_HLINE);
 258         waddch(boardwin, ACS_HLINE);
 259         waddch(boardwin, ACS_HLINE);
 260         waddch(boardwin, ACS_TTEE);
 261     }
 262     waddch(boardwin, ACS_HLINE);
 263     waddch(boardwin, ACS_HLINE);
 264     waddch(boardwin, ACS_HLINE);
 265     waddch(boardwin, ACS_URCORNER);
 266
 267     for (i = 1; i < ylimit; i++) {
 268         move(BOARDY + i * 2 - 1, BOARDX);
 269         waddch(boardwin, ACS_VLINE);
 270         for (j = 0; j < xlimit; j++) {
 271             waddch(boardwin, ' ');
 272             waddch(boardwin, ' ');
 273             waddch(boardwin, ' ');
 274             waddch(boardwin, ACS_VLINE);
 275         }
 276         move(BOARDY + i * 2, BOARDX);
 277         waddch(boardwin, ACS_LTEE);
 278         for (j = 0; j < xlimit - 1; j++) {
 279             waddch(boardwin, ACS_HLINE);
 280             waddch(boardwin, ACS_HLINE);
 281             waddch(boardwin, ACS_HLINE);
 282             waddch(boardwin, ACS_PLUS);
 283         }
 284         waddch(boardwin, ACS_HLINE);
 285         waddch(boardwin, ACS_HLINE);
 286         waddch(boardwin, ACS_HLINE);
 287         waddch(boardwin, ACS_RTEE);
 288     }
 289
 290     move(BOARDY + i * 2 - 1, BOARDX);
 291     waddch(boardwin, ACS_VLINE);
 292     for (j = 0; j < xlimit; j++) {
 293         waddch(boardwin, ' ');
 294         waddch(boardwin, ' ');
 295         waddch(boardwin, ' ');
 296         waddch(boardwin, ACS_VLINE);
 297     }
 298
 299     move(BOARDY + i * 2, BOARDX);
 300     waddch(boardwin, ACS_LLCORNER);
 301     for (j = 0; j < xlimit - 1; j++) {
 302         waddch(boardwin, ACS_HLINE);
 303         waddch(boardwin, ACS_HLINE);
 304         waddch(boardwin, ACS_HLINE);
 305         waddch(boardwin, ACS_BTEE);
 306     }
 307     waddch(boardwin, ACS_HLINE);
 308     waddch(boardwin, ACS_HLINE);
 309     waddch(boardwin, ACS_HLINE);
 310     waddch(boardwin, ACS_LRCORNER);
 311 }
 312
 313 static void
 314 mark_possibles(SQUARES squares, int y, int x, chtype mark)
 315 {
 316     unsigned n;
 317
 318     for (n = 0; n < MAX_OFFSET; n++) {
 319         if (isUnusedYX(squares, y + offsets[n].y, x + offsets[n].x)) {
 320             cellmove(y + offsets[n].y, x + offsets[n].x);
 321             waddch(boardwin, mark);
 322         }
 323     }
 324 }
 325
 326 static bool
 327 find_next_move(SQUARES squares, HISTORY * doneData, int doneSize, int *y, int *x)
 328 {
 329     unsigned j, k;
 330     int found = -1;
 331     int first = -1;
 332     int next = -1;
 333     int oldy, oldx;
 334     int newy, newx;
 335     bool result = FALSE;
 336
 337     if (doneSize > 1) {
 338         oldy = doneData[doneSize - 1].y;
 339         oldx = doneData[doneSize - 1].x;
 340         for (j = 0; j < MAX_OFFSET * 2; j++) {
 341             k = j % MAX_OFFSET;
 342             newy = oldy + offsets[k].y;
 343             newx = oldx + offsets[k].x;
 344             if (isUnusedYX(squares, newy, newx)) {
 345                 if (first < 0)
 346                     first = (int) k;
 347                 if (newy == *y
 348                     && newx == *x) {
 349                     found = (int) k;
 350                 } else if (found >= 0) {
 351                     next = (int) k;
 352                     break;
 353                 }
 354             }
 355         }
 356         if (found < 0)
 357             next = first;
 358         if (next >= 0) {
 359             *y = oldy + offsets[next].y;
 360             *x = oldx + offsets[next].x;
 361         }
 362         result = TRUE;
 363     }
 364     return result;
 365 }
 366
 367 static void
 368 count_next_moves(SQUARES squares, int count_moves, int y, int x)
 369 {
 370     int count = 0;
 371     unsigned j;
 372
 373     wprintw(msgwin, "\nMove %d", count_moves);
 374     for (j = 0; j < MAX_OFFSET; j++) {
 375         int newy = y + offsets[j].y;
 376         int newx = x + offsets[j].x;
 377         if (isUnusedYX(squares, newy, newx)) {
 378             ++count;
 379         }
 380     }
 381     wprintw(msgwin, ", gives %d choices", count);
 382     wclrtoeol(msgwin);
 383 }
 384
 385 static void
 386 unmarkcell(int row, int column)
 387 {
 388     cellmove(row, column);
 389     waddch(boardwin, '\b');
 390     waddch(boardwin, ' ');
 391     waddch(boardwin, minus);
 392     waddch(boardwin, ' ');
 393 }
 394
 395 static void
 396 markcell(chtype tchar, int row, int column)
 397 {
 398     cellmove(row, column);
 399     waddch(boardwin, '\b');
 400     waddch(boardwin, tchar);
 401     waddch(boardwin, tchar);
 402     waddch(boardwin, tchar);
 403 }
 404
 405 static void
 406 drawMove(SQUARES squares, int count_moves, chtype tchar, int oldy, int oldx, int
 407          row, int column)
 408 /* place the stars, update board & currents */
 409 {
 410     if (count_moves <= 1) {
 411         int i, j;
 412
 413         for (i = 0; i < ylimit; i++) {
 414             for (j = 0; j < xlimit; j++) {
 415                 if (count_moves == 0) {
 416                     unmarkcell(i, j);
 417                 } else {
 418                     cellmove(i, j);
 419                     if (winch(boardwin) == minus)
 420                         waddch(boardwin, count_moves ? ' ' : minus);
 421                 }
 422             }
 423         }
 424     } else {
 425         markcell(tchar, oldy, oldx);
 426         mark_possibles(squares, oldy, oldx, ' ');
 427     }
 428
 429     if (row >= 0 && column >= 0) {
 430         markcell(trail, row, column);
 431         mark_possibles(squares, row, column, minus);
 432         squares[row][column] = TRUE;
 433     }
 434
 435     wprintw(msgwin, "\nMove %d", count_moves);
 436     if (count_tries != count_moves)
 437         wprintw(msgwin, " (%d tries)", count_tries);
 438     wclrtoeol(msgwin);
 439 }
 440
 441 static int
 442 iabs(int num)
 443 {
 444     if (num < 0)
 445         return (-num);
 446     else
 447         return (num);
 448 }
 449
 450 static bool
 451 evaluate_move(SQUARES squares, HISTORY * doneData, int doneSize, int row, int column)
 452 {
 453     if (doneSize <= 1)
 454         return (TRUE);
 455     else if (squares[row][column] == TRUE) {
 456         waddstr(msgwin, "\nYou've already been there.");
 457         return (FALSE);
 458     } else {
 459         int rdif = iabs(row - doneData[doneSize - 1].y);
 460         int cdif = iabs(column - doneData[doneSize - 1].x);
 461
 462         if (!((rdif == 1) && (cdif == 2)) && !((rdif == 2) && (cdif == 1))) {
 463             waddstr(msgwin, "\nThat's not a legal knight's move.");
 464             return (FALSE);
 465         }
 466     }
 467
 468     return (TRUE);
 469 }
 470
 471 static int
 472 completed(SQUARES squares)
 473 {
 474     int i, j, count = 0;
 475
 476     for (i = 0; i < ylimit; i++) {
 477         for (j = 0; j < xlimit; j++) {
 478             if (squares[i][j] != 0) {
 479                 count += 1;
 480             }
 481         }
 482     }
 483     return ((count == maxmoves) ? -1 : count);
 484 }
 485
 486 static void
 487 no_previous_move(void)
 488 {
 489     waddstr(msgwin, "\nNo previous move.");
 490     beep();
 491 }
 492
 493 /* Recursively try all possible moves, starting from (y,x) */
 494 static int
 495 recurBack(SQUARES squares, int y, int x, int total)
 496 {
 497     int longest = total;
 498     int best_x = x;
 499     int best_y = y;
 500     int result;
 501
 502     if (total < maxmoves) {
 503         int try_x, try_y;
 504         unsigned k;
 505
 506         for (k = 0; k < MAX_OFFSET; k++) {
 507             try_x = x + offsets[k].x;
 508             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 }