test/knight.c

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