ncurses 6.1 - patch 20181201
[ncurses.git] / test / knight.c
index 0e091f46dfa50e54fdcde54120e04180bad4c0c2..0d6675e5ba1689ad22ee843b7bbb2d8fec11c1a1 100644 (file)
@@ -1,3 +1,30 @@
+/****************************************************************************
+ * Copyright (c) 1998-2017,2018 Free Software Foundation, Inc.              *
+ *                                                                          *
+ * Permission is hereby granted, free of charge, to any person obtaining a  *
+ * copy of this software and associated documentation files (the            *
+ * "Software"), to deal in the Software without restriction, including      *
+ * without limitation the rights to use, copy, modify, merge, publish,      *
+ * distribute, distribute with modifications, sublicense, and/or sell       *
+ * copies of the Software, and to permit persons to whom the Software is    *
+ * furnished to do so, subject to the following conditions:                 *
+ *                                                                          *
+ * The above copyright notice and this permission notice shall be included  *
+ * in all copies or substantial portions of the Software.                   *
+ *                                                                          *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS  *
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF               *
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.   *
+ * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,   *
+ * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR    *
+ * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR    *
+ * THE USE OR OTHER DEALINGS IN THE SOFTWARE.                               *
+ *                                                                          *
+ * Except as contained in this notice, the name(s) of the above copyright   *
+ * holders shall not be used in advertising or otherwise to promote the     *
+ * sale, use or other dealings in this Software without prior written       *
+ * authorization.                                                           *
+ ****************************************************************************/
 /*
  * Knight's Tour - a brain game
  *
  * Eric S. Raymond <esr@snark.thyrsus.com> July 22 1995.  Mouse support
  * added September 20th 1995.
  *
- * $Id: knight.c,v 1.25 2002/06/29 23:32:18 tom Exp $
+ * $Id: knight.c,v 1.44 2018/05/12 13:23:24 tom Exp $
  */
 
-#include <ctype.h>
-
 #include <test.priv.h>
 
 /* board size */
-#define BDEPTH 8
-#define BWIDTH 8
+#define YLIMIT         8
+#define XLIMIT         8
+#define MAXMOVES       (ylimit * xlimit)
 
 /* where to start the instructions */
-#define INSTRY 2
-#define INSTRX 35
+#define INSTRY         2
+#define INSTRX         35
 
 /* corner of board */
-#define BOARDY 2
-#define BOARDX 0
+#define BOARDY         2
+#define BOARDX         0
 
 /* notification line */
-#define NOTIFYY        21
+#define NOTIFYY                21
 
 /* virtual color values */
 #define TRAIL_COLOR    1
 #define CYINV(y)       (((y) - 2) / 2)
 
 typedef struct {
-    short x, y;
-} cell;
+    int x, y;
+} HISTORY;
+
+typedef int SQUARES[YLIMIT][XLIMIT];
 
 static WINDOW *boardwin;       /* the board window */
 static WINDOW *helpwin;                /* the help window */
 static WINDOW *msgwin;         /* the message window */
-static cell history[BDEPTH * BWIDTH + 1];      /* choice history */
+
+static bool d_option;
+
 static chtype minus = '-';     /* possible-move character */
 static chtype oldch;
 static chtype plus = '+';      /* cursor hot-spot character */
 static chtype trail = '#';     /* trail character */
