X-Git-Url: http://ncurses.scripts.mit.edu/?p=ncurses.git;a=blobdiff_plain;f=test%2Fknight.c;h=f9f725b0fc6c96ae9270aac9ac6c19d4478f0559;hp=ad923b42b1de37a08ac68ee026f4afef8d442519;hb=312665d3aaaf5d8e3ba34d80fdd650abf758272a;hpb=b1f61d9f3aa244512045a6b02e759825d7049d34 diff --git a/test/knight.c b/test/knight.c index ad923b42..f9f725b0 100644 --- a/test/knight.c +++ b/test/knight.c @@ -1,3 +1,31 @@ +/**************************************************************************** + * Copyright 2018-2020,2021 Thomas E. Dickey * + * Copyright 1998-2013,2017 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,396 +34,229 @@ * Eric S. Raymond July 22 1995. Mouse support * added September 20th 1995. * - * $Id: knight.c,v 1.15 1999/11/13 23:39:10 tom Exp $ + * $Id: knight.c,v 1.48 2021/04/25 00:10:43 tom Exp $ */ #include -#include -#include -#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 #define PLUS_COLOR 2 #define MINUS_COLOR 3 -#define CX(x) (2 + 4 * (x)) -#define CY(y) (1 + 2 * (y)) +#define CX(x) (2 + 4 * (x)) +#define CY(y) (1 + 2 * (y)) #define cellmove(y, x) wmove(boardwin, CY(y), CX(x)) #define CXINV(x) (((x) - 1) / 4) #define CYINV(y) (((y) - 2) / 2) -typedef struct -{ - short x, y; -} -cell; - -static short board[BDEPTH][BWIDTH]; /* the squares */ -static int rw,col; /* current row and column */ -static int lastrow,lastcol; /* last location visited */ -static cell history[BDEPTH*BWIDTH]; /* choice history */ -static int movecount; /* count of moves so far */ -static WINDOW *boardwin; /* the board window */ -static WINDOW *helpwin; /* the help window */ -static WINDOW *msgwin; /* the message window */ -static chtype trail = '#'; /* trail character */ -static chtype plus = '+'; /* cursor hot-spot character */ -static chtype minus = '-'; /* possible-move character */ -static chtype oldch; - -static void init(void); -static void play(void); -static void dosquares(void); -static void drawmove(char, int, int, int, int); -static bool evalmove(int, int); -static bool chkmoves(void); -static bool chksqr(int, int); -static int iabs(int); - -int main( - int argc GCC_UNUSED, - char *argv[] GCC_UNUSED) -{ - init(); +typedef struct { + int x, y; +} HISTORY; - play(); +typedef int SQUARES[YLIMIT][XLIMIT]; - endwin(); - return EXIT_SUCCESS; -} +static WINDOW *boardwin; /* the board window */ +static WINDOW *helpwin; /* the help window */ +static WINDOW *msgwin; /* the message window */ + +#if HAVE_USE_DEFAULT_COLORS +static bool d_option; +#endif -static void init (void) +static chtype minus = '-'; /* possible-move character */ +static chtype oldch; +static chtype plus = '+'; /* cursor hot-spot character */ +static chtype trail = '#'; /* trail character */ + +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; + int x; +} offsets[] = { + { 2, 1 }, + { 1, 2 }, + { -1, 2 }, + { -2, 1 }, + { -2, -1 }, + { -1, -2 }, + { 1, -2 }, + { 2, -1 }, +}; +#define MAX_OFFSET (unsigned)SIZEOF(offsets) +/* *INDENT-ON* */ + +static void +init_program(void) { - srand ((unsigned)getpid()); - initscr (); - cbreak (); /* immediate char return */ - noecho (); /* no immediate echo */ - boardwin = newwin(BDEPTH * 2 + 1, BWIDTH * 4 + 1, BOARDY, BOARDX); + setlocale(LC_ALL, ""); + + srand((unsigned) getpid()); + initscr(); + cbreak(); /* immediate char return */ + noecho(); /* no immediate echo */ + + 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); + msgwin = newwin(1, INSTRX - 1, NOTIFYY, 0); + scrollok(msgwin, TRUE); keypad(boardwin, TRUE); - if (has_colors()) - { + if (has_colors()) { int bg = COLOR_BLACK; start_color(); -#ifdef HAVE_USE_DEFAULT_COLORS - if (use_default_colors() == OK) +#if HAVE_USE_DEFAULT_COLORS + 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*/ + (void) mousemask(BUTTON1_CLICKED, (mmask_t *) NULL); +#endif /* NCURSES_MOUSE_VERSION */ +#if defined(PDCURSES) + mouse_set(BUTTON1_RELEASED); +#endif oldch = minus; } -static void help1(void) +static void +help1(void) /* game explanation -- initial help screen */ { - (void)waddstr(helpwin, "Knight's move is a solitaire puzzle. Your\n"); - (void)waddstr(helpwin, "objective is to visit each square of the \n"); - (void)waddstr(helpwin, "chessboard exactly once by making knight's\n"); - (void)waddstr(helpwin, "moves (one square right or left followed \n"); - (void)waddstr(helpwin, "by two squares up or down, or two squares \n"); - (void)waddstr(helpwin, "right or left followed by one square up or\n"); - (void)waddstr(helpwin, "down). You may start anywhere.\n\n"); - - (void)waddstr(helpwin, "Use arrow keys to move the cursor around.\n"); - (void)waddstr(helpwin, "When you want to move your knight to the \n"); - (void)waddstr(helpwin, "cursor location, press or Enter.\n"); - (void)waddstr(helpwin, "Illegal moves will be rejected with an \n"); - (void)waddstr(helpwin, "audible beep.\n\n"); - (void)waddstr(helpwin, "The program will detect if you solve the\n"); - (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."); + (void) waddstr(helpwin, "Knight's move is a solitaire puzzle. Your\n"); + (void) waddstr(helpwin, "objective is to visit each square of the \n"); + (void) waddstr(helpwin, "chessboard exactly once by making knight's\n"); + (void) waddstr(helpwin, "moves (one square right or left followed \n"); + (void) waddstr(helpwin, "by two squares up or down, or two squares \n"); + (void) waddstr(helpwin, "right or left followed by one square up or\n"); + (void) waddstr(helpwin, "down). You may start anywhere.\n\n"); + + (void) waddstr(helpwin, "Use arrow keys to move the cursor around.\n"); + (void) waddstr(helpwin, "When you want to move your knight to the \n"); + (void) waddstr(helpwin, "cursor location, press or Enter.\n"); + (void) waddstr(helpwin, "Illegal moves will be rejected with an \n"); + (void) waddstr(helpwin, "audible beep.\n\n"); + (void) waddstr(helpwin, "The program will detect if you solve the\n"); + (void) waddstr(helpwin, "puzzle; also inform you when you run out\n"); + (void) waddstr(helpwin, "of legal moves.\n\n"); + + MvWAddStr(helpwin, NOTIFYY - INSTRY, 0, + "Press `?' to go to keystroke help."); } -static void help2(void) +static void +help2(void) /* keystroke help screen */ { - (void)waddstr(helpwin, "Possible moves are shown with `-'.\n\n"); - - (void)waddstr(helpwin, "You can move around with the arrow keys or\n"); - (void)waddstr(helpwin, "with the rogue/hack movement keys. Other\n"); - (void)waddstr(helpwin, "commands allow you to undo moves or redraw.\n"); - (void)waddstr(helpwin, "Your mouse may work; try left-button to\n"); - (void)waddstr(helpwin, "move to the square under the pointer.\n\n"); - - (void)waddstr(helpwin, "x,q -- exit y k u 7 8 9\n"); - (void)waddstr(helpwin, "r -- redraw screen \\|/ \\|/ \n"); - (void)waddstr(helpwin, "u -- undo move h-+-l 4-+-6\n"); - (void)waddstr(helpwin, " /|\\ /|\\ \n"); - (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. You can quit with `x' or `q'.\n"); - - (void)mvwaddstr(helpwin, NOTIFYY-INSTRY, 0, - "Press `?' to go to game explanation"); + (void) waddstr(helpwin, "Possible moves are shown with `-'.\n\n"); + + (void) waddstr(helpwin, "You can move around with the arrow keys or\n"); + (void) waddstr(helpwin, "with the rogue/hack movement keys. Other\n"); + (void) waddstr(helpwin, "commands allow you to undo moves or redraw.\n"); + (void) waddstr(helpwin, "Your mouse may work; try left-button to\n"); + (void) waddstr(helpwin, "move to the square under the pointer.\n\n"); + + (void) waddstr(helpwin, "x,q -- exit y k u 7 8 9\n"); + (void) waddstr(helpwin, "r -- redraw screen \\|/ \\|/ \n"); + (void) waddstr(helpwin, "bksp -- undo move h-+-l 4-+-6\n"); + (void) waddstr(helpwin, "a -- autojump /|\\ /|\\ \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"); + + MvWAddStr(helpwin, NOTIFYY - INSTRY, 0, + "Press `?' to go to game explanation"); +} + +static void +show_help(bool * keyhelp) +{ + werase(helpwin); + if (*keyhelp) { + help1(); + *keyhelp = FALSE; + } else { + help2(); + *keyhelp = TRUE; + } + wrefresh(helpwin); } -static void play (void) -/* play the game */ +static inline bool +isValidYX(int y, int x) { - bool keyhelp; /* TRUE if keystroke help is up */ - int c, ny = 0, nx = 0; - int i, j, count; + return (y >= 0 && y < ylimit && x >= 0 && x < xlimit) ? TRUE : FALSE; +} - do { - /* clear screen and draw board */ - werase(boardwin); - werase(helpwin); - werase(msgwin); - dosquares(); - help1(); - wnoutrefresh(stdscr); - wnoutrefresh(helpwin); - wnoutrefresh(msgwin); - wnoutrefresh(boardwin); - doupdate(); - - for (i = 0; i < BDEPTH; i++) - for (j = 0; j < BWIDTH; j++) - { - board[i][j] = FALSE; - cellmove(i, j); - waddch(boardwin, minus); - } - memset(history, '\0', sizeof(history)); - history[0].y = history[0].x = -1; - lastrow = lastcol = -2; - movecount = 1; - keyhelp = FALSE; - - for (;;) - { - if (rw != lastrow || col != lastcol) - { - if (lastrow >= 0 && lastcol >= 0) - { - cellmove(lastrow, lastcol); - if (board[lastrow][lastcol]) - waddch(boardwin, trail); - else - waddch(boardwin, oldch); - } - - cellmove(rw, col); - oldch = winch(boardwin); - - lastrow = rw; - lastcol= col; - } - cellmove(rw, col); - waddch(boardwin, plus); - cellmove(rw, col); - - wrefresh(msgwin); - - c = wgetch(boardwin); - - werase(msgwin); - - switch (c) - { - case 'k': case '8': - case KEY_UP: - ny = rw+BDEPTH-1; nx = col; - break; - case 'j': case '2': - case KEY_DOWN: - ny = rw+1; nx = col; - break; - case 'h': case '4': - case KEY_LEFT: - ny = rw; nx = col+BWIDTH-1; - break; - case 'l': case '6': - case KEY_RIGHT: - ny = rw; nx = col+1; - break; - case 'y': case '7': - case KEY_A1: - ny = rw+BDEPTH-1; nx = col+BWIDTH-1; - break; - case 'b': case '1': - case KEY_C1: - ny = rw+1; nx = col+BWIDTH-1; - break; - case 'u': case '9': - case KEY_A3: - ny = rw+BDEPTH-1; nx = col+1; - break; - case 'n': case '3': - case KEY_C3: - ny = rw+1; nx = col+1; - break; +static inline bool +isUnusedYX(SQUARES squares, int y, int x) +{ + return (isValidYX(y, x) && (!squares[y][x]) ? TRUE : FALSE); +} -#ifdef NCURSES_MOUSE_VERSION - case KEY_MOUSE: - { - MEVENT myevent; - - getmouse(&myevent); - if (myevent.y >= CY(0) && myevent.y <= CY(BDEPTH) - && myevent.x >= CX(0) && myevent.x <= CX(BWIDTH)) - { - nx = CXINV(myevent.x); - ny = CYINV(myevent.y); - ungetch('\n'); - break; - } - else - { - beep(); - continue; - } - } -#endif /* NCURSES_MOUSE_VERSION */ +static bool +boardIsFilled(SQUARES squares, int y, int x) +{ + unsigned n; - case KEY_B2: - case '\n': - case ' ': - if (evalmove(rw, col)) - { - drawmove(trail, - history[movecount-1].y, history[movecount-1].x, - rw, col); - history[movecount].y = rw; - history[movecount].x = col; - movecount++; - - if (!chkmoves()) - goto dropout; - } - else - beep(); - break; - - case KEY_REDO: - case '\f': - case 'r': - clearok(curscr, TRUE); - wnoutrefresh(stdscr); - wnoutrefresh(boardwin); - wnoutrefresh(msgwin); - wnoutrefresh(helpwin); - doupdate(); - break; - - case KEY_UNDO: - case KEY_BACKSPACE: - case '\b': - if (movecount == 1) - { - ny = lastrow; - nx = lastcol; - waddstr(msgwin, "\nNo previous move."); - beep(); - } - else - { - int oldy = history[movecount-1].y; - int oldx = history[movecount-1].x; - - board[oldy][oldx] = FALSE; - --movecount; - ny = history[movecount-1].y; - nx = history[movecount-1].x; - drawmove(' ', oldy, oldx, ny, nx); - - /* avoid problems if we just changed the current cell */ - cellmove(lastrow, lastcol); - oldch = winch(boardwin); - } - break; - - case 'q': - case 'x': - goto dropout; - - case '?': - werase(helpwin); - if (keyhelp) - { - help1(); - keyhelp = FALSE; - } - else - { - help2(); - keyhelp = TRUE; - } - wrefresh(helpwin); - break; - - default: - beep(); - break; - } - - col = nx % BWIDTH; - rw = ny % BDEPTH; - } - - dropout: - count = 0; - for (i = 0; i < BDEPTH; i++) - for (j = 0; j < BWIDTH; j++) - if (board[i][j] != 0) - count += 1; - if (count == (BWIDTH * BDEPTH)) - wprintw(msgwin, "\nYou won. Care to try again? "); - else - wprintw(msgwin, "\n%d squares filled. Try again? ", count); - } while - (tolower(wgetch(msgwin)) == 'y'); + 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) +static 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); + 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); @@ -406,21 +267,18 @@ static void 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++) - { + waddch(boardwin, ACS_VLINE); + for (j = 0; j < xlimit; j++) { waddch(boardwin, ' '); waddch(boardwin, ' '); waddch(boardwin, ' '); waddch(boardwin, ACS_VLINE); } move(BOARDY + i * 2, BOARDX); - waddch(boardwin, ACS_LTEE); - for (j = 0; j < BWIDTH - 1; j++) - { + waddch(boardwin, ACS_LTEE); + for (j = 0; j < xlimit - 1; j++) { waddch(boardwin, ACS_HLINE); waddch(boardwin, ACS_HLINE); waddch(boardwin, ACS_HLINE); @@ -434,8 +292,7 @@ static void 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, ' '); @@ -444,8 +301,7 @@ static void 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); @@ -457,109 +313,644 @@ static void dosquares (void) waddch(boardwin, ACS_LRCORNER); } -static void mark_possibles(int prow, int pcol, chtype mark) +static void +mark_possibles(SQUARES squares, int y, int x, chtype mark) +{ + unsigned n; + + 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 bool +find_next_move(SQUARES squares, HISTORY * doneData, int doneSize, int *y, int *x) +{ + bool result = FALSE; + + if (doneSize > 1) { + unsigned j; + int oldy = doneData[doneSize - 1].y; + int oldx = doneData[doneSize - 1].x; + int found = -1; + int first = -1; + int next = -1; + + for (j = 0; j < MAX_OFFSET * 2; j++) { + unsigned k = j % MAX_OFFSET; + int newy = oldy + offsets[k].y; + int newx = oldx + offsets[k].x; + if (isUnusedYX(squares, newy, newx)) { + if (first < 0) + first = (int) k; + if (newy == *y + && newx == *x) { + found = (int) k; + } else if (found >= 0) { + next = (int) k; + break; + } + } + } + if (found < 0) + next = first; + if (next >= 0) { + *y = oldy + offsets[next].y; + *x = oldx + offsets[next].x; + } + 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 +unmarkcell(int row, int column) +{ + cellmove(row, column); + waddch(boardwin, '\b'); + waddch(boardwin, ' '); + waddch(boardwin, minus); + waddch(boardwin, ' '); +} + +static void +markcell(chtype tchar, int row, int column) { - if (chksqr(prow+2,pcol+1)){cellmove(prow+2,pcol+1);waddch(boardwin,mark);}; - if (chksqr(prow+2,pcol-1)){cellmove(prow+2,pcol-1);waddch(boardwin,mark);}; - if (chksqr(prow-2,pcol+1)){cellmove(prow-2,pcol+1);waddch(boardwin,mark);}; - if (chksqr(prow-2,pcol-1)){cellmove(prow-2,pcol-1);waddch(boardwin,mark);}; - if (chksqr(prow+1,pcol+2)){cellmove(prow+1,pcol+2);waddch(boardwin,mark);}; - if (chksqr(prow+1,pcol-2)){cellmove(prow+1,pcol-2);waddch(boardwin,mark);}; - if (chksqr(prow-1,pcol+2)){cellmove(prow-1,pcol+2);waddch(boardwin,mark);}; - if (chksqr(prow-1,pcol-2)){cellmove(prow-1,pcol-2);waddch(boardwin,mark);}; + cellmove(row, column); + waddch(boardwin, '\b'); + waddch(boardwin, tchar); + waddch(boardwin, tchar); + waddch(boardwin, tchar); } -static void drawmove(char tchar, int oldy, int oldx, int row, int column) +static void +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++) - { - cellmove(i, j); - if (winch(boardwin) == minus) - waddch(boardwin, movecount ? ' ' : minus); + 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, ' '); + } } - } - else - { - cellmove(oldy, oldx); - waddch(boardwin, '\b'); - waddch(boardwin, tchar); - waddch(boardwin, tchar); - waddch(boardwin, tchar); - mark_possibles(oldy, oldx, ' '); + } + } else { + markcell(tchar, oldy, oldx); + mark_possibles(squares, oldy, oldx, ' '); } - if (row != -1 && column != -1) - { - cellmove(row, column); - waddch(boardwin, '\b'); - waddch(boardwin, trail); - waddch(boardwin, trail); - waddch(boardwin, trail); - mark_possibles(row, column, minus); - board[row][column] = TRUE; + if (row >= 0 && column >= 0) { + markcell(trail, row, column); + mark_possibles(squares, row, column, minus); + squares[row][column] = TRUE; } - wprintw(msgwin, "\nMove %d", movecount); + wprintw(msgwin, "\nMove %d", count_moves); + if (count_tries != count_moves) + wprintw(msgwin, " (%d tries)", count_tries); + wclrtoeol(msgwin); } -static bool evalmove(int row, int column) -/* evaluate move */ +static int +iabs(int num) { - if (movecount == 1) - return(TRUE); - else if (board[row][column] == TRUE) - { - waddstr(msgwin, "\nYou've already been there."); - return(FALSE); - } + if (num < 0) + return (-num); else - { - int rdif = iabs(row - history[movecount-1].y); - int cdif = iabs(column - history[movecount-1].x); + return (num); +} - if (!((rdif == 1) && (cdif == 2)) && !((rdif == 2) && (cdif == 1))) - { +static bool +evaluate_move(SQUARES squares, HISTORY * doneData, int doneSize, int row, int column) +{ + if (doneSize <= 1) + return (TRUE); + else if (squares[row][column] == TRUE) { + waddstr(msgwin, "\nYou've already been there."); + return (FALSE); + } else { + 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."); - return(FALSE); + return (FALSE); + } + } + + return (TRUE); +} + +static int +completed(SQUARES squares) +{ + int i, j, count = 0; + + for (i = 0; i < ylimit; i++) { + for (j = 0; j < xlimit; j++) { + if (squares[i][j] != 0) { + count += 1; + } + } + } + return ((count == maxmoves) ? -1 : count); +} + +static void +no_previous_move(void) +{ + waddstr(msgwin, "\nNo previous move."); + 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) { + unsigned k; + + for (k = 0; k < MAX_OFFSET; k++) { + int try_x = x + offsets[k].x; + int 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... */ + } } } - return(TRUE); + 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 bool chkmoves (void) -/* check to see if valid moves are available */ +static int +reviewHistory(HISTORY * history, int count_moves, int review, int *ny, int *nx) { - if (chksqr(rw+2,col+1)) return(TRUE); - if (chksqr(rw+2,col-1)) return(TRUE); - if (chksqr(rw-2,col+1)) return(TRUE); - if (chksqr(rw-2,col-1)) return(TRUE); - if (chksqr(rw+1,col+2)) return(TRUE); - if (chksqr(rw+1,col-2)) return(TRUE); - if (chksqr(rw-1,col+2)) return(TRUE); - if (chksqr(rw-1,col-2)) return(TRUE); - return (FALSE); + 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 int iabs(int num) +static void +play(void) +/* play the game */ { - if (num < 0) return (-num); - else return (num); + bool keyhelp; /* TRUE if keystroke help is up */ + int i, j, count; + int lastcol; /* last location visited */ + int lastrow; + 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); + drawBoard(); + help1(); + wnoutrefresh(stdscr); + wnoutrefresh(helpwin); + wnoutrefresh(msgwin); + wnoutrefresh(boardwin); + doupdate(); + + for (i = 0; i < ylimit; i++) { + for (j = 0; j < xlimit; j++) { + squares[i][j] = FALSE; + unmarkcell(i, j); + } + } + memset(history, 0, sizeof(history)); + history[0].y = history[0].x = -1; + history[1].y = history[1].x = -1; + lastrow = lastcol = -2; + count_moves = 1; + count_tries = 1; + keyhelp = FALSE; + show_help(&keyhelp); + + for (;;) { + if (rw != lastrow || col != lastcol) { + if (lastrow >= 0 && lastcol >= 0) { + cellmove(lastrow, lastcol); + if (squares[lastrow][lastcol]) + waddch(boardwin, trail); + else + waddch(boardwin, oldch); + } + + cellmove(rw, col); + oldch = winch(boardwin); + + lastrow = rw; + lastcol = col; + } + cellmove(rw, col); + waddch(boardwin, plus); + cellmove(rw, col); + + wrefresh(msgwin); + + switch (wgetch(boardwin)) { + case 'k': + case '8': + case KEY_UP: + ny = rw + ylimit - 1; + nx = col; + break; + case 'j': + case '2': + case KEY_DOWN: + ny = rw + 1; + nx = col; + break; + case 'h': + case '4': + case KEY_LEFT: + ny = rw; + nx = col + xlimit - 1; + break; + case 'l': + case '6': + case KEY_RIGHT: + ny = rw; + nx = col + 1; + break; + case 'y': + case '7': + case KEY_A1: + ny = rw + ylimit - 1; + nx = col + xlimit - 1; + break; + case 'b': + case '1': + case KEY_C1: + ny = rw + 1; + nx = col + xlimit - 1; + break; + case 'u': + case '9': + case KEY_A3: + ny = rw + ylimit - 1; + nx = col + 1; + break; + case 'n': + case '3': + case KEY_C3: + ny = rw + 1; + nx = col + 1; + break; + +#ifdef KEY_MOUSE + case KEY_MOUSE: +#ifdef NCURSES_MOUSE_VERSION + { + MEVENT myevent; + + getmouse(&myevent); + 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'); + break; + } else { + beep(); + continue; + } + } +#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 (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[count_moves].y = (short) rw; + history[count_moves].x = (short) col; + count_moves++; + count_tries++; + + if (boardIsFilled(squares, rw, col)) { + if (completed(squares) < 0) { + waddstr(msgwin, "\nYou won."); + } else { + waddstr(msgwin, + "\nNo further moves are possible."); + } + } + } else { + beep(); + } + break; + + case KEY_UNDO: + case KEY_BACKSPACE: + case '\b': + review = 0; + if (count_moves <= 0) { + no_previous_move(); + } else if (count_moves <= 1) { + ny = history[count_moves].y; + nx = history[count_moves].x; + if (nx < 0 || ny < 0) { + ny = (lastrow >= 0) ? lastrow : 0; + nx = (lastcol >= 0) ? lastcol : 0; + } + count_moves = 0; + squares[ny][nx] = FALSE; + oldch = minus; + drawMove(squares, count_moves, ' ', ny, nx, -1, -1); + count_moves = 1; + count_tries = 1; + no_previous_move(); + } else { + int oldy = history[count_moves - 1].y; + int oldx = history[count_moves - 1].x; + + if (!squares[rw][col]) { + cellmove(rw, col); + waddch(boardwin, ' '); + } + + 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(squares, count_moves, ' ', oldy, oldx, ny, nx); + + /* avoid problems if we just changed the current cell */ + cellmove(lastrow, lastcol); + oldch = winch(boardwin); + } + break; + + case 'a': + nx = col; + ny = rw; + if (find_next_move(squares, history, count_moves, &ny, &nx)) + count_next_moves(squares, count_moves, ny, nx); + else + beep(); + break; + + case 'F': + review = reviewHistory(history, count_moves, review - 1, + &ny, &nx); + break; + + case 'B': + 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 { + wprintw(msgwin, "\nBoard is too large."); + } + wrefresh(msgwin); + break; + +#if HAVE_CURSCR + case KEY_REDO: + case '\f': + case 'r': + clearok(curscr, TRUE); + wnoutrefresh(stdscr); + wnoutrefresh(boardwin); + wnoutrefresh(msgwin); + wnoutrefresh(helpwin); + doupdate(); + break; +#endif + + case 'q': + case 'x': + goto dropout; + + case HELP_KEY_1: + show_help(&keyhelp); + break; + + default: + beep(); + break; + } + + col = nx % xlimit; + rw = ny % ylimit; + } + + dropout: + if ((count = completed(squares)) < 0) + wprintw(msgwin, "\nYou won. Care to try again? "); + else + wprintw(msgwin, "\n%d squares filled. Try again? ", count); + wclrtoeol(msgwin); + } while + (tolower(wgetch(msgwin)) == 'y'); } -static bool chksqr (int r1, int c1) +static void +usage(void) { - if ((r1 < 0) || (r1 > BDEPTH - 1)) - return(FALSE); - if ((c1 < 0) || (c1 > BWIDTH - 1)) - return(FALSE); - return ((!board[r1][c1]) ? TRUE : FALSE); + 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); } -/* knight.c ends here */ +int +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(); + + endwin(); + ExitProgram(EXIT_SUCCESS); +}