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>
26 #include "loa-board.h"
28 /* Given an (x,y) position on the board, return the index of the array
29 * used to count pieces in diagonal rows running from upper-left to
30 * lower-right, (like a grave accent: à or like a backslash: \).
32 * This is the array to look into when a move occurs with dx and dy of
35 _grave_index (int x, int y)
37 return x - y + LOA_BOARD_SIZE - 1;
40 /* Given an (x,y) position on the board, return the index of the array
41 * used to count pieces in diagonal rows running from lower-left to
42 * upper-right, (like an acute accent: á or like a forward slash: /).
44 * This is the array to look into when a move occurs with dx and dy of
45 * opposite sign, (one positive, one negative). */
47 _acute_index (int x, int y)
53 loa_board_add_piece (loa_board_t *board, int x, int y, loa_cell_t cell)
55 assert (cell == LOA_CELL_BLACK || cell == LOA_CELL_WHITE);
56 assert (board->cells[x][y] == LOA_CELL_EMPTY);
58 board->col_pieces[x]++;
59 board->row_pieces[y]++;
60 board->diag_grave_pieces[_grave_index (x, y)]++;
61 board->diag_acute_pieces[_acute_index (x, y)]++;
63 board->num_pieces[cell]++;
65 board->cells[x][y] = cell;
69 loa_board_remove_piece (loa_board_t *board, int x, int y)
73 cell = board->cells[x][y];
75 if (cell == LOA_CELL_EMPTY)
76 return LOA_CELL_EMPTY;
78 board->col_pieces[x]--;
79 board->row_pieces[y]--;
80 board->diag_grave_pieces[_grave_index (x, y)]--;
81 board->diag_acute_pieces[_acute_index (x, y)]--;
83 board->num_pieces[cell]--;
85 board->cells[x][y] = LOA_CELL_EMPTY;
91 loa_board_init (loa_board_t *board)
95 for (x = 0; x < LOA_BOARD_SIZE; x++)
96 for (y = 0; y < LOA_BOARD_SIZE; y++)
97 board->cells[x][y] = LOA_CELL_EMPTY;
99 board->num_pieces[LOA_CELL_BLACK] = 0;
100 board->num_pieces[LOA_CELL_WHITE] = 0;
102 for (i = 0; i < LOA_BOARD_SIZE; i++) {
103 board->row_pieces[i] = 0;
104 board->col_pieces[i] = 0;
107 for (i = 0; i < LOA_DIAG_ARRAY_SIZE; i++) {
108 board->diag_grave_pieces[i] = 0;
109 board->diag_acute_pieces[i] = 0;
112 for (i = 1; i < LOA_BOARD_SIZE - 1; i++) {
113 loa_board_add_piece (board, i, 0, LOA_CELL_BLACK);
114 loa_board_add_piece (board, i, LOA_BOARD_SIZE - 1, LOA_CELL_BLACK);
115 loa_board_add_piece (board, 0, i, LOA_CELL_WHITE);
116 loa_board_add_piece (board, LOA_BOARD_SIZE - 1, i, LOA_CELL_WHITE);
119 board->player = LOA_PLAYER_BLACK;
123 loa_board_group_size_recursive (loa_board_t *board, int x, int y,
132 if (x >= LOA_BOARD_SIZE || y >= LOA_BOARD_SIZE)
135 bit = 1ll << (x * LOA_BOARD_SIZE + y);
141 if (board->cells[x][y] != cell)
145 loa_board_group_size_recursive (board, x-1, y-1, cell, visited) +
146 loa_board_group_size_recursive (board, x-1, y , cell, visited) +
147 loa_board_group_size_recursive (board, x-1, y+1, cell, visited) +
148 loa_board_group_size_recursive (board, x , y-1, cell, visited) +
149 loa_board_group_size_recursive (board, x , y , cell, visited) +
150 loa_board_group_size_recursive (board, x , y+1, cell, visited) +
151 loa_board_group_size_recursive (board, x+1, y-1, cell, visited) +
152 loa_board_group_size_recursive (board, x+1, y , cell, visited) +
153 loa_board_group_size_recursive (board, x+1, y+1, cell, visited);
157 loa_board_group_size (loa_board_t *board, int x, int y)
159 uint64_t visited = 0ll;
160 loa_cell_t cell = board->cells[x][y];
162 return loa_board_group_size_recursive (board, x, y, cell, &visited);
166 loa_board_is_won (loa_board_t *board, int x, int y)
168 loa_cell_t cell = board->cells[x][y];
170 if (cell == LOA_CELL_EMPTY)
173 if (loa_board_group_size (board, x, y) == board->num_pieces[cell])
180 loa_board_move_legal (loa_board_t *board,
189 if (x1 < 0 || y1 < 0 || x1 >= LOA_BOARD_SIZE || y1 >= LOA_BOARD_SIZE ||
190 x2 < 0 || y2 < 0 || x2 >= LOA_BOARD_SIZE || y2 >= LOA_BOARD_SIZE)
192 *error = "Invalid coordinates (not on board)";
197 if (board->cells[x1][y1] == LOA_CELL_EMPTY) {
198 *error = "There is no piece there to move";
202 if (board->cells[x1][y1] != board->player) {
203 *error = "You cannot move your opponent's piece";
207 if (board->cells[x2][y2] == board->cells[x1][y1]) {
208 *error = "You cannot capture your own piece";
215 /* Here's the meat of Lines of Action legaility: Does the distance
216 * moved exactly match the number of pieces (of either color) in
217 * the row, column, or diagonal of the movement. */
220 if (abs (dy) != board->col_pieces[x1]) {
221 *error = "The move distance does not match the number of pieces in that column";
224 } else if (dy == 0) {
226 if (abs (dx) != board->row_pieces[y1]) {
227 *error = "The move distance does not match the number of pieces in that row";
231 if (abs (dx) != abs (dy)) {
232 *error = "That move is not in a row, column, or diagonal";
236 if ((dx > 0) == (dy > 0)) {
237 if (abs (dx) != board->diag_grave_pieces[_grave_index (x1, y1)]) {
238 *error = "The move distance does not match the number of pieces in that diagonal";
242 if (abs (dx) != board->diag_acute_pieces[_acute_index (x1, y1)]) {
243 *error = "The move distance does not match the number of pieces in that diagonal";
249 /* Finally, we have to ensure that no opponent pieces are being
251 step_x = dx ? ((dx < 0) ? -1 : +1) : 0;
252 step_y = dy ? ((dy < 0) ? -1 : +1) : 0;
253 for (x = x1 + step_x, y = y1 + step_y;
255 x += step_x, y += step_y)
257 if (board->cells[x][y] != LOA_CELL_EMPTY &&
258 board->cells[x][y] != board->cells[x1][y1])
260 *error = "You cannot jump an opponent's piece";
269 loa_board_next_player (loa_board_t *board)
271 if (board->player == LOA_PLAYER_BLACK)
272 board->player = LOA_PLAYER_WHITE;
274 board->player = LOA_PLAYER_BLACK;
277 /* XXX: Should check for a legal move for the current player and
278 * return FALSE in that case, (that is, it should be illegal to pass
279 * if there's a legal move available). */
281 loa_board_pass (loa_board_t *board)
283 loa_board_next_player (board);
289 loa_board_move (loa_board_t *board,
296 if (! loa_board_move_legal (board, x1, y1, x2, y2, error))
299 cell = loa_board_remove_piece (board, x1, y1);
300 loa_board_remove_piece (board, x2, y2);
301 loa_board_add_piece (board, x2, y2, cell);
303 loa_board_next_player (board);
308 /* A few different ideas for displaying boards:
310 * 8│ │●│●│●│●│●│●│ | 8| |*|*|*|*|*|*| |
311 * 7│○│ │ │ │ │ │ │○| 7|o| | | | | | |o|
312 * 6│○│ │ │ │ │ │ │○| 6|o| | | | | | |o|
313 * 5│○│ │ │ │ │ │ │○| 5|o| | | | | | |o|
314 * 4│○│ │ │ │ │ │ │○| 4|o| | | | | | |o|
315 * 3│○│ │ │ │ │ │ │○| 3|o| | | | | | |o|
316 * 2│○│ │ │ │ │ │ │○| 2|o| | | | | | |o|
317 * 1│ │●│●│●│●│●│●│ | 1| |*|*|*|*|*|*| |
318 * A B C D E F G H A B C D E F G H
320 * ┌───┬───┬───┬───┬───┬───┬───┬───┐ -------------------------------
321 * 8│ │ ● │ ● │ ● │ ● │ ● │ ● │ │ 8| | * | * | * | * | * | * | |
322 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
323 * 7│ ○ │ │ │ │ │ │ │ ○ │ 7| o | | | | | | | o |
324 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
325 * 6│ ○ │ │ │ │ │ │ │ ○ │ 6| o | | | | | | | o |
326 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
327 * 5│ ○ │ │ │ │ │ │ │ ○ │ 5| o | | | | | | | o |
328 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
329 * 4│ ○ │ │ │ │ │ │ │ ○ │ 4| o | | | | | | | o |
330 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
331 * 3│ ○ │ │ │ │ │ │ │ ○ │ 3| o | | | | | | | o |
332 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
333 * 2│ ○ │ │ │ │ │ │ │ ○ │ 2| o | | | | | | | o |
334 * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---|
335 * 1│ │ ● │ ● │ ● │ ● │ ● │ ● │ │ 1| | * | * | * | * | * | * | |
336 * └───┴───┴───┴───┴───┴───┴───┴───┘ -------------------------------
337 * A B C D E F G H A B C D E F G H
340 loa_board_to_string (loa_board_t *board)
343 /* In order of BLACK, WHITE, EMPTY */
344 const char* cell_strings[] = {"●","○"," "};
345 const char board_header[] = "┌───┬───┬───┬───┬───┬───┬───┬───┐";
346 const char row_header[] = "│ ";
347 const char cell_separator[] = " │ ";
348 const char row_footer[] = " │";
349 const char row_separator[] = "├───┼───┼───┼───┼───┼───┼───┼───┤";
350 const char board_footer[] = "└───┴───┴───┴───┴───┴───┴───┴───┘";
351 char *board_string = g_strdup ("");
353 #define APPEND(str) do { \
354 char *_new = g_strconcat (board_string, (str), NULL); \
355 free (board_string); \
356 board_string = _new; \
359 #define APPENDF(format, ...) do { \
360 char *str = g_strdup_printf (format, ## __VA_ARGS__); \
365 APPENDF (" %s\n", board_header);
366 for (y = 0; y < LOA_BOARD_SIZE; y++) {
367 APPENDF ("%d%s", LOA_BOARD_SIZE - y, row_header);
368 for (x = 0; x < LOA_BOARD_SIZE; x++) {
369 APPENDF ("%s", cell_strings[board->cells[x][y]]);
370 if (x != LOA_BOARD_SIZE - 1)
371 APPENDF ("%s", cell_separator);
373 APPENDF ("%s\n", row_footer);
374 if (y != LOA_BOARD_SIZE -1)
375 APPENDF (" %s\n", row_separator);
377 APPENDF (" %s\n", board_footer);
380 for (x = 0; x < LOA_BOARD_SIZE; x++) {
381 APPENDF ("%c", 'A' + x);
382 if (x != LOA_BOARD_SIZE - 1)