-static int movecount;          /* count of moves so far */
-static int trialcount;         /* count of trials so far */
-static short board[BDEPTH][BWIDTH];    /* the squares */
+
+static int ylimit = YLIMIT;
+static int xlimit = XLIMIT;
+static int maxmoves = (YLIMIT * XLIMIT);
+
+static int count_tries;                /* count of trials so far */
+static int test_test;          /* FIXME */
 /* *INDENT-OFF* */
 static const struct {
     int y;
@@ -68,6 +102,7 @@ static const struct {
     {  1, -2 },
     {  2, -1 },
 };
+#define MAX_OFFSET     (unsigned)SIZEOF(offsets)
 /* *INDENT-ON* */
 
 static void
@@ -79,9 +114,12 @@ init_program(void)
     initscr();
     cbreak();                  /* immediate char return */
     noecho();                  /* no immediate echo */
-    boardwin = newwin(BDEPTH * 2 + 1, BWIDTH * 4 + 1, BOARDY, BOARDX);
+
+    maxmoves = MAXMOVES;
+    boardwin = newwin(ylimit * 2 + 1, xlimit * 4 + 1, BOARDY, BOARDX);
     helpwin = newwin(0, 0, INSTRY, INSTRX);
     msgwin = newwin(1, INSTRX - 1, NOTIFYY, 0);
+
     scrollok(msgwin, TRUE);
     keypad(boardwin, TRUE);
 
@@ -90,21 +128,24 @@ init_program(void)
 
        start_color();
 #if HAVE_USE_DEFAULT_COLORS
-       if (use_default_colors() == OK)
+       if (d_option && (use_default_colors() == OK))
            bg = -1;
 #endif
 
-       (void) init_pair(TRAIL_COLOR, COLOR_CYAN, bg);
-       (void) init_pair(PLUS_COLOR, COLOR_RED, bg);
-       (void) init_pair(MINUS_COLOR, COLOR_GREEN, bg);
+       (void) init_pair(TRAIL_COLOR, (short) COLOR_CYAN, (short) bg);
+       (void) init_pair(PLUS_COLOR, (short) COLOR_RED, (short) bg);
+       (void) init_pair(MINUS_COLOR, (short) COLOR_GREEN, (short) bg);
 
-       trail |= COLOR_PAIR(TRAIL_COLOR);
-       plus |= COLOR_PAIR(PLUS_COLOR);
-       minus |= COLOR_PAIR(MINUS_COLOR);
+       trail |= (chtype) COLOR_PAIR(TRAIL_COLOR);
+       plus |= (chtype) COLOR_PAIR(PLUS_COLOR);
+       minus |= (chtype) COLOR_PAIR(MINUS_COLOR);
     }
 #ifdef NCURSES_MOUSE_VERSION
     (void) mousemask(BUTTON1_CLICKED, (mmask_t *) NULL);
 #endif /* NCURSES_MOUSE_VERSION */
+#if defined(PDCURSES)
+    mouse_set(BUTTON1_RELEASED);
+#endif
 
     oldch = minus;
 }
@@ -130,8 +171,8 @@ help1(void)
     (void) waddstr(helpwin, "puzzle; also inform you when you run out\n");
     (void) waddstr(helpwin, "of legal moves.\n\n");
 
-    (void) mvwaddstr(helpwin, NOTIFYY - INSTRY, 0,
-                    "Press `?' to go to keystroke help.");
+    MvWAddStr(helpwin, NOTIFYY - INSTRY, 0,
+             "Press `?' to go to keystroke help.");
 }
 
 static void
@@ -150,14 +191,18 @@ help2(void)
     (void) waddstr(helpwin, "r -- redraw screen       \\|/      \\|/ \n");
     (void) waddstr(helpwin, "bksp -- undo move       h-+-l    4-+-6\n");
     (void) waddstr(helpwin, "a -- autojump            /|\\      /|\\ \n");
-    (void) waddstr(helpwin, "                        b j n    1 2 3\n");
+    if (ylimit <= 6) {
+       (void) waddstr(helpwin, "R -- solve (slow)       b j n    1 2 3\n");
+    } else {
+       (void) waddstr(helpwin, "                        b j n    1 2 3\n");
+    }
 
     (void) waddstr(helpwin, "\nYou can place your knight on the selected\n");
     (void) waddstr(helpwin, "square with spacebar, Enter, or the keypad\n");
     (void) waddstr(helpwin, "center key.  Use F/B to review the path.\n");
 
-    (void) mvwaddstr(helpwin, NOTIFYY - INSTRY, 0,
-                    "Press `?' to go to game explanation");
+    MvWAddStr(helpwin, NOTIFYY - INSTRY, 0,
+             "Press `?' to go to game explanation");
 }
 
 static void
@@ -174,38 +219,41 @@ show_help(bool * keyhelp)
     wrefresh(helpwin);
 }
 
-static bool
-chksqr(int r1, int c1)
+static inline bool
+isValidYX(int y, int x)
 {
-    if ((r1 < 0) || (r1 > BDEPTH - 1))
-       return (FALSE);
-    if ((c1 < 0) || (c1 > BWIDTH - 1))
-       return (FALSE);
-    return ((!board[r1][c1]) ? TRUE : FALSE);
+    return (y >= 0 && y < ylimit && x >= 0 && x < xlimit) ? TRUE : FALSE;
+}
+
+static inline bool
+isUnusedYX(SQUARES squares, int y, int x)
+{
+    return (isValidYX(y, x) && (!squares[y][x]) ? TRUE : FALSE);
 }
 
 static bool
-chkmoves(int rw, int col)
-/* check to see if valid moves are available */
+boardIsFilled(SQUARES squares, int y, int x)
 {
     unsigned n;
 
-    for (n = 0; n < SIZEOF(offsets); n++)
-       if (chksqr(rw + offsets[n].y, col + offsets[n].x))
-           return (TRUE);
-    return (FALSE);
+    for (n = 0; n < MAX_OFFSET; n++) {
+       if (isUnusedYX(squares, y + offsets[n].y, x + offsets[n].x)) {
+           return FALSE;
+       }
+    }
+    return TRUE;
 }
 
 static void
-dosquares(void)
+drawBoard(void)
 {
     int i, j;
 
-    mvaddstr(0, 20, "KNIGHT'S MOVE -- a logical solitaire");
+    MvAddStr(0, 20, "KNIGHT'S MOVE -- a logical solitaire");
 
     move(BOARDY, BOARDX);
     waddch(boardwin, ACS_ULCORNER);
-    for (j = 0; j < 7; j++) {
+    for (j = 0; j < (ylimit - 1); j++) {
        waddch(boardwin, ACS_HLINE);
        waddch(boardwin, ACS_HLINE);
        waddch(boardwin, ACS_HLINE);
@@ -216,10 +264,10 @@ dosquares(void)
     waddch(boardwin, ACS_HLINE);
     waddch(boardwin, ACS_URCORNER);
 
-    for (i = 1; i < BDEPTH; i++) {
+    for (i = 1; i < ylimit; i++) {
        move(BOARDY + i * 2 - 1, BOARDX);
        waddch(boardwin, ACS_VLINE);
-       for (j = 0; j < BWIDTH; j++) {
+       for (j = 0; j < xlimit; j++) {
            waddch(boardwin, ' ');
            waddch(boardwin, ' ');
            waddch(boardwin, ' ');
@@ -227,7 +275,7 @@ dosquares(void)
        }
        move(BOARDY + i * 2, BOARDX);
        waddch(boardwin, ACS_LTEE);
-       for (j = 0; j < BWIDTH - 1; j++) {
+       for (j = 0; j < xlimit - 1; j++) {
            waddch(boardwin, ACS_HLINE);
            waddch(boardwin, ACS_HLINE);
            waddch(boardwin, ACS_HLINE);
@@ -241,7 +289,7 @@ dosquares(void)
 
     move(BOARDY + i * 2 - 1, BOARDX);
     waddch(boardwin, ACS_VLINE);
-    for (j = 0; j < BWIDTH; j++) {
+    for (j = 0; j < xlimit; j++) {
        waddch(boardwin, ' ');
        waddch(boardwin, ' ');
        waddch(boardwin, ' ');
@@ -250,7 +298,7 @@ dosquares(void)
 
     move(BOARDY + i * 2, BOARDX);
     waddch(boardwin, ACS_LLCORNER);
-    for (j = 0; j < BWIDTH - 1; j++) {
+    for (j = 0; j < xlimit - 1; j++) {
        waddch(boardwin, ACS_HLINE);
        waddch(boardwin, ACS_HLINE);
        waddch(boardwin, ACS_HLINE);
@@ -263,43 +311,44 @@ dosquares(void)
 }
 
 static void
-mark_possibles(int prow, int pcol, chtype mark)
+mark_possibles(SQUARES squares, int y, int x, chtype mark)
 {
     unsigned n;
 
-    for (n = 0; n < SIZEOF(offsets); n++) {
-       if (chksqr(prow + offsets[n].y, pcol + offsets[n].x)) {
-           cellmove(prow + offsets[n].y, pcol + offsets[n].x);
+    for (n = 0; n < MAX_OFFSET; n++) {
+       if (isUnusedYX(squares, y + offsets[n].y, x + offsets[n].x)) {
+           cellmove(y + offsets[n].y, x + offsets[n].x);
            waddch(boardwin, mark);
        }
     }
 }
 
-static void
-find_next_move(int *y, int *x)
+static bool
+find_next_move(SQUARES squares, HISTORY * doneData, int doneSize, int *y, int *x)
 {
     unsigned j, k;
     int found = -1;
     int first = -1;
-    int next = 0;
+    int next = -1;
     int oldy, oldx;
     int newy, newx;
+    bool result = FALSE;
 
-    if (movecount > 1) {
-       oldy = history[movecount - 1].y;
-       oldx = history[movecount - 1].x;
-       for (j = 0; j < SIZEOF(offsets) * 2; j++) {
-           k = j % SIZEOF(offsets);
+    if (doneSize > 1) {
+       oldy = doneData[doneSize - 1].y;
+       oldx = doneData[doneSize - 1].x;
+       for (j = 0; j < MAX_OFFSET * 2; j++) {
+           k = j % MAX_OFFSET;
            newy = oldy + offsets[k].y;
            newx = oldx + offsets[k].x;
-           if (chksqr(newy, newx)) {
+           if (isUnusedYX(squares, newy, newx)) {
                if (first < 0)
-                   first = k;
+                   first = (int) k;
                if (newy == *y
                    && newx == *x) {
-                   found = k;
+                   found = (int) k;
                } else if (found >= 0) {
-                   next = k;
+                   next = (int) k;
                    break;
                }
            }
@@ -310,9 +359,27 @@ find_next_move(int *y, int *x)
            *y = oldy + offsets[next].y;
            *x = oldx + offsets[next].x;
        }
-    } else {
-       beep();
+       result = TRUE;
+    }
+    return result;
+}
+
+static void
+count_next_moves(SQUARES squares, int count_moves, int y, int x)
+{
+    int count = 0;
+    unsigned j;
+
+    wprintw(msgwin, "\nMove %d", count_moves);
+    for (j = 0; j < MAX_OFFSET; j++) {
+       int newy = y + offsets[j].y;
+       int newx = x + offsets[j].x;
+       if (isUnusedYX(squares, newy, newx)) {
+           ++count;
+       }
     }
+    wprintw(msgwin, ", gives %d choices", count);
+    wclrtoeol(msgwin);
 }
 
 static void
@@ -336,37 +403,38 @@ markcell(chtype tchar, int row, int column)
 }
 
 static void
-drawmove(chtype tchar, int oldy, int oldx, int row, int column)
+drawMove(SQUARES squares, int count_moves, chtype tchar, int oldy, int oldx, int
+        row, int column)
 /* place the stars, update board & currents */
 {
-    if (movecount <= 1) {
+    if (count_moves <= 1) {
        int i, j;
 
-       for (i = 0; i < BDEPTH; i++) {
-           for (j = 0; j < BWIDTH; j++) {
-               if (movecount == 0) {
+       for (i = 0; i < ylimit; i++) {
+           for (j = 0; j < xlimit; j++) {
+               if (count_moves == 0) {
                    unmarkcell(i, j);
                } else {
                    cellmove(i, j);
                    if (winch(boardwin) == minus)
-                       waddch(boardwin, movecount ? ' ' : minus);
+                       waddch(boardwin, ' ');
                }
            }
        }
     } else {
        markcell(tchar, oldy, oldx);
-       mark_possibles(oldy, oldx, ' ');
+       mark_possibles(squares, oldy, oldx, ' ');
     }
 
-    if (row != -1 && column != -1) {
+    if (row >= 0 && column >= 0) {
        markcell(trail, row, column);
-       mark_possibles(row, column, minus);
-       board[row][column] = TRUE;
+       mark_possibles(squares, row, column, minus);
+       squares[row][column] = TRUE;
     }
 
-    wprintw(msgwin, "\nMove %d", movecount);
-    if (trialcount != movecount)
-       wprintw(msgwin, " (%d tries)", trialcount);
+    wprintw(msgwin, "\nMove %d", count_moves);
+    if (count_tries != count_moves)
+       wprintw(msgwin, " (%d tries)", count_tries);
     wclrtoeol(msgwin);
 }
 
@@ -380,17 +448,16 @@ iabs(int num)
 }
 
 static bool
-evalmove(int row, int column)
-/* evaluate move */
+evaluate_move(SQUARES squares, HISTORY * doneData, int doneSize, int row, int column)
 {
-    if (movecount == 1)
+    if (doneSize <= 1)
        return (TRUE);
-    else if (board[row][column] == TRUE) {
+    else if (squares[row][column] == TRUE) {
        waddstr(msgwin, "\nYou've already been there.");
        return (FALSE);
     } else {
-       int rdif = iabs(row - history[movecount - 1].y);
-       int cdif = iabs(column - history[movecount - 1].x);
+       int rdif = iabs(row - doneData[doneSize - 1].y);
+       int cdif = iabs(column - doneData[doneSize - 1].x);
 
        if (!((rdif == 1) && (cdif == 2)) && !((rdif == 2) && (cdif == 1))) {
            waddstr(msgwin, "\nThat's not a legal knight's move.");
@@ -402,15 +469,18 @@ evalmove(int row, int column)
 }
 
 static int
-completed(void)
+completed(SQUARES squares)
 {
     int i, j, count = 0;
 
-    for (i = 0; i < BDEPTH; i++)
-       for (j = 0; j < BWIDTH; j++)
-           if (board[i][j] != 0)
+    for (i = 0; i < ylimit; i++) {
+       for (j = 0; j < xlimit; j++) {
+           if (squares[i][j] != 0) {
                count += 1;
-    return (count == (BWIDTH * BDEPTH) ? -1 : count);
+           }
+       }
+    }
+    return ((count == maxmoves) ? -1 : count);
 }
 
 static void
@@ -420,6 +490,104 @@ no_previous_move(void)
     beep();
 }
 
+/* Recursively try all possible moves, starting from (y,x) */
+static int
+recurBack(SQUARES squares, int y, int x, int total)
+{
+    int longest = total;
+    int best_x = x;
+    int best_y = y;
+    int result;
+
+    if (total < maxmoves) {
+       int try_x, try_y;
+       unsigned k;
+
+       for (k = 0; k < MAX_OFFSET; k++) {
+           try_x = x + offsets[k].x;
+           try_y = y + offsets[k].y;
+           if (isUnusedYX(squares, try_y, try_x)) {
+               ++test_test;
+               squares[try_y][try_x] = total + 1;
+               result = recurBack(squares, try_y, try_x, total + 1);
+               if (result > longest) {
+                   longest = result;
+                   best_x = try_x;
+                   best_y = try_y;
+               }
+               if (result >= maxmoves)
+                   break;
+               squares[try_y][try_x] = 0;      /* allow retry... */
+           }
+       }
+    }
+
+    result = total;
+    if (longest > total) {
+       result = longest;
+       squares[best_y][best_x] = total + 1;
+       (void) recurBack(squares, best_y, best_x, total + 1);
+       if (result < maxmoves)
+           squares[best_y][best_x] = 0;
+    }
+
+    return result;
+}
+
+/*
+ * Solve the Knight Tour problem using backtracking, returning the length of
+ * the resulting solution.  If this is invoked from a point where the remaining
+ * choices cannot complete the tour, the result will fall short.
+ */
+static int
+useBacktracking(SQUARES result, HISTORY * doneData, int doneSize)
+{
+    int y = 0, x = 0, n;
+    SQUARES squares;
+    int total;
+    int actual = doneSize - 1;
+
+    memset(squares, 0, sizeof(squares));
+    for (n = 1; n <= actual; ++n) {
+       y = doneData[n].y;
+       x = doneData[n].x;
+       squares[y][x] = n;
+    }
+
+    total = recurBack(squares, y, x, actual);
+    if (total > actual) {
+       for (y = 0; y < ylimit; ++y) {
+           for (x = 0; x < xlimit; ++x) {
+               result[y][x] = squares[y][x];
+               if ((n = squares[y][x]) != 0) {
+                   doneData[n].y = y;
+                   doneData[n].x = x;
+               }
+           }
+       }
+    }
+    return total;
+}
+
+static int
+reviewHistory(HISTORY * history, int count_moves, int review, int *ny, int *nx)
+{
+    if (review < 0) {
+       beep();
+       review = 0;
+    } else if (review > count_moves - 2) {
+       beep();
+       review = count_moves - 2;
+    } else {
+       *ny = history[count_moves - review - 1].y;
+       *nx = history[count_moves - review - 1].x;
+       wprintw(msgwin, "\nReview %d:%d.", count_moves - review - 1,
+               count_moves - 1);
+       wrefresh(msgwin);
+    }
+    return review;
+}
+
 static void
 play(void)
 /* play the game */
@@ -430,14 +598,19 @@ play(void)
     int lastrow = 0;
     int ny = 0, nx = 0;
     int review = 0;            /* review history */
+    int test_size;
     int rw = 0, col = 0;       /* current row and column */
 
     do {
+       SQUARES squares;
+       HISTORY history[(YLIMIT * XLIMIT) + 1];
+       int count_moves = 0;    /* count of moves so far */
+
        /* clear screen and draw board */
        werase(boardwin);
        werase(helpwin);
        werase(msgwin);
-       dosquares();
+       drawBoard();
        help1();
        wnoutrefresh(stdscr);
        wnoutrefresh(helpwin);
@@ -445,10 +618,9 @@ play(void)
        wnoutrefresh(boardwin);
        doupdate();
 
-       movecount = 0;
-       for (i = 0; i < BDEPTH; i++) {
-           for (j = 0; j < BWIDTH; j++) {
-               board[i][j] = FALSE;
+       for (i = 0; i < ylimit; i++) {
+           for (j = 0; j < xlimit; j++) {
+               squares[i][j] = FALSE;
                unmarkcell(i, j);
            }
        }
@@ -456,8 +628,8 @@ play(void)
        history[0].y = history[0].x = -1;
        history[1].y = history[1].x = -1;
        lastrow = lastcol = -2;
-       movecount = 1;
-       trialcount = 1;
+       count_moves = 1;
+       count_tries = 1;
        keyhelp = FALSE;
        show_help(&keyhelp);
 
@@ -465,7 +637,7 @@ play(void)
            if (rw != lastrow || col != lastcol) {
                if (lastrow >= 0 && lastcol >= 0) {
                    cellmove(lastrow, lastcol);
-                   if (board[lastrow][lastcol])
+                   if (squares[lastrow][lastcol])
                        waddch(boardwin, trail);
                    else
                        waddch(boardwin, oldch);
@@ -487,7 +659,7 @@ play(void)
            case 'k':
            case '8':
            case KEY_UP:
-               ny = rw + BDEPTH - 1;
+               ny = rw + ylimit - 1;
                nx = col;
                break;
            case 'j':
@@ -500,7 +672,7 @@ play(void)
            case '4':
            case KEY_LEFT:
                ny = rw;
-               nx = col + BWIDTH - 1;
+               nx = col + xlimit - 1;
                break;
            case 'l':
            case '6':
@@ -511,19 +683,19 @@ play(void)
            case 'y':
            case '7':
            case KEY_A1:
-               ny = rw + BDEPTH - 1;
-               nx = col + BWIDTH - 1;
+               ny = rw + ylimit - 1;
+               nx = col + xlimit - 1;
                break;
            case 'b':
            case '1':
            case KEY_C1:
                ny = rw + 1;
-               nx = col + BWIDTH - 1;
+               nx = col + xlimit - 1;
                break;
            case 'u':
            case '9':
            case KEY_A3:
-               ny = rw + BDEPTH - 1;
+               ny = rw + ylimit - 1;
                nx = col + 1;
                break;
            case 'n':
@@ -533,14 +705,15 @@ play(void)
                nx = col + 1;
                break;
 
-#ifdef NCURSES_MOUSE_VERSION
+#ifdef KEY_MOUSE
            case KEY_MOUSE:
+#ifdef NCURSES_MOUSE_VERSION
                {
                    MEVENT myevent;
 
                    getmouse(&myevent);
-                   if (myevent.y >= CY(0) && myevent.y <= CY(BDEPTH)
-                       && myevent.x >= CX(0) && myevent.x <= CX(BWIDTH)) {
+                   if (myevent.y >= CY(0) && myevent.y <= CY(ylimit)
+                       && myevent.x >= CX(0) && myevent.x <= CX(xlimit)) {
                        nx = CXINV(myevent.x);
                        ny = CYINV(myevent.y);
                        ungetch('\n');
@@ -551,23 +724,43 @@ play(void)
                    }
                }
 #endif /* NCURSES_MOUSE_VERSION */
+#ifdef PDCURSES
+               {
+                   int test_y, test_x;
+                   request_mouse_pos();
+                   test_y = MOUSE_Y_POS + 0;
+                   test_x = MOUSE_X_POS + 1;
+                   if (test_y >= CY(0) && test_y <= CY(ylimit)
+                       && test_x >= CX(0) && test_x <= CX(xlimit)) {
+                       ny = CYINV(test_y);
+                       nx = CXINV(test_x);
+                       wmove(helpwin, 0, 0);
+                       wrefresh(helpwin);
+                       ungetch('\n');
+                   }
+                   break;
+               }
+#endif /* PDCURSES */
+#endif /* KEY_MOUSE */
 
            case KEY_B2:
            case '\n':
            case ' ':
                review = 0;
-               if (evalmove(rw, col)) {
-                   drawmove(trail,
-                            history[movecount - 1].y,
-                            history[movecount - 1].x,
+               if (evaluate_move(squares, history, count_moves, rw, col)) {
+                   drawMove(squares,
+                            count_moves,
+                            trail,
+                            history[count_moves - 1].y,
+                            history[count_moves - 1].x,
                             rw, col);
-                   history[movecount].y = rw;
-                   history[movecount].x = col;
-                   movecount++;
-                   trialcount++;
+                   history[count_moves].y = (short) rw;
+                   history[count_moves].x = (short) col;
+                   count_moves++;
+                   count_tries++;
 
-                   if (!chkmoves(rw, col)) {
-                       if (completed() < 0) {
+                   if (boardIsFilled(squares, rw, col)) {
+                       if (completed(squares) < 0) {
                            waddstr(msgwin, "\nYou won.");
                        } else {
                            waddstr(msgwin,
@@ -583,40 +776,40 @@ play(void)
            case KEY_BACKSPACE:
            case '\b':
                review = 0;
-               if (movecount <= 0) {
+               if (count_moves <= 0) {
                    no_previous_move();
-               } else if (movecount <= 1) {
-                   ny = history[movecount].y;
-                   nx = history[movecount].x;
+               } else if (count_moves <= 1) {
+                   ny = history[count_moves].y;
+                   nx = history[count_moves].x;
                    if (nx < 0 || ny < 0) {
-                       ny = lastrow;
-                       nx = lastcol;
+                       ny = (lastrow >= 0) ? lastrow : 0;
+                       nx = (lastcol >= 0) ? lastcol : 0;
                    }
-                   movecount = 0;
-                   board[ny][nx] = FALSE;
+                   count_moves = 0;
+                   squares[ny][nx] = FALSE;
                    oldch = minus;
-                   drawmove(' ', ny, nx, -1, -1);
-                   movecount = 1;
-                   trialcount = 1;
+                   drawMove(squares, count_moves, ' ', ny, nx, -1, -1);
+                   count_moves = 1;
+                   count_tries = 1;
                    no_previous_move();
                } else {
-                   int oldy = history[movecount - 1].y;
-                   int oldx = history[movecount - 1].x;
+                   int oldy = history[count_moves - 1].y;
+                   int oldx = history[count_moves - 1].x;
 
-                   if (!board[rw][col]) {
+                   if (!squares[rw][col]) {
                        cellmove(rw, col);
                        waddch(boardwin, ' ');
                    }
 
-                   board[oldy][oldx] = FALSE;
-                   --movecount;
-                   ny = history[movecount - 1].y;
-                   nx = history[movecount - 1].x;
+                   squares[oldy][oldx] = FALSE;
+                   --count_moves;
+                   ny = history[count_moves - 1].y;
+                   nx = history[count_moves - 1].x;
                    if (nx < 0 || ny < 0) {
                        ny = oldy;
                        nx = oldx;
                    }
-                   drawmove(' ', oldy, oldx, ny, nx);
+                   drawMove(squares, count_moves, ' ', oldy, oldx, ny, nx);
 
                    /* avoid problems if we just changed the current cell */
                    cellmove(lastrow, lastcol);
@@ -627,29 +820,44 @@ play(void)
            case 'a':
                nx = col;
                ny = rw;
-               find_next_move(&ny, &nx);
+               if (find_next_move(squares, history, count_moves, &ny, &nx))
+                   count_next_moves(squares, count_moves, ny, nx);
+               else
+                   beep();
                break;
 
            case 'F':
-               if (review > 0) {
-                   review--;
-                   ny = history[movecount - review - 1].y;
-                   nx = history[movecount - review - 1].x;
-               } else {
-                   beep();
-               }
+               review = reviewHistory(history, count_moves, review - 1,
+                                      &ny, &nx);
                break;
 
            case 'B':
-               if (review < movecount - 2) {
-                   review++;
-                   ny = history[movecount - review - 1].y;
-                   nx = history[movecount - review - 1].x;
+               review = reviewHistory(history, count_moves, review + 1,
+                                      &ny, &nx);
+               break;
+
+           case 'R':
+               if (ylimit <= 6) {
+                   wprintw(msgwin, "\nworking...");
+                   wrefresh(msgwin);
+                   test_test = 0;
+                   test_size = useBacktracking(squares, history, count_moves);
+                   wprintw(msgwin, "\nOk %d:%d (%d tests)",
+                           test_size, maxmoves, test_test);
+                   review = 0;
+                   while (count_moves <= test_size) {
+                       markcell(trail,
+                                ny = history[count_moves].y,
+                                nx = history[count_moves].x);
+                       count_moves++;
+                   }
                } else {
-                   beep();
+                   wprintw(msgwin, "\nBoard is too large.");
                }
+               wrefresh(msgwin);
                break;
 
+#if HAVE_CURSCR
            case KEY_REDO:
            case '\f':
            case 'r':
@@ -660,12 +868,13 @@ play(void)
                wnoutrefresh(helpwin);
                doupdate();
                break;
+#endif
 
            case 'q':
            case 'x':
                goto dropout;
 
-           case '?':
+           case HELP_KEY_1:
                show_help(&keyhelp);
                break;
 
@@ -674,12 +883,12 @@ play(void)
                break;
            }
 
-           col = nx % BWIDTH;
-           rw = ny % BDEPTH;
+           col = nx % xlimit;
+           rw = ny % ylimit;
        }
 
       dropout:
-       if ((count = completed()) < 0)
+       if ((count = completed(squares)) < 0)
            wprintw(msgwin, "\nYou won.  Care to try again? ");
        else
            wprintw(msgwin, "\n%d squares filled.  Try again? ", count);
@@ -688,9 +897,55 @@ play(void)
        (tolower(wgetch(msgwin)) == 'y');
 }
 
+static void
+usage(void)
+{
+    static const char *msg[] =
+    {
+       "Usage: knight [options]"
+       ,""
+       ,"Options:"
+#if HAVE_USE_DEFAULT_COLORS
+       ," -d       invoke use_default_colors"
+#endif
+       ," -n NUM   set board-size to NUM*NUM (default 8x8)"
+    };
+    size_t n;
+
+    for (n = 0; n < SIZEOF(msg); n++)
+       fprintf(stderr, "%s\n", msg[n]);
+
+    ExitProgram(EXIT_FAILURE);
+}
+
 int
-main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
+main(int argc, char *argv[])
 {
+    int ch;
+
+    while ((ch = getopt(argc, argv, "dn:")) != -1) {
+       switch (ch) {
+#if HAVE_USE_DEFAULT_COLORS
+       case 'd':
+           d_option = TRUE;
+           break;
+#endif
+       case 'n':
+           ch = atoi(optarg);
+           if (ch < 3 || ch > 8) {
+               fprintf(stderr, "board size %d is outside [3..8]\n", ch);
+               usage();
+           }
+           xlimit = ylimit = ch;
+           break;
+       default:
+           usage();
+           /* NOTREACHED */
+       }
+    }
+    if (optind < argc)
+       usage();
+
     init_program();
 
     play();
@@ -698,5 +953,3 @@ main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
     endwin();
     ExitProgram(EXIT_SUCCESS);
 }
-
-/* knight.c ends here */