1 /****************************************************************************
2 * Copyright (c) 1998-2012,2013 Free Software Foundation, Inc. *
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: *
12 * The above copyright notice and this permission notice shall be included *
13 * in all copies or substantial portions of the Software. *
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. *
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 *
27 ****************************************************************************/
29 * Knight's Tour - a brain game
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.
36 * $Id: knight.c,v 1.36 2013/02/16 19:53:08 tom Exp $
39 #include <test.priv.h>
45 /* where to start the instructions */
53 /* notification line */
56 /* virtual color values */
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)
71 static WINDOW
*boardwin
; /* the board window */
72 static WINDOW
*helpwin
; /* the help window */
73 static WINDOW
*msgwin
; /* the message window */
74 static cell history
[BDEPTH
* BWIDTH
+ 1]; /* choice history */
75 static chtype minus
= '-'; /* possible-move character */
77 static chtype plus
= '+'; /* cursor hot-spot character */
78 static chtype trail
= '#'; /* trail character */
79 static int movecount
; /* count of moves so far */
80 static int trialcount
; /* count of trials so far */
81 static short board
[BDEPTH
][BWIDTH
]; /* the squares */
101 setlocale(LC_ALL
, "");
103 srand((unsigned) getpid());
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
);
114 int bg
= COLOR_BLACK
;
117 #if HAVE_USE_DEFAULT_COLORS
118 if (use_default_colors() == OK
)
122 (void) init_pair(TRAIL_COLOR
, (short) COLOR_CYAN
, (short) bg
);
123 (void) init_pair(PLUS_COLOR
, (short) COLOR_RED
, (short) bg
);
124 (void) init_pair(MINUS_COLOR
, (short) COLOR_GREEN
, (short) bg
);
126 trail
|= (chtype
) COLOR_PAIR(TRAIL_COLOR
);
127 plus
|= (chtype
) COLOR_PAIR(PLUS_COLOR
);
128 minus
|= (chtype
) COLOR_PAIR(MINUS_COLOR
);
130 #ifdef NCURSES_MOUSE_VERSION
131 (void) mousemask(BUTTON1_CLICKED
, (mmask_t
*) NULL
);
132 #endif /* NCURSES_MOUSE_VERSION */
133 #if defined(PDCURSES)
134 mouse_set(BUTTON1_RELEASED
);
142 /* game explanation -- initial help screen */
144 (void) waddstr(helpwin
, "Knight's move is a solitaire puzzle. Your\n");
145 (void) waddstr(helpwin
, "objective is to visit each square of the \n");
146 (void) waddstr(helpwin
, "chessboard exactly once by making knight's\n");
147 (void) waddstr(helpwin
, "moves (one square right or left followed \n");
148 (void) waddstr(helpwin
, "by two squares up or down, or two squares \n");
149 (void) waddstr(helpwin
, "right or left followed by one square up or\n");
150 (void) waddstr(helpwin
, "down). You may start anywhere.\n\n");
152 (void) waddstr(helpwin
, "Use arrow keys to move the cursor around.\n");
153 (void) waddstr(helpwin
, "When you want to move your knight to the \n");
154 (void) waddstr(helpwin
, "cursor location, press <space> or Enter.\n");
155 (void) waddstr(helpwin
, "Illegal moves will be rejected with an \n");
156 (void) waddstr(helpwin
, "audible beep.\n\n");
157 (void) waddstr(helpwin
, "The program will detect if you solve the\n");
158 (void) waddstr(helpwin
, "puzzle; also inform you when you run out\n");
159 (void) waddstr(helpwin
, "of legal moves.\n\n");
161 MvWAddStr(helpwin
, NOTIFYY
- INSTRY
, 0,
162 "Press `?' to go to keystroke help.");
167 /* keystroke help screen */
169 (void) waddstr(helpwin
, "Possible moves are shown with `-'.\n\n");
171 (void) waddstr(helpwin
, "You can move around with the arrow keys or\n");
172 (void) waddstr(helpwin
, "with the rogue/hack movement keys. Other\n");
173 (void) waddstr(helpwin
, "commands allow you to undo moves or redraw.\n");
174 (void) waddstr(helpwin
, "Your mouse may work; try left-button to\n");
175 (void) waddstr(helpwin
, "move to the square under the pointer.\n\n");
177 (void) waddstr(helpwin
, "x,q -- exit y k u 7 8 9\n");
178 (void) waddstr(helpwin
, "r -- redraw screen \\|/ \\|/ \n");
179 (void) waddstr(helpwin
, "bksp -- undo move h-+-l 4-+-6\n");
180 (void) waddstr(helpwin
, "a -- autojump /|\\ /|\\ \n");
181 (void) waddstr(helpwin
, " b j n 1 2 3\n");
183 (void) waddstr(helpwin
, "\nYou can place your knight on the selected\n");
184 (void) waddstr(helpwin
, "square with spacebar, Enter, or the keypad\n");
185 (void) waddstr(helpwin
, "center key. Use F/B to review the path.\n");
187 MvWAddStr(helpwin
, NOTIFYY
- INSTRY
, 0,
188 "Press `?' to go to game explanation");
192 show_help(bool * keyhelp
)
206 chksqr(int r1
, int c1
)
208 if ((r1
< 0) || (r1
> BDEPTH
- 1))
210 if ((c1
< 0) || (c1
> BWIDTH
- 1))
212 return ((!board
[r1
][c1
]) ? TRUE
: FALSE
);
216 chkmoves(int rw
, int col
)
217 /* check to see if valid moves are available */
221 for (n
= 0; n
< SIZEOF(offsets
); n
++)
222 if (chksqr(rw
+ offsets
[n
].y
, col
+ offsets
[n
].x
))
232 MvAddStr(0, 20, "KNIGHT'S MOVE -- a logical solitaire");
234 move(BOARDY
, BOARDX
);
235 waddch(boardwin
, ACS_ULCORNER
);
236 for (j
= 0; j
< 7; j
++) {
237 waddch(boardwin
, ACS_HLINE
);
238 waddch(boardwin
, ACS_HLINE
);
239 waddch(boardwin
, ACS_HLINE
);
240 waddch(boardwin
, ACS_TTEE
);
242 waddch(boardwin
, ACS_HLINE
);
243 waddch(boardwin
, ACS_HLINE
);
244 waddch(boardwin
, ACS_HLINE
);
245 waddch(boardwin
, ACS_URCORNER
);
247 for (i
= 1; i
< BDEPTH
; i
++) {
248 move(BOARDY
+ i
* 2 - 1, BOARDX
);
249 waddch(boardwin
, ACS_VLINE
);
250 for (j
= 0; j
< BWIDTH
; j
++) {
251 waddch(boardwin
, ' ');
252 waddch(boardwin
, ' ');
253 waddch(boardwin
, ' ');
254 waddch(boardwin
, ACS_VLINE
);
256 move(BOARDY
+ i
* 2, BOARDX
);
257 waddch(boardwin
, ACS_LTEE
);
258 for (j
= 0; j
< BWIDTH
- 1; j
++) {
259 waddch(boardwin
, ACS_HLINE
);
260 waddch(boardwin
, ACS_HLINE
);
261 waddch(boardwin
, ACS_HLINE
);
262 waddch(boardwin
, ACS_PLUS
);
264 waddch(boardwin
, ACS_HLINE
);
265 waddch(boardwin
, ACS_HLINE
);
266 waddch(boardwin
, ACS_HLINE
);
267 waddch(boardwin
, ACS_RTEE
);
270 move(BOARDY
+ i
* 2 - 1, BOARDX
);
271 waddch(boardwin
, ACS_VLINE
);
272 for (j
= 0; j
< BWIDTH
; j
++) {
273 waddch(boardwin
, ' ');
274 waddch(boardwin
, ' ');
275 waddch(boardwin
, ' ');
276 waddch(boardwin
, ACS_VLINE
);
279 move(BOARDY
+ i
* 2, BOARDX
);
280 waddch(boardwin
, ACS_LLCORNER
);
281 for (j
= 0; j
< BWIDTH
- 1; j
++) {
282 waddch(boardwin
, ACS_HLINE
);
283 waddch(boardwin
, ACS_HLINE
);
284 waddch(boardwin
, ACS_HLINE
);
285 waddch(boardwin
, ACS_BTEE
);
287 waddch(boardwin
, ACS_HLINE
);
288 waddch(boardwin
, ACS_HLINE
);
289 waddch(boardwin
, ACS_HLINE
);
290 waddch(boardwin
, ACS_LRCORNER
);
294 mark_possibles(int prow
, int pcol
, chtype mark
)
298 for (n
= 0; n
< SIZEOF(offsets
); n
++) {
299 if (chksqr(prow
+ offsets
[n
].y
, pcol
+ offsets
[n
].x
)) {
300 cellmove(prow
+ offsets
[n
].y
, pcol
+ offsets
[n
].x
);
301 waddch(boardwin
, mark
);
307 find_next_move(int *y
, int *x
)
318 oldy
= history
[movecount
- 1].y
;
319 oldx
= history
[movecount
- 1].x
;
320 for (j
= 0; j
< SIZEOF(offsets
) * 2; j
++) {
321 k
= j
% SIZEOF(offsets
);
322 newy
= oldy
+ offsets
[k
].y
;
323 newx
= oldx
+ offsets
[k
].x
;
324 if (chksqr(newy
, newx
)) {
330 } else if (found
>= 0) {
339 *y
= oldy
+ offsets
[next
].y
;
340 *x
= oldx
+ offsets
[next
].x
;
348 count_next_moves(int y
, int x
)
353 wprintw(msgwin
, "\nMove %d", movecount
);
354 for (j
= 0; j
< SIZEOF(offsets
); j
++) {
355 int newy
= y
+ offsets
[j
].y
;
356 int newx
= x
+ offsets
[j
].x
;
357 if (chksqr(newy
, newx
)) {
361 wprintw(msgwin
, ", gives %d choices", count
);
366 unmarkcell(int row
, int column
)
368 cellmove(row
, column
);
369 waddch(boardwin
, '\b');
370 waddch(boardwin
, ' ');
371 waddch(boardwin
, minus
);
372 waddch(boardwin
, ' ');
376 markcell(chtype tchar
, int row
, int column
)
378 cellmove(row
, column
);
379 waddch(boardwin
, '\b');
380 waddch(boardwin
, tchar
);
381 waddch(boardwin
, tchar
);
382 waddch(boardwin
, tchar
);
386 drawmove(chtype tchar
, int oldy
, int oldx
, int row
, int column
)
387 /* place the stars, update board & currents */
389 if (movecount
<= 1) {
392 for (i
= 0; i
< BDEPTH
; i
++) {
393 for (j
= 0; j
< BWIDTH
; j
++) {
394 if (movecount
== 0) {
398 if (winch(boardwin
) == minus
)
399 waddch(boardwin
, movecount
? ' ' : minus
);
404 markcell(tchar
, oldy
, oldx
);
405 mark_possibles(oldy
, oldx
, ' ');
408 if (row
>= 0 && column
>= 0) {
409 markcell(trail
, row
, column
);
410 mark_possibles(row
, column
, minus
);
411 board
[row
][column
] = TRUE
;
414 wprintw(msgwin
, "\nMove %d", movecount
);
415 if (trialcount
!= movecount
)
416 wprintw(msgwin
, " (%d tries)", trialcount
);
430 evalmove(int row
, int column
)
435 else if (board
[row
][column
] == TRUE
) {
436 waddstr(msgwin
, "\nYou've already been there.");
439 int rdif
= iabs(row
- history
[movecount
- 1].y
);
440 int cdif
= iabs(column
- history
[movecount
- 1].x
);
442 if (!((rdif
== 1) && (cdif
== 2)) && !((rdif
== 2) && (cdif
== 1))) {
443 waddstr(msgwin
, "\nThat's not a legal knight's move.");
456 for (i
= 0; i
< BDEPTH
; i
++)
457 for (j
= 0; j
< BWIDTH
; j
++)
458 if (board
[i
][j
] != 0)
460 return (count
== (BWIDTH
* BDEPTH
) ? -1 : count
);
464 no_previous_move(void)
466 waddstr(msgwin
, "\nNo previous move.");
474 bool keyhelp
; /* TRUE if keystroke help is up */
476 int lastcol
= 0; /* last location visited */
479 int review
= 0; /* review history */
480 int rw
= 0, col
= 0; /* current row and column */
483 /* clear screen and draw board */
489 wnoutrefresh(stdscr
);
490 wnoutrefresh(helpwin
);
491 wnoutrefresh(msgwin
);
492 wnoutrefresh(boardwin
);
496 for (i
= 0; i
< BDEPTH
; i
++) {
497 for (j
= 0; j
< BWIDTH
; j
++) {
502 memset(history
, 0, sizeof(history
));
503 history
[0].y
= history
[0].x
= -1;
504 history
[1].y
= history
[1].x
= -1;
505 lastrow
= lastcol
= -2;
512 if (rw
!= lastrow
|| col
!= lastcol
) {
513 if (lastrow
>= 0 && lastcol
>= 0) {
514 cellmove(lastrow
, lastcol
);
515 if (board
[lastrow
][lastcol
])
516 waddch(boardwin
, trail
);
518 waddch(boardwin
, oldch
);
522 oldch
= winch(boardwin
);
528 waddch(boardwin
, plus
);
533 switch (wgetch(boardwin
)) {
537 ny
= rw
+ BDEPTH
- 1;
550 nx
= col
+ BWIDTH
- 1;
561 ny
= rw
+ BDEPTH
- 1;
562 nx
= col
+ BWIDTH
- 1;
568 nx
= col
+ BWIDTH
- 1;
573 ny
= rw
+ BDEPTH
- 1;
585 #ifdef NCURSES_MOUSE_VERSION
590 if (myevent
.y
>= CY(0) && myevent
.y
<= CY(BDEPTH
)
591 && myevent
.x
>= CX(0) && myevent
.x
<= CX(BWIDTH
)) {
592 nx
= CXINV(myevent
.x
);
593 ny
= CYINV(myevent
.y
);
601 #endif /* NCURSES_MOUSE_VERSION */
606 test_y
= MOUSE_Y_POS
+ 0;
607 test_x
= MOUSE_X_POS
+ 1;
608 if (test_y
>= CY(0) && test_y
<= CY(BDEPTH
)
609 && test_x
>= CX(0) && test_x
<= CX(BWIDTH
)) {
612 wmove(helpwin
, 0, 0);
618 #endif /* PDCURSES */
619 #endif /* KEY_MOUSE */
625 if (evalmove(rw
, col
)) {
627 history
[movecount
- 1].y
,
628 history
[movecount
- 1].x
,
630 history
[movecount
].y
= (short) rw
;
631 history
[movecount
].x
= (short) col
;
635 if (!chkmoves(rw
, col
)) {
636 if (completed() < 0) {
637 waddstr(msgwin
, "\nYou won.");
640 "\nNo further moves are possible.");
652 if (movecount
<= 0) {
654 } else if (movecount
<= 1) {
655 ny
= history
[movecount
].y
;
656 nx
= history
[movecount
].x
;
657 if (nx
< 0 || ny
< 0) {
658 ny
= (lastrow
>= 0) ? lastrow
: 0;
659 nx
= (lastcol
>= 0) ? lastcol
: 0;
662 board
[ny
][nx
] = FALSE
;
664 drawmove(' ', ny
, nx
, -1, -1);
669 int oldy
= history
[movecount
- 1].y
;
670 int oldx
= history
[movecount
- 1].x
;
672 if (!board
[rw
][col
]) {
674 waddch(boardwin
, ' ');
677 board
[oldy
][oldx
] = FALSE
;
679 ny
= history
[movecount
- 1].y
;
680 nx
= history
[movecount
- 1].x
;
681 if (nx
< 0 || ny
< 0) {
685 drawmove(' ', oldy
, oldx
, ny
, nx
);
687 /* avoid problems if we just changed the current cell */
688 cellmove(lastrow
, lastcol
);
689 oldch
= winch(boardwin
);
696 if (find_next_move(&ny
, &nx
))
697 count_next_moves(ny
, nx
);
705 ny
= history
[movecount
- review
- 1].y
;
706 nx
= history
[movecount
- review
- 1].x
;
713 if (review
< movecount
- 2) {
715 ny
= history
[movecount
- review
- 1].y
;
716 nx
= history
[movecount
- review
- 1].x
;
725 clearok(curscr
, TRUE
);
726 wnoutrefresh(stdscr
);
727 wnoutrefresh(boardwin
);
728 wnoutrefresh(msgwin
);
729 wnoutrefresh(helpwin
);
751 if ((count
= completed()) < 0)
752 wprintw(msgwin
, "\nYou won. Care to try again? ");
754 wprintw(msgwin
, "\n%d squares filled. Try again? ", count
);
757 (tolower(wgetch(msgwin
)) == 'y');
761 main(int argc GCC_UNUSED
, char *argv
[]GCC_UNUSED
)
768 ExitProgram(EXIT_SUCCESS
);
771 /* knight.c ends here */