1/**************************************************************************** 2 * Copyright (c) 1998-2006,2008 Free Software Foundation, Inc. * 3 * * 4 * Permission is hereby granted, free of charge, to any person obtaining a * 5 * copy of this software and associated documentation files (the * 6 * "Software"), to deal in the Software without restriction, including * 7 * without limitation the rights to use, copy, modify, merge, publish, * 8 * distribute, distribute with modifications, sublicense, and/or sell * 9 * copies of the Software, and to permit persons to whom the Software is * 10 * furnished to do so, subject to the following conditions: * 11 * * 12 * The above copyright notice and this permission notice shall be included * 13 * in all copies or substantial portions of the Software. * 14 * * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS * 16 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF * 17 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. * 18 * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, * 19 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR * 20 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR * 21 * THE USE OR OTHER DEALINGS IN THE SOFTWARE. * 22 * * 23 * Except as contained in this notice, the name(s) of the above copyright * 24 * holders shall not be used in advertising or otherwise to promote the * 25 * sale, use or other dealings in this Software without prior written * 26 * authorization. * 27 ****************************************************************************/ 28/* 29 * Knight's Tour - a brain game 30 * 31 * The original of this game was anonymous. It had an unbelievably bogus 32 * interface, you actually had to enter square coordinates! Redesign by 33 * Eric S. Raymond <esr@snark.thyrsus.com> July 22 1995. Mouse support 34 * added September 20th 1995. 35 * 36 * $Id: knight.c,v 1.28 2008/08/03 23:04:26 tom Exp $ 37 */ 38 39#include <test.priv.h> 40 41/* board size */ 42#define BDEPTH 8 43#define BWIDTH 8 44 45/* where to start the instructions */ 46#define INSTRY 2 47#define INSTRX 35 48 49/* corner of board */ 50#define BOARDY 2 51#define BOARDX 0 52 53/* notification line */ 54#define NOTIFYY 21 55 56/* virtual color values */ 57#define TRAIL_COLOR 1 58#define PLUS_COLOR 2 59#define MINUS_COLOR 3 60 61#define CX(x) (2 + 4 * (x)) 62#define CY(y) (1 + 2 * (y)) 63#define cellmove(y, x) wmove(boardwin, CY(y), CX(x)) 64#define CXINV(x) (((x) - 1) / 4) 65#define CYINV(y) (((y) - 2) / 2) 66 67typedef struct { 68 short x, y; 69} cell; 70 71static WINDOW *boardwin; /* the board window */ 72static WINDOW *helpwin; /* the help window */ 73static WINDOW *msgwin; /* the message window */ 74static cell history[BDEPTH * BWIDTH + 1]; /* choice history */ 75static chtype minus = '-'; /* possible-move character */ 76static chtype oldch; 77static chtype plus = '+'; /* cursor hot-spot character */ 78static chtype trail = '#'; /* trail character */ 79static int movecount; /* count of moves so far */ 80static int trialcount; /* count of trials so far */ 81static short board[BDEPTH][BWIDTH]; /* the squares */ 82/* *INDENT-OFF* */ 83static const struct { 84 int y; 85 int x; 86} offsets[] = { 87 { 2, 1 }, 88 { 1, 2 }, 89 { -1, 2 }, 90 { -2, 1 }, 91 { -2, -1 }, 92 { -1, -2 }, 93 { 1, -2 }, 94 { 2, -1 }, 95}; 96/* *INDENT-ON* */ 97 98static void 99init_program(void) 100{ 101 setlocale(LC_ALL, ""); 102 103 srand((unsigned) getpid()); 104 initscr(); 105 cbreak(); /* immediate char return */ 106 noecho(); /* no immediate echo */ 107 boardwin = newwin(BDEPTH * 2 + 1, BWIDTH * 4 + 1, BOARDY, BOARDX); 108 helpwin = newwin(0, 0, INSTRY, INSTRX); 109 msgwin = newwin(1, INSTRX - 1, NOTIFYY, 0); 110 scrollok(msgwin, TRUE); 111 keypad(boardwin, TRUE); 112 113 if (has_colors()) { 114 int bg = COLOR_BLACK; 115 116 start_color(); 117#if HAVE_USE_DEFAULT_COLORS 118 if (use_default_colors() == OK) 119 bg = -1; 120#endif 121 122 (void) init_pair(TRAIL_COLOR, COLOR_CYAN, bg); 123 (void) init_pair(PLUS_COLOR, COLOR_RED, bg); 124 (void) init_pair(MINUS_COLOR, COLOR_GREEN, bg); 125 126 trail |= COLOR_PAIR(TRAIL_COLOR); 127 plus |= COLOR_PAIR(PLUS_COLOR); 128 minus |= COLOR_PAIR(MINUS_COLOR); 129 } 130#ifdef NCURSES_MOUSE_VERSION 131 (void) mousemask(BUTTON1_CLICKED, (mmask_t *) NULL); 132#endif /* NCURSES_MOUSE_VERSION */ 133 134 oldch = minus; 135} 136 137static void 138help1(void) 139/* game explanation -- initial help screen */ 140{ 141 (void) waddstr(helpwin, "Knight's move is a solitaire puzzle. Your\n"); 142 (void) waddstr(helpwin, "objective is to visit each square of the \n"); 143 (void) waddstr(helpwin, "chessboard exactly once by making knight's\n"); 144 (void) waddstr(helpwin, "moves (one square right or left followed \n"); 145 (void) waddstr(helpwin, "by two squares up or down, or two squares \n"); 146 (void) waddstr(helpwin, "right or left followed by one square up or\n"); 147 (void) waddstr(helpwin, "down). You may start anywhere.\n\n"); 148 149 (void) waddstr(helpwin, "Use arrow keys to move the cursor around.\n"); 150 (void) waddstr(helpwin, "When you want to move your knight to the \n"); 151 (void) waddstr(helpwin, "cursor location, press <space> or Enter.\n"); 152 (void) waddstr(helpwin, "Illegal moves will be rejected with an \n"); 153 (void) waddstr(helpwin, "audible beep.\n\n"); 154 (void) waddstr(helpwin, "The program will detect if you solve the\n"); 155 (void) waddstr(helpwin, "puzzle; also inform you when you run out\n"); 156 (void) waddstr(helpwin, "of legal moves.\n\n"); 157 158 (void) mvwaddstr(helpwin, NOTIFYY - INSTRY, 0, 159 "Press `?' to go to keystroke help."); 160} 161 162static void 163help2(void) 164/* keystroke help screen */ 165{ 166 (void) waddstr(helpwin, "Possible moves are shown with `-'.\n\n"); 167 168 (void) waddstr(helpwin, "You can move around with the arrow keys or\n"); 169 (void) waddstr(helpwin, "with the rogue/hack movement keys. Other\n"); 170 (void) waddstr(helpwin, "commands allow you to undo moves or redraw.\n"); 171 (void) waddstr(helpwin, "Your mouse may work; try left-button to\n"); 172 (void) waddstr(helpwin, "move to the square under the pointer.\n\n"); 173 174 (void) waddstr(helpwin, "x,q -- exit y k u 7 8 9\n"); 175 (void) waddstr(helpwin, "r -- redraw screen \\|/ \\|/ \n"); 176 (void) waddstr(helpwin, "bksp -- undo move h-+-l 4-+-6\n"); 177 (void) waddstr(helpwin, "a -- autojump /|\\ /|\\ \n"); 178 (void) waddstr(helpwin, " b j n 1 2 3\n"); 179 180 (void) waddstr(helpwin, "\nYou can place your knight on the selected\n"); 181 (void) waddstr(helpwin, "square with spacebar, Enter, or the keypad\n"); 182 (void) waddstr(helpwin, "center key. Use F/B to review the path.\n"); 183 184 (void) mvwaddstr(helpwin, NOTIFYY - INSTRY, 0, 185 "Press `?' to go to game explanation"); 186} 187 188static void 189show_help(bool * keyhelp) 190{ 191 werase(helpwin); 192 if (*keyhelp) { 193 help1(); 194 *keyhelp = FALSE; 195 } else { 196 help2(); 197 *keyhelp = TRUE; 198 } 199 wrefresh(helpwin); 200} 201 202static bool 203chksqr(int r1, int c1) 204{ 205 if ((r1 < 0) || (r1 > BDEPTH - 1)) 206 return (FALSE); 207 if ((c1 < 0) || (c1 > BWIDTH - 1)) 208 return (FALSE); 209 return ((!board[r1][c1]) ? TRUE : FALSE); 210} 211 212static bool 213chkmoves(int rw, int col) 214/* check to see if valid moves are available */ 215{ 216 unsigned n; 217 218 for (n = 0; n < SIZEOF(offsets); n++) 219 if (chksqr(rw + offsets[n].y, col + offsets[n].x)) 220 return (TRUE); 221 return (FALSE); 222} 223 224static void 225dosquares(void) 226{ 227 int i, j; 228 229 mvaddstr(0, 20, "KNIGHT'S MOVE -- a logical solitaire"); 230 231 move(BOARDY, BOARDX); 232 waddch(boardwin, ACS_ULCORNER); 233 for (j = 0; j < 7; j++) { 234 waddch(boardwin, ACS_HLINE); 235 waddch(boardwin, ACS_HLINE); 236 waddch(boardwin, ACS_HLINE); 237 waddch(boardwin, ACS_TTEE); 238 } 239 waddch(boardwin, ACS_HLINE); 240 waddch(boardwin, ACS_HLINE); 241 waddch(boardwin, ACS_HLINE); 242 waddch(boardwin, ACS_URCORNER); 243 244 for (i = 1; i < BDEPTH; i++) { 245 move(BOARDY + i * 2 - 1, BOARDX); 246 waddch(boardwin, ACS_VLINE); 247 for (j = 0; j < BWIDTH; j++) { 248 waddch(boardwin, ' '); 249 waddch(boardwin, ' '); 250 waddch(boardwin, ' '); 251 waddch(boardwin, ACS_VLINE); 252 } 253 move(BOARDY + i * 2, BOARDX); 254 waddch(boardwin, ACS_LTEE); 255 for (j = 0; j < BWIDTH - 1; j++) { 256 waddch(boardwin, ACS_HLINE); 257 waddch(boardwin, ACS_HLINE); 258 waddch(boardwin, ACS_HLINE); 259 waddch(boardwin, ACS_PLUS); 260 } 261 waddch(boardwin, ACS_HLINE); 262 waddch(boardwin, ACS_HLINE); 263 waddch(boardwin, ACS_HLINE); 264 waddch(boardwin, ACS_RTEE); 265 } 266 267 move(BOARDY + i * 2 - 1, BOARDX); 268 waddch(boardwin, ACS_VLINE); 269 for (j = 0; j < BWIDTH; j++) { 270 waddch(boardwin, ' '); 271 waddch(boardwin, ' '); 272 waddch(boardwin, ' '); 273 waddch(boardwin, ACS_VLINE); 274 } 275 276 move(BOARDY + i * 2, BOARDX); 277 waddch(boardwin, ACS_LLCORNER); 278 for (j = 0; j < BWIDTH - 1; j++) { 279 waddch(boardwin, ACS_HLINE); 280 waddch(boardwin, ACS_HLINE); 281 waddch(boardwin, ACS_HLINE); 282 waddch(boardwin, ACS_BTEE); 283 } 284 waddch(boardwin, ACS_HLINE); 285 waddch(boardwin, ACS_HLINE); 286 waddch(boardwin, ACS_HLINE); 287 waddch(boardwin, ACS_LRCORNER); 288} 289 290static void 291mark_possibles(int prow, int pcol, chtype mark) 292{ 293 unsigned n; 294 295 for (n = 0; n < SIZEOF(offsets); n++) { 296 if (chksqr(prow + offsets[n].y, pcol + offsets[n].x)) { 297 cellmove(prow + offsets[n].y, pcol + offsets[n].x); 298 waddch(boardwin, mark); 299 } 300 } 301} 302 303static void 304find_next_move(int *y, int *x) 305{ 306 unsigned j, k; 307 int found = -1; 308 int first = -1; 309 int next = 0; 310 int oldy, oldx; 311 int newy, newx; 312 313 if (movecount > 1) { 314 oldy = history[movecount - 1].y; 315 oldx = history[movecount - 1].x; 316 for (j = 0; j < SIZEOF(offsets) * 2; j++) { 317 k = j % SIZEOF(offsets); 318 newy = oldy + offsets[k].y; 319 newx = oldx + offsets[k].x; 320 if (chksqr(newy, newx)) { 321 if (first < 0) 322 first = k; 323 if (newy == *y 324 && newx == *x) { 325 found = k; 326 } else if (found >= 0) { 327 next = k; 328 break; 329 } 330 } 331 } 332 if (found < 0) 333 next = first; 334 if (next >= 0) { 335 *y = oldy + offsets[next].y; 336 *x = oldx + offsets[next].x; 337 } 338 } else { 339 beep(); 340 } 341} 342 343static void 344unmarkcell(int row, int column) 345{ 346 cellmove(row, column); 347 waddch(boardwin, '\b'); 348 waddch(boardwin, ' '); 349 waddch(boardwin, minus); 350 waddch(boardwin, ' '); 351} 352 353static void 354markcell(chtype tchar, int row, int column) 355{ 356 cellmove(row, column); 357 waddch(boardwin, '\b'); 358 waddch(boardwin, tchar); 359 waddch(boardwin, tchar); 360 waddch(boardwin, tchar); 361} 362 363static void 364drawmove(chtype tchar, int oldy, int oldx, int row, int column) 365/* place the stars, update board & currents */ 366{ 367 if (movecount <= 1) { 368 int i, j; 369 370 for (i = 0; i < BDEPTH; i++) { 371 for (j = 0; j < BWIDTH; j++) { 372 if (movecount == 0) { 373 unmarkcell(i, j); 374 } else { 375 cellmove(i, j); 376 if (winch(boardwin) == minus) 377 waddch(boardwin, movecount ? ' ' : minus); 378 } 379 } 380 } 381 } else { 382 markcell(tchar, oldy, oldx); 383 mark_possibles(oldy, oldx, ' '); 384 } 385 386 if (row >= 0 && column >= 0) { 387 markcell(trail, row, column); 388 mark_possibles(row, column, minus); 389 board[row][column] = TRUE; 390 } 391 392 wprintw(msgwin, "\nMove %d", movecount); 393 if (trialcount != movecount) 394 wprintw(msgwin, " (%d tries)", trialcount); 395 wclrtoeol(msgwin); 396} 397 398static int 399iabs(int num) 400{ 401 if (num < 0) 402 return (-num); 403 else 404 return (num); 405} 406 407static bool 408evalmove(int row, int column) 409/* evaluate move */ 410{ 411 if (movecount == 1) 412 return (TRUE); 413 else if (board[row][column] == TRUE) { 414 waddstr(msgwin, "\nYou've already been there."); 415 return (FALSE); 416 } else { 417 int rdif = iabs(row - history[movecount - 1].y); 418 int cdif = iabs(column - history[movecount - 1].x); 419 420 if (!((rdif == 1) && (cdif == 2)) && !((rdif == 2) && (cdif == 1))) { 421 waddstr(msgwin, "\nThat's not a legal knight's move."); 422 return (FALSE); 423 } 424 } 425 426 return (TRUE); 427} 428 429static int 430completed(void) 431{ 432 int i, j, count = 0; 433 434 for (i = 0; i < BDEPTH; i++) 435 for (j = 0; j < BWIDTH; j++) 436 if (board[i][j] != 0) 437 count += 1; 438 return (count == (BWIDTH * BDEPTH) ? -1 : count); 439} 440 441static void 442no_previous_move(void) 443{ 444 waddstr(msgwin, "\nNo previous move."); 445 beep(); 446} 447 448static void 449play(void) 450/* play the game */ 451{ 452 bool keyhelp; /* TRUE if keystroke help is up */ 453 int i, j, count; 454 int lastcol = 0; /* last location visited */ 455 int lastrow = 0; 456 int ny = 0, nx = 0; 457 int review = 0; /* review history */ 458 int rw = 0, col = 0; /* current row and column */ 459 460 do { 461 /* clear screen and draw board */ 462 werase(boardwin); 463 werase(helpwin); 464 werase(msgwin); 465 dosquares(); 466 help1(); 467 wnoutrefresh(stdscr); 468 wnoutrefresh(helpwin); 469 wnoutrefresh(msgwin); 470 wnoutrefresh(boardwin); 471 doupdate(); 472 473 movecount = 0; 474 for (i = 0; i < BDEPTH; i++) { 475 for (j = 0; j < BWIDTH; j++) { 476 board[i][j] = FALSE; 477 unmarkcell(i, j); 478 } 479 } 480 memset(history, 0, sizeof(history)); 481 history[0].y = history[0].x = -1; 482 history[1].y = history[1].x = -1; 483 lastrow = lastcol = -2; 484 movecount = 1; 485 trialcount = 1; 486 keyhelp = FALSE; 487 show_help(&keyhelp); 488 489 for (;;) { 490 if (rw != lastrow || col != lastcol) { 491 if (lastrow >= 0 && lastcol >= 0) { 492 cellmove(lastrow, lastcol); 493 if (board[lastrow][lastcol]) 494 waddch(boardwin, trail); 495 else 496 waddch(boardwin, oldch); 497 } 498 499 cellmove(rw, col); 500 oldch = winch(boardwin); 501 502 lastrow = rw; 503 lastcol = col; 504 } 505 cellmove(rw, col); 506 waddch(boardwin, plus); 507 cellmove(rw, col); 508 509 wrefresh(msgwin); 510 511 switch (wgetch(boardwin)) { 512 case 'k': 513 case '8': 514 case KEY_UP: 515 ny = rw + BDEPTH - 1; 516 nx = col; 517 break; 518 case 'j': 519 case '2': 520 case KEY_DOWN: 521 ny = rw + 1; 522 nx = col; 523 break; 524 case 'h': 525 case '4': 526 case KEY_LEFT: 527 ny = rw; 528 nx = col + BWIDTH - 1; 529 break; 530 case 'l': 531 case '6': 532 case KEY_RIGHT: 533 ny = rw; 534 nx = col + 1; 535 break; 536 case 'y': 537 case '7': 538 case KEY_A1: 539 ny = rw + BDEPTH - 1; 540 nx = col + BWIDTH - 1; 541 break; 542 case 'b': 543 case '1': 544 case KEY_C1: 545 ny = rw + 1; 546 nx = col + BWIDTH - 1; 547 break; 548 case 'u': 549 case '9': 550 case KEY_A3: 551 ny = rw + BDEPTH - 1; 552 nx = col + 1; 553 break; 554 case 'n': 555 case '3': 556 case KEY_C3: 557 ny = rw + 1; 558 nx = col + 1; 559 break; 560 561#ifdef NCURSES_MOUSE_VERSION 562 case KEY_MOUSE: 563 { 564 MEVENT myevent; 565 566 getmouse(&myevent); 567 if (myevent.y >= CY(0) && myevent.y <= CY(BDEPTH) 568 && myevent.x >= CX(0) && myevent.x <= CX(BWIDTH)) { 569 nx = CXINV(myevent.x); 570 ny = CYINV(myevent.y); 571 ungetch('\n'); 572 break; 573 } else { 574 beep(); 575 continue; 576 } 577 } 578#endif /* NCURSES_MOUSE_VERSION */ 579 580 case KEY_B2: 581 case '\n': 582 case ' ': 583 review = 0; 584 if (evalmove(rw, col)) { 585 drawmove(trail, 586 history[movecount - 1].y, 587 history[movecount - 1].x, 588 rw, col); 589 history[movecount].y = rw; 590 history[movecount].x = col; 591 movecount++; 592 trialcount++; 593 594 if (!chkmoves(rw, col)) { 595 if (completed() < 0) { 596 waddstr(msgwin, "\nYou won."); 597 } else { 598 waddstr(msgwin, 599 "\nNo further moves are possible."); 600 } 601 } 602 } else { 603 beep(); 604 } 605 break; 606 607 case KEY_UNDO: 608 case KEY_BACKSPACE: 609 case '\b': 610 review = 0; 611 if (movecount <= 0) { 612 no_previous_move(); 613 } else if (movecount <= 1) { 614 ny = history[movecount].y; 615 nx = history[movecount].x; 616 if (nx < 0 || ny < 0) { 617 ny = lastrow; 618 nx = lastcol; 619 } 620 movecount = 0; 621 board[ny][nx] = FALSE; 622 oldch = minus; 623 drawmove(' ', ny, nx, -1, -1); 624 movecount = 1; 625 trialcount = 1; 626 no_previous_move(); 627 } else { 628 int oldy = history[movecount - 1].y; 629 int oldx = history[movecount - 1].x; 630 631 if (!board[rw][col]) { 632 cellmove(rw, col); 633 waddch(boardwin, ' '); 634 } 635 636 board[oldy][oldx] = FALSE; 637 --movecount; 638 ny = history[movecount - 1].y; 639 nx = history[movecount - 1].x; 640 if (nx < 0 || ny < 0) { 641 ny = oldy; 642 nx = oldx; 643 } 644 drawmove(' ', oldy, oldx, ny, nx); 645 646 /* avoid problems if we just changed the current cell */ 647 cellmove(lastrow, lastcol); 648 oldch = winch(boardwin); 649 } 650 break; 651 652 case 'a': 653 nx = col; 654 ny = rw; 655 find_next_move(&ny, &nx); 656 break; 657 658 case 'F': 659 if (review > 0) { 660 review--; 661 ny = history[movecount - review - 1].y; 662 nx = history[movecount - review - 1].x; 663 } else { 664 beep(); 665 } 666 break; 667 668 case 'B': 669 if (review < movecount - 2) { 670 review++; 671 ny = history[movecount - review - 1].y; 672 nx = history[movecount - review - 1].x; 673 } else { 674 beep(); 675 } 676 break; 677 678 case KEY_REDO: 679 case '\f': 680 case 'r': 681 clearok(curscr, TRUE); 682 wnoutrefresh(stdscr); 683 wnoutrefresh(boardwin); 684 wnoutrefresh(msgwin); 685 wnoutrefresh(helpwin); 686 doupdate(); 687 break; 688 689 case 'q': 690 case 'x': 691 goto dropout; 692 693 case '?': 694 show_help(&keyhelp); 695 break; 696 697 default: 698 beep(); 699 break; 700 } 701 702 col = nx % BWIDTH; 703 rw = ny % BDEPTH; 704 } 705 706 dropout: 707 if ((count = completed()) < 0) 708 wprintw(msgwin, "\nYou won. Care to try again? "); 709 else 710 wprintw(msgwin, "\n%d squares filled. Try again? ", count); 711 wclrtoeol(msgwin); 712 } while 713 (tolower(wgetch(msgwin)) == 'y'); 714} 715 716int 717main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED) 718{ 719 init_program(); 720 721 play(); 722 723 endwin(); 724 ExitProgram(EXIT_SUCCESS); 725} 726 727/* knight.c ends here */ 728