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.45 2019/04/20 20:34:55 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     unsigned j, k;
 332     int found = -1;
 333     int first = -1;
 334     int next = -1;
 335     int oldy, oldx;
 336     int newy, newx;
 337     bool result = FALSE;
 338
 339     if (doneSize > 1) {
 340         oldy = doneData[doneSize - 1].y;
 341         oldx = doneData[doneSize - 1].x;
 342         for (j = 0; j < MAX_OFFSET * 2; j++) {
 343             k = j % MAX_OFFSET;
 344             newy = oldy + offsets[k].y;
 345             newx = oldx + offsets[k].x;
 346             if (isUnusedYX(squares, newy, newx)) {
 347                 if (first < 0)
 348                     first = (int) k;
 349                 if (newy == *y
 350                     && newx == *x) {
 351                     found = (int) k;
 352                 } else if (found >= 0) {
 353                     next = (int) k;
 354                     break;
 355                 }
 356             }
 357         }
 358         if (found < 0)
 359             next = first;
 360         if (next >= 0) {
 361             *y = oldy + offsets[next].y;
 362             *x = oldx + offsets[next].x;
 363         }
 364         result = TRUE;
 365     }
 366     return result;
 367 }
 368
 369 static void
 370 count_next_moves(SQUARES squares, int count_moves, int y, int x)
 371 {
 372     int count = 0;
 373     unsigned j;
 374
 375     wprintw(msgwin, "\nMove %d", count_moves);
 376     for (j = 0; j < MAX_OFFSET; j++) {
 377         int newy = y + offsets[j].y;
 378         int newx = x + offsets[j].x;
 379         if (isUnusedYX(squares, newy, newx)) {
 380             ++count;
 381         }
 382     }
 383     wprintw(msgwin, ", gives %d choices", count);
 384     wclrtoeol(msgwin);
 385 }
 386
 387 static void
 388 unmarkcell(int row, int column)
 389 {
 390     cellmove(row, column);
 391     waddch(boardwin, '\b');
 392     waddch(boardwin, ' ');
 393     waddch(boardwin, minus);
 394     waddch(boardwin, ' ');
 395 }
 396
 397 static void
 398 markcell(chtype tchar, int row, int column)
 399 {
 400     cellmove(row, column);
 401     waddch(boardwin, '\b');
 402     waddch(boardwin, tchar);
 403     waddch(boardwin, tchar);
 404     waddch(boardwin, tchar);
 405 }
 406
 407 static void
 408 drawMove(SQUARES squares, int count_moves, chtype tchar, int oldy, int oldx, int
 409          row, int column)
 410 /* place the stars, update board & currents */
 411 {
 412     if (count_moves <= 1) {
 413         int i, j;
 414
 415         for (i = 0; i < ylimit; i++) {
 416             for (j = 0; j < xlimit; j++) {
 417                 if (count_moves == 0) {
 418                     unmarkcell(i, j);
 419                 } else {
 420                     cellmove(i, j);
 421                     if (winch(boardwin) == minus)
 422                         waddch(boardwin, ' ');
 423                 }
 424             }
 425         }
 426     } else {
 427         markcell(tchar, oldy, oldx);
 428         mark_possibles(squares, oldy, oldx, ' ');
 429     }
 430
 431     if (row >= 0 && column >= 0) {
 432         markcell(trail, row, column);
 433         mark_possibles(squares, row, column, minus);
 434         squares[row][column] = TRUE;
 435     }
 436
 437     wprintw(msgwin, "\nMove %d", count_moves);
 438     if (count_tries != count_moves)
 439         wprintw(msgwin, " (%d tries)", count_tries);
 440     wclrtoeol(msgwin);
 441 }
 442
 443 static int
 444 iabs(int num)
 445 {
 446     if (num < 0)
 447         return (-num);
 448     else
 449         return (num);
 450 }
 451
 452 static bool
 453 evaluate_move(SQUARES squares, HISTORY * doneData, int doneSize, int row, int column)
 454 {
 455     if (doneSize <= 1)
 456         return (TRUE);
 457     else if (squares[row][column] == TRUE) {
 458         waddstr(msgwin, "\nYou've already been there.");
 459         return (FALSE);
 460     } else {
 461         int rdif = iabs(row - doneData[doneSize - 1].y);
 462         int cdif = iabs(column - doneData[doneSize - 1].x);
 463
 464         if (!((rdif == 1) && (cdif == 2)) && !((rdif == 2) && (cdif == 1))) {
 465             waddstr(msgwin, "\nThat's not a legal knight's move.");
 466             return (FALSE);
 467         }
 468     }
 469
 470     return (TRUE);
 471 }
 472
 473 static int
 474 completed(SQUARES squares)
 475 {
 476     int i, j, count = 0;
 477
 478     for (i = 0; i < ylimit; i++) {
 479         for (j = 0; j < xlimit; j++) {
 480             if (squares[i][j] != 0) {
 481                 count += 1;
 482             }
 483         }
 484     }
 485     return ((count == maxmoves) ? -1 : count);
 486 }
 487
 488 static void
 489 no_previous_move(void)
 490 {
 491     waddstr(msgwin, "\nNo previous move.");
 492     beep();
 493 }
 494
 495 /* Recursively try all possible moves, starting from (y,x) */
 496 static int
 497 recurBack(SQUARES squares, int y, int x, int total)
 498 {
 499     int longest = total;
 500     int best_x = x;
 501     int best_y = y;
 502     int result;
 503
 504     if (total < maxmoves) {
 505         int try_x, try_y;
 506         unsigned k;
 507
 508         for (k = 0; k < MAX_OFFSET; k++) {
 509             try_x = x + offsets[k].x;
 510             try_y = y + offsets[k].y;
 511             if (isUnusedYX(squares, try_y, try_x)) {
 512                 ++test_test;
 513                 squares[try_y][try_x] = total + 1;
 514                 result = recurBack(squares, try_y, try_x, total + 1);
 515                 if (result > longest) {
 516                     longest = result;
 517                     best_x = try_x;
 518                     best_y = try_y;
 519                 }
 520                 if (result >= maxmoves)
 521                     break;
 522                 squares[try_y][try_x] = 0;      /* allow retry... */
 523             }
 524         }
 525     }
 526
 527     result = total;
 528     if (longest > total) {
 529         result = longest;
 530         squares[best_y][best_x] = total + 1;
 531         (void) recurBack(squares, best_y, best_x, total + 1);
 532         if (result < maxmoves)
 533             squares[best_y][best_x] = 0;
 534     }
 535
 536     return result;
 537 }
 538
 539 /*
 540  * Solve the Knight Tour problem using backtracking, returning the length of
 541  * the resulting solution.  If this is invoked from a point where the remaining
 542  * choices cannot complete the tour, the result will fall short.
 543  */
 544 static int
 545 useBacktracking(SQUARES result, HISTORY * doneData, int doneSize)
 546 {
 547     int y = 0, x = 0, n;
 548     SQUARES squares;
 549     int total;
 550     int actual = doneSize - 1;
 551
 552     memset(squares, 0, sizeof(squares));
 553     for (n = 1; n <= actual; ++n) {
 554         y = doneData[n].y;
 555         x = doneData[n].x;
 556         squares[y][x] = n;
 557     }
 558
 559     total = recurBack(squares, y, x, actual);
 560     if (total > actual) {
 561         for (y = 0; y < ylimit; ++y) {
 562             for (x = 0; x < xlimit; ++x) {
 563                 result[y][x] = squares[y][x];
 564                 if ((n = squares[y][x]) != 0) {
 565                     doneData[n].y = y;
 566                     doneData[n].x = x;
 567                 }
 568             }
 569         }
 570     }
 571     return total;
 572 }
 573
 574 static int
 575 reviewHistory(HISTORY * history, int count_moves, int review, int *ny, int *nx)
 576 {
 577     if (review < 0) {
 578         beep();
 579         review = 0;
 580     } else if (review > count_moves - 2) {
 581         beep();
 582         review = count_moves - 2;
 583     } else {
 584         *ny = history[count_moves - review - 1].y;
 585         *nx = history[count_moves - review - 1].x;
 586         wprintw(msgwin, "\nReview %d:%d.", count_moves - review - 1,
 587                 count_moves - 1);
 588         wrefresh(msgwin);
 589     }
 590     return review;
 591 }
 592
 593 static void
 594 play(void)
 595 /* play the game */
 596 {
 597     bool keyhelp;               /* TRUE if keystroke help is up */
 598     int i, j, count;
 599     int lastcol = 0;            /* last location visited */
 600     int lastrow = 0;
 601     int ny = 0, nx = 0;
 602     int review = 0;             /* review history */
 603     int test_size;
 604     int rw = 0, col = 0;        /* current row and column */
 605
 606     do {
 607         SQUARES squares;
 608         HISTORY history[(YLIMIT * XLIMIT) + 1];
 609         int count_moves = 0;    /* count of moves so far */
 610
 611         /* clear screen and draw board */
 612         werase(boardwin);
 613         werase(helpwin);
 614         werase(msgwin);
 615         drawBoard();
 616         help1();
 617         wnoutrefresh(stdscr);
 618         wnoutrefresh(helpwin);
 619         wnoutrefresh(msgwin);
 620         wnoutrefresh(boardwin);
 621         doupdate();
 622
 623         for (i = 0; i < ylimit; i++) {
 624             for (j = 0; j < xlimit; j++) {
 625                 squares[i][j] = FALSE;
 626                 unmarkcell(i, j);
 627             }
 628         }
 629         memset(history, 0, sizeof(history));
 630         history[0].y = history[0].x = -1;
 631         history[1].y = history[1].x = -1;
 632         lastrow = lastcol = -2;
 633         count_moves = 1;
 634         count_tries = 1;
 635         keyhelp = FALSE;
 636         show_help(&keyhelp);
 637
 638         for (;;) {
 639             if (rw != lastrow || col != lastcol) {
 640                 if (lastrow >= 0 && lastcol >= 0) {
 641                     cellmove(lastrow, lastcol);
 642                     if (squares[lastrow][lastcol])
 643                         waddch(boardwin, trail);
 644                     else
 645                         waddch(boardwin, oldch);
 646                 }
 647
 648                 cellmove(rw, col);
 649                 oldch = winch(boardwin);
 650
 651                 lastrow = rw;
 652                 lastcol = col;
 653             }
 654             cellmove(rw, col);
 655             waddch(boardwin, plus);
 656             cellmove(rw, col);
 657
 658             wrefresh(msgwin);
 659
 660             switch (wgetch(boardwin)) {
 661             case 'k':
 662             case '8':
 663             case KEY_UP:
 664                 ny = rw + ylimit - 1;
 665                 nx = col;
 666                 break;
 667             case 'j':
 668             case '2':
 669             case KEY_DOWN:
 670                 ny = rw + 1;
 671                 nx = col;
 672                 break;
 673             case 'h':
 674             case '4':
 675             case KEY_LEFT:
 676                 ny = rw;
 677                 nx = col + xlimit - 1;
 678                 break;
 679             case 'l':
 680             case '6':
 681             case KEY_RIGHT:
 682                 ny = rw;
 683                 nx = col + 1;
 684                 break;
 685             case 'y':
 686             case '7':
 687             case KEY_A1:
 688                 ny = rw + ylimit - 1;
 689                 nx = col + xlimit - 1;
 690                 break;
 691             case 'b':
 692             case '1':
 693             case KEY_C1:
 694                 ny = rw + 1;
 695                 nx = col + xlimit - 1;
 696                 break;
 697             case 'u':
 698             case '9':
 699             case KEY_A3:
 700                 ny = rw + ylimit - 1;
 701                 nx = col + 1;
 702                 break;
 703             case 'n':
 704             case '3':
 705             case KEY_C3:
 706                 ny = rw + 1;
 707                 nx = col + 1;
 708                 break;
 709
 710 #ifdef KEY_MOUSE
 711             case KEY_MOUSE:
 712 #ifdef NCURSES_MOUSE_VERSION
 713                 {
 714                     MEVENT myevent;
 715
 716                     getmouse(&myevent);
 717                     if (myevent.y >= CY(0) && myevent.y <= CY(ylimit)
 718                         && myevent.x >= CX(0) && myevent.x <= CX(xlimit)) {
 719                         nx = CXINV(myevent.x);
 720                         ny = CYINV(myevent.y);
 721                         ungetch('\n');
 722                         break;
 723                     } else {
 724                         beep();
 725                         continue;
 726                     }
 727                 }
 728 #endif /* NCURSES_MOUSE_VERSION */
 729 #ifdef PDCURSES
 730                 {
 731                     int test_y, test_x;
 732                     request_mouse_pos();
 733                     test_y = MOUSE_Y_POS + 0;
 734                     test_x = MOUSE_X_POS + 1;
 735                     if (test_y >= CY(0) && test_y <= CY(ylimit)
 736                         && test_x >= CX(0) && test_x <= CX(xlimit)) {
 737                         ny = CYINV(test_y);
 738                         nx = CXINV(test_x);
 739                         wmove(helpwin, 0, 0);
 740                         wrefresh(helpwin);
 741                         ungetch('\n');
 742                     }
 743                     break;
 744                 }
 745 #endif /* PDCURSES */
 746 #endif /* KEY_MOUSE */
 747
 748             case KEY_B2:
 749             case '\n':
 750             case ' ':
 751                 review = 0;
 752                 if (evaluate_move(squares, history, count_moves, rw, col)) {
 753                     drawMove(squares,
 754                              count_moves,
 755                              trail,
 756                              history[count_moves - 1].y,
 757                              history[count_moves - 1].x,
 758                              rw, col);
 759                     history[count_moves].y = (short) rw;
 760                     history[count_moves].x = (short) col;
 761                     count_moves++;
 762                     count_tries++;
 763
 764                     if (boardIsFilled(squares, rw, col)) {
 765                         if (completed(squares) < 0) {
 766                             waddstr(msgwin, "\nYou won.");
 767                         } else {
 768                             waddstr(msgwin,
 769                                     "\nNo further moves are possible.");
 770                         }
 771                     }
 772                 } else {
 773                     beep();
 774                 }
 775                 break;
 776
 777             case KEY_UNDO:
 778             case KEY_BACKSPACE:
 779             case '\b':
 780                 review = 0;
 781                 if (count_moves <= 0) {
 782                     no_previous_move();
 783                 } else if (count_moves <= 1) {
 784                     ny = history[count_moves].y;
 785                     nx = history[count_moves].x;
 786                     if (nx < 0 || ny < 0) {
 787                         ny = (lastrow >= 0) ? lastrow : 0;
 788                         nx = (lastcol >= 0) ? lastcol : 0;
 789                     }
 790                     count_moves = 0;
 791                     squares[ny][nx] = FALSE;
 792                     oldch = minus;
 793                     drawMove(squares, count_moves, ' ', ny, nx, -1, -1);
 794                     count_moves = 1;
 795                     count_tries = 1;
 796                     no_previous_move();
 797                 } else {
 798                     int oldy = history[count_moves - 1].y;
 799                     int oldx = history[count_moves - 1].x;
 800
 801                     if (!squares[rw][col]) {
 802                         cellmove(rw, col);
 803                         waddch(boardwin, ' ');
 804                     }
 805
 806                     squares[oldy][oldx] = FALSE;
 807                     --count_moves;
 808                     ny = history[count_moves - 1].y;
 809                     nx = history[count_moves - 1].x;
 810                     if (nx < 0 || ny < 0) {
 811                         ny = oldy;
 812                         nx = oldx;
 813                     }
 814                     drawMove(squares, count_moves, ' ', oldy, oldx, ny, nx);
 815
 816                     /* avoid problems if we just changed the current cell */
 817                     cellmove(lastrow, lastcol);
 818                     oldch = winch(boardwin);
 819                 }
 820                 break;
 821
 822             case 'a':
 823                 nx = col;
 824                 ny = rw;
 825                 if (find_next_move(squares, history, count_moves, &ny, &nx))
 826                     count_next_moves(squares, count_moves, ny, nx);
 827                 else
 828                     beep();
 829                 break;
 830
 831             case 'F':
 832                 review = reviewHistory(history, count_moves, review - 1,
 833                                        &ny, &nx);
 834                 break;
 835
 836             case 'B':
 837                 review = reviewHistory(history, count_moves, review + 1,
 838                                        &ny, &nx);
 839                 break;
 840
 841             case 'R':
 842                 if (ylimit <= 6) {
 843                     wprintw(msgwin, "\nworking...");
 844                     wrefresh(msgwin);
 845                     test_test = 0;
 846                     test_size = useBacktracking(squares, history, count_moves);
 847                     wprintw(msgwin, "\nOk %d:%d (%d tests)",
 848                             test_size, maxmoves, test_test);
 849                     review = 0;
 850                     while (count_moves <= test_size) {
 851                         markcell(trail,
 852                                  ny = history[count_moves].y,
 853                                  nx = history[count_moves].x);
 854                         count_moves++;
 855                     }
 856                 } else {
 857                     wprintw(msgwin, "\nBoard is too large.");
 858                 }
 859                 wrefresh(msgwin);
 860                 break;
 861
 862 #if HAVE_CURSCR
 863             case KEY_REDO:
 864             case '\f':
 865             case 'r':
 866                 clearok(curscr, TRUE);
 867                 wnoutrefresh(stdscr);
 868                 wnoutrefresh(boardwin);
 869                 wnoutrefresh(msgwin);
 870                 wnoutrefresh(helpwin);
 871                 doupdate();
 872                 break;
 873 #endif
 874
 875             case 'q':
 876             case 'x':
 877                 goto dropout;
 878
 879             case HELP_KEY_1:
 880                 show_help(&keyhelp);
 881                 break;
 882
 883             default:
 884                 beep();
 885                 break;
 886             }
 887
 888             col = nx % xlimit;
 889             rw = ny % ylimit;
 890         }
 891
 892       dropout:
 893         if ((count = completed(squares)) < 0)
 894             wprintw(msgwin, "\nYou won.  Care to try again? ");
 895         else
 896             wprintw(msgwin, "\n%d squares filled.  Try again? ", count);
 897         wclrtoeol(msgwin);
 898     } while
 899         (tolower(wgetch(msgwin)) == 'y');
 900 }
 901
 902 static void
 903 usage(void)
 904 {
 905     static const char *msg[] =
 906     {
 907         "Usage: knight [options]"
 908         ,""
 909         ,"Options:"
 910 #if HAVE_USE_DEFAULT_COLORS
 911         ," -d       invoke use_default_colors"
 912 #endif
 913         ," -n NUM   set board-size to NUM*NUM (default 8x8)"
 914     };
 915     size_t n;
 916
 917     for (n = 0; n < SIZEOF(msg); n++)
 918         fprintf(stderr, "%s\n", msg[n]);
 919
 920     ExitProgram(EXIT_FAILURE);
 921 }
 922
 923 int
 924 main(int argc, char *argv[])
 925 {
 926     int ch;
 927
 928     while ((ch = getopt(argc, argv, "dn:")) != -1) {
 929         switch (ch) {
 930 #if HAVE_USE_DEFAULT_COLORS
 931         case 'd':
 932             d_option = TRUE;
 933             break;
 934 #endif
 935         case 'n':
 936             ch = atoi(optarg);
 937             if (ch < 3 || ch > 8) {
 938                 fprintf(stderr, "board size %d is outside [3..8]\n", ch);
 939                 usage();
 940             }
 941             xlimit = ylimit = ch;
 942             break;
 943         default:
 944             usage();
 945             /* NOTREACHED */
 946         }
 947     }
 948     if (optind < argc)
 949         usage();
 950
 951     init_program();
 952
 953     play();
 954
 955     endwin();
 956     ExitProgram(EXIT_SUCCESS);
 957 }