X-Git-Url: https://ncurses.scripts.mit.edu/?p=ncurses.git;a=blobdiff_plain;f=test%2Fknight.c;h=0d6675e5ba1689ad22ee843b7bbb2d8fec11c1a1;hp=44537d41d62132cc09b735ed43ec94685e161a3d;hb=31418a0e4a6f75ceffc9fee20ddbe390209a4ef4;hpb=a8987e73ec254703634802b4f7ee30d3a485524d diff --git a/test/knight.c b/test/knight.c index 44537d41..0d6675e5 100644 --- a/test/knight.c +++ b/test/knight.c @@ -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 * @@ -6,25 +33,26 @@ * Eric S. Raymond July 22 1995. Mouse support * added September 20th 1995. * - * $Id: knight.c,v 1.26 2002/10/19 22:11:24 tom Exp $ + * $Id: knight.c,v 1.44 2018/05/12 13:23:24 tom Exp $ */ #include /* 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 @@ -38,20 +66,28 @@ #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; @@ -66,6 +102,7 @@ static const struct { { 1, -2 }, { 2, -1 }, }; +#define MAX_OFFSET (unsigned)SIZEOF(offsets) /* *INDENT-ON* */ static void @@ -77,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); @@ -88,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; } @@ -128,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 @@ -148,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 @@ -172,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); @@ -214,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, ' '); @@ -225,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); @@ -239,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, ' '); @@ -248,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); @@ -261,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; } } @@ -308,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 @@ -334,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); } @@ -378,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."); @@ -400,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 @@ -418,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 */ @@ -428,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); @@ -443,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); } } @@ -454,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); @@ -463,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); @@ -485,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': @@ -498,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': @@ -509,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': @@ -531,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'); @@ -549,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, @@ -581,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); @@ -625,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': @@ -658,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; @@ -672,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); @@ -686,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(); @@ -696,5 +953,3 @@ main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED) endwin(); ExitProgram(EXIT_SUCCESS); } - -/* knight.c ends here */