2 * Copyright (C) 2008 Carl Worth
4 * This program is free software: you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation, either version 3 of the License, or
7 * (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program. If not, see http://www.gnu.org/licenses/ .
17 * Author: Carl Worth <cworth@cworth.org>
29 #include "loa-board.h"
32 loa_move_is_valid (const loa_move_t *move)
34 return (move->x1 >= 0 && move->x1 < LOA_BOARD_SIZE &&
35 move->y1 >= 0 && move->y1 < LOA_BOARD_SIZE &&
36 move->x2 >= 0 && move->x2 < LOA_BOARD_SIZE &&
37 move->y2 >= 0 && move->y2 < LOA_BOARD_SIZE);
41 loa_move_to_string (const loa_move_t *move)
43 #define LOA_MOVE_STRING_SIZE 6
44 static char move_string[LOA_MOVE_STRING_SIZE];
46 if (! loa_move_is_valid (move)) {
47 strcpy (move_string, "***");
51 snprintf (move_string, LOA_MOVE_STRING_SIZE,
53 'a' + move->x1, LOA_BOARD_SIZE - move->y1,
54 move->is_capture ? 'x' : '-',
55 'a' + move->x2, LOA_BOARD_SIZE - move->y2);
61 loa_move_init_from_string (loa_move_t *move, const char *string)
67 /* Avoid returning uninitialized data on error. */
74 matched = sscanf (string, " %c%d%c%c%d", &xc1, &y1, &sep, &xc2, &y2);
76 printf ("Matched only %d fields of %s\n", matched, string);
80 x1 = tolower (xc1) - 'a';
81 x2 = tolower (xc2) - 'a';
82 y1 = LOA_BOARD_SIZE - y1;
83 y2 = LOA_BOARD_SIZE - y2;
85 if (x1 < 0 || x1 >= LOA_BOARD_SIZE ||
86 y1 < 0 || y1 >= LOA_BOARD_SIZE ||
87 x2 < 0 || x2 >= LOA_BOARD_SIZE ||
88 y2 < 0 || y2 >= LOA_BOARD_SIZE)
93 if (sep != '-' && sep != 'x' && sep != 'X')
101 if (sep == 'x' || sep == 'X')
102 move->is_capture = TRUE;
104 move->is_capture = FALSE;
109 /* Given an (x,y) position on the board, return the index of the array
110 * used to count pieces in diagonal rows running from upper-left to
111 * lower-right, (like a grave accent: à or like a backslash: \).
113 * This is the array to look into when a move occurs with dx and dy of
116 _grave_index (int x, int y)
118 return x - y + LOA_BOARD_SIZE - 1;
121 /* Given an (x,y) position on the board, return the index of the array
122 * used to count pieces in diagonal rows running from lower-left to
123 * upper-right, (like an acute accent: á or like a forward slash: /).
125 * This is the array to look into when a move occurs with dx and dy of
126 * opposite sign, (one positive, one negative). */
128 _acute_index (int x, int y)
134 loa_board_add_piece (loa_board_t *board, int x, int y, loa_cell_t cell)
136 assert (cell == LOA_CELL_BLACK || cell == LOA_CELL_WHITE);
137 assert (board->cells[x][y] == LOA_CELL_EMPTY);
139 board->col_pieces[x]++;
140 board->row_pieces[y]++;
141 board->diag_grave_pieces[_grave_index (x, y)]++;
142 board->diag_acute_pieces[_acute_index (x, y)]++;
144 board->num_pieces[cell]++;
146 board->cells[x][y] = cell;
150 loa_board_remove_piece (loa_board_t *board, int x, int y)
154 cell = board->cells[x][y];
156 if (cell == LOA_CELL_EMPTY)
157 return LOA_CELL_EMPTY;
159 board->col_pieces[x]--;
160 board->row_pieces[y]--;
161 board->diag_grave_pieces[_grave_index (x, y)]--;
162 board->diag_acute_pieces[_acute_index (x, y)]--;
164 board->num_pieces[cell]--;
166 board->cells[x][y] = LOA_CELL_EMPTY;
172 loa_board_init (loa_board_t *board)
175 board->moves_size = 0;
177 loa_board_reset (board);
181 loa_board_fini (loa_board_t *board)
188 loa_board_reset (loa_board_t *board)
192 for (x = 0; x < LOA_BOARD_SIZE; x++)
193 for (y = 0; y < LOA_BOARD_SIZE; y++)
194 board->cells[x][y] = LOA_CELL_EMPTY;
196 board->num_pieces[LOA_CELL_BLACK] = 0;
197 board->num_pieces[LOA_CELL_WHITE] = 0;
199 for (i = 0; i < LOA_BOARD_SIZE; i++) {
200 board->row_pieces[i] = 0;
201 board->col_pieces[i] = 0;
204 for (i = 0; i < LOA_DIAG_ARRAY_SIZE; i++) {
205 board->diag_grave_pieces[i] = 0;
206 board->diag_acute_pieces[i] = 0;
209 for (i = 1; i < LOA_BOARD_SIZE - 1; i++) {
210 loa_board_add_piece (board, i, 0, LOA_CELL_BLACK);
211 loa_board_add_piece (board, i, LOA_BOARD_SIZE - 1, LOA_CELL_BLACK);
212 loa_board_add_piece (board, 0, i, LOA_CELL_WHITE);
213 loa_board_add_piece (board, LOA_BOARD_SIZE - 1, i, LOA_CELL_WHITE);
216 /* Leave board->moves and board->moves_size as allocated */
217 board->num_moves = 0;
219 board->player = LOA_PLAYER_BLACK;
223 loa_board_group_size_recursive (loa_board_t *board, int x, int y,
232 if (x >= LOA_BOARD_SIZE || y >= LOA_BOARD_SIZE)
235 bit = 1ll << (x * LOA_BOARD_SIZE + y);
241 if (board->cells[x][y] != cell)
245 loa_board_group_size_recursive (board, x-1, y-1, cell, visited) +
246 loa_board_group_size_recursive (board, x-1, y , cell, visited) +
247 loa_board_group_size_recursive (board, x-1, y+1, cell, visited) +
248 loa_board_group_size_recursive (board, x , y-1, cell, visited) +
249 loa_board_group_size_recursive (board, x , y , cell, visited) +
250 loa_board_group_size_recursive (board, x , y+1, cell, visited) +
251 loa_board_group_size_recursive (board, x+1, y-1, cell, visited) +
252 loa_board_group_size_recursive (board, x+1, y , cell, visited) +
253 loa_board_group_size_recursive (board, x+1, y+1, cell, visited);
257 loa_board_group_size (loa_board_t *board, int x, int y)
259 uint64_t visited = 0ll;
260 loa_cell_t cell = board->cells[x][y];
262 return loa_board_group_size_recursive (board, x, y, cell, &visited);
266 loa_board_is_won (loa_board_t *board, int x, int y)
268 loa_cell_t cell = board->cells[x][y];
270 if (cell == LOA_CELL_EMPTY)
273 if (loa_board_group_size (board, x, y) == board->num_pieces[cell])
280 loa_board_move_legal (loa_board_t *board,
281 const loa_move_t *move,
289 if (! loa_move_is_valid (move))
291 *error = "Invalid coordinates (not on board)";
300 if (board->cells[x1][y1] == LOA_CELL_EMPTY) {
301 *error = "There is no piece there to move";
305 if (board->cells[x1][y1] != board->player) {
306 *error = "You cannot move your opponent's piece";
310 if (board->cells[x2][y2] == board->cells[x1][y1]) {
311 *error = "You cannot capture your own piece";
318 /* Here's the meat of Lines of Action legaility: Does the distance
319 * moved exactly match the number of pieces (of either color) in
320 * the row, column, or diagonal of the movement. */
323 if (abs (dy) != board->col_pieces[x1]) {
324 *error = "The move distance does not match the number of pieces in that column";
327 } else if (dy == 0) {
329 if (abs (dx) != board->row_pieces[y1]) {
330 *error = "The move distance does not match the number of pieces in that row";
334 if (abs (dx) != abs (dy)) {
335 *error = "That move is not in a row, column, or diagonal";
339 if ((dx > 0) == (dy > 0)) {
340 if (abs (dx) != board->diag_grave_pieces[_grave_index (x1, y1)]) {
341 *error = "The move distance does not match the number of pieces in that diagonal";
345 if (abs (dx) != board->diag_acute_pieces[_acute_index (x1, y1)]) {
346 *error = "The move distance does not match the number of pieces in that diagonal";
352 /* Finally, we have to ensure that no opponent pieces are being
354 step_x = dx ? ((dx < 0) ? -1 : +1) : 0;
355 step_y = dy ? ((dy < 0) ? -1 : +1) : 0;
356 for (x = x1 + step_x, y = y1 + step_y;
358 x += step_x, y += step_y)
360 if (board->cells[x][y] != LOA_CELL_EMPTY &&
361 board->cells[x][y] != board->cells[x1][y1])
363 *error = "You cannot jump an opponent's piece";
372 loa_board_next_player (loa_board_t *board)
374 if (board->player == LOA_PLAYER_BLACK)
375 board->player = LOA_PLAYER_WHITE;
377 board->player = LOA_PLAYER_BLACK;
380 /* XXX: Should check for a legal move for the current player and
381 * return FALSE in that case, (that is, it should be illegal to pass
382 * if there's a legal move available). */
384 loa_board_pass (loa_board_t *board)
386 loa_board_next_player (board);
391 /* Once the move is validated and executed, append it to the moves
392 * array that stores the move history. */
394 loa_board_add_move_to_history (loa_board_t *board,
395 const loa_move_t *move)
399 if (board->num_moves > board->moves_size) {
400 if (board->moves_size)
401 board->moves_size *= 2;
403 board->moves_size = 20;
405 board->moves = realloc (board->moves,
406 board->moves_size * sizeof (loa_move_t));
407 if (board->moves == NULL) {
408 fprintf (stderr, "Out of memory.\n");
413 board->moves[board->num_moves - 1] = *move;
417 loa_board_move (loa_board_t *board,
423 if (! loa_board_move_legal (board, move, error))
426 cell = loa_board_remove_piece (board, move->x1, move->y1);
427 assert (cell == board->player);
429 cell = loa_board_remove_piece (board, move->x2, move->y2);
430 if (cell == LOA_CELL_EMPTY) {
431 move->is_capture = FALSE;
433 assert (cell != board->player);
434 move->is_capture = TRUE;
437 loa_board_add_piece (board,
441 loa_board_add_move_to_history (board, move);
443 loa_board_next_player (board);
448 /* A few different ideas for displaying boards:
450 * 8│ │●│●│●│●│●│●│ | 8| |*|*|*|*|*|*| |
451 * 7│○│ │ │ │ │ │ │○| 7|o| | | | | | |o|
452 * 6│○│ │ │ │ │ │ │○| 6|o| | | | | | |o|
453 * 5│○│ │ │ │ │ │ │○| 5|o| | | | | | |o|
454 * 4│○│ │ │ │ │ │ │○| 4|o| | | | | | |o|
455 * 3│○│ │ │ │ │ │ │○| 3|o| | | | | | |o|
456 * 2│○│ │ │ │ │ │ │○| 2|o| | | | | | |o|
457 * 1│ │●│●│●│●│●│●│ | 1| |*|*|*|*|*|*| |
458 * A B C D E F G H A B C D E F G H
460 * ┌───┬───┬───┬───┬───┬───┬───┬───┐ -------------------------------
461 * 8│ │ ● │ ● │ ● │ ● │ ● │ ● │ │ 8| | * | * | * | * | * | * | |
462 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
463 * 7│ ○ │ │ │ │ │ │ │ ○ │ 7| o | | | | | | | o |
464 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
465 * 6│ ○ │ │ │ │ │ │ │ ○ │ 6| o | | | | | | | o |
466 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
467 * 5│ ○ │ │ │ │ │ │ │ ○ │ 5| o | | | | | | | o |
468 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
469 * 4│ ○ │ │ │ │ │ │ │ ○ │ 4| o | | | | | | | o |
470 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
471 * 3│ ○ │ │ │ │ │ │ │ ○ │ 3| o | | | | | | | o |
472 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
473 * 2│ ○ │ │ │ │ │ │ │ ○ │ 2| o | | | | | | | o |
474 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
475 * 1│ │ ● │ ● │ ● │ ● │ ● │ ● │ │ 1| | * | * | * | * | * | * | |
476 * └───┴───┴───┴───┴───┴───┴───┴───┘ -------------------------------
477 * A B C D E F G H A B C D E F G H
480 loa_board_to_string (loa_board_t *board)
483 /* In order of BLACK, WHITE, EMPTY */
484 const char* cell_strings[] = {"●","○"," "};
485 const char board_header[] = "┌───┬───┬───┬───┬───┬───┬───┬───┐";
486 const char row_header[] = "│ ";
487 const char cell_separator[] = " │ ";
488 const char row_footer[] = " │";
489 const char row_separator[] = "├───┼───┼───┼───┼───┼───┼───┼───┤";
490 const char board_footer[] = "└───┴───┴───┴───┴───┴───┴───┴───┘";
491 char *board_string = g_strdup ("");
493 #define APPEND(str) do { \
494 char *_new = g_strconcat (board_string, (str), NULL); \
495 free (board_string); \
496 board_string = _new; \
499 #define APPENDF(format, ...) do { \
500 char *str = g_strdup_printf (format, ## __VA_ARGS__); \
505 APPENDF (" %s\n", board_header);
506 for (y = 0; y < LOA_BOARD_SIZE; y++) {
507 APPENDF ("%d%s", LOA_BOARD_SIZE - y, row_header);
508 for (x = 0; x < LOA_BOARD_SIZE; x++) {
509 APPENDF ("%s", cell_strings[board->cells[x][y]]);
510 if (x != LOA_BOARD_SIZE - 1)
511 APPENDF ("%s", cell_separator);
513 APPENDF ("%s\n", row_footer);
514 if (y != LOA_BOARD_SIZE -1)
515 APPENDF (" %s\n", row_separator);
517 APPENDF (" %s\n", board_footer);
520 for (x = 0; x < LOA_BOARD_SIZE; x++) {
521 APPENDF ("%c", 'A' + x);
522 if (x != LOA_BOARD_SIZE - 1)