Lines
79.01 %
Functions
44.67 %
Branches
100 %
// This file is part of hnefatafl-copenhagen.
//
// hnefatafl-copenhagen is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
// hnefatafl-copenhagen is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU Affero General Public License for more details.
// You should have received a copy of the GNU Affero General Public License
// along with this program. If not, see <https://www.gnu.org/licenses/>.
// SPDX-License-Identifier: AGPL-3.0-or-later
// SPDX-FileCopyrightText: 2025 David Campbell <david@hnefatafl.org>
use std::{collections::HashMap, fmt, str::FromStr};
use rustc_hash::{FxBuildHasher, FxHashSet};
use serde::{Deserialize, Serialize};
use thiserror::Error;
use crate::{
characters::Characters,
game::PreviousBoards,
play::{BOARD_LETTERS, EXIT_SQUARES_11X11, EXIT_SQUARES_13X13, Plae, Play, Vertex},
role::Role,
space::Space,
status::Status,
};
pub const STARTING_POSITION_11X11: [&str; 11] = [
"...XXXXX...",
".....X.....",
"...........",
"X....O....X",
"X...OOO...X",
"XX.OOKOO.XX",
];
pub const STARTING_POSITION_13X13: [&str; 13] = [
"...XXXXXXX...",
"......X......",
".............",
"X.....O.....X",
"X....OOO....X",
"XX.OOOKOOO.XX",
#[derive(Clone, Deserialize, Eq, Hash, PartialEq, Serialize)]
pub struct Board {
pub spaces: Vec<Space>,
#[serde(skip)]
pub display_ascii: bool,
}
impl Default for Board {
fn default() -> Self {
board_11x11()
impl fmt::Debug for Board {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let board_size: usize = self.size().into();
writeln!(f)?;
for y in 0..board_size {
write!(f, r#"""#)?;
for x in 0..board_size {
match self.spaces[(y * board_size) + x] {
Space::Attacker => write!(f, "X")?,
Space::Empty => write!(f, ".")?,
Space::King => write!(f, "K")?,
Space::Defender => write!(f, "O")?,
writeln!(f, r#"""#)?;
Ok(())
impl fmt::Display for Board {
let mut letters = " ".repeat(3).clone();
letters.push_str(&BOARD_LETTERS[..board_size]);
let bar = "─".repeat(board_size);
writeln!(f, "\n{letters}\n ┌{bar}┐")?;
let y_label = board_size - y;
write!(f, "{y_label:2}│",)?;
if (((y, x) == (0, 0)
|| (y, x) == (10, 0)
|| (y, x) == (0, 10)
|| (y, x) == (10, 10)
|| (y, x) == (5, 5))
&& self.spaces[y * board_size + x] == Space::Empty
&& board_size == 11)
|| (((y, x) == (0, 0)
|| (y, x) == (12, 0)
|| (y, x) == (0, 12)
|| (y, x) == (12, 12)
|| (y, x) == (6, 6))
&& board_size == 13)
{
if self.display_ascii {
write!(f, "#")?;
} else {
write!(f, "⌘")?;
} else if self.display_ascii {
write!(f, "{}", self.spaces[y * board_size + x].display_ascii())?;
write!(f, "{}", self.spaces[y * board_size + x])?;
writeln!(f, "│{y_label:2}")?;
write!(f, " └{bar}┘\n{letters}")
impl TryFrom<[&str; 11]> for Board {
type Error = anyhow::Error;
fn try_from(value: [&str; 11]) -> anyhow::Result<Self> {
let mut spaces = Vec::with_capacity(11 * 11);
let mut kings = 0;
for (y, row) in value.iter().enumerate() {
for (x, ch) in row.chars().enumerate() {
let space = ch.try_into()?;
match space {
Space::Attacker | Space::Defender => {
let vertex = Vertex {
size: BoardSize::_11,
x,
y,
if vertex.on_restricted_square() {
return Err(anyhow::Error::msg(
"Only the king is allowed on restricted squares!",
));
Space::Empty => {}
Space::King => {
kings += 1;
if kings > 1 {
return Err(anyhow::Error::msg("You can only have one king!"));
spaces.push(space);
Ok(Self {
spaces,
display_ascii: false,
})
impl TryFrom<[&str; 13]> for Board {
fn try_from(value: [&str; 13]) -> anyhow::Result<Self> {
let mut spaces = Vec::with_capacity(13 * 13);
size: BoardSize::_13,
impl Board {
#[must_use]
pub fn new(board_size: BoardSize) -> Self {
match board_size {
BoardSize::_11 => board_11x11(),
BoardSize::_13 => board_13x13(),
fn able_to_move(&self, play_from: &Vertex) -> bool {
if let Some(vertex) = play_from.up()
&& self.get(&vertex) == Space::Empty
return true;
if let Some(vertex) = play_from.left()
if let Some(vertex) = play_from.down()
if let Some(vertex) = play_from.right()
false
pub fn a_legal_move_exists(
&self,
status: &Status,
turn: &Role,
previous_boards: &PreviousBoards,
) -> bool {
let size = self.size();
let board_size_usize: usize = size.into();
for y in 0..board_size_usize {
for x in 0..board_size_usize {
let vertex_from = Vertex { size, x, y };
if Role::from(self.get(&vertex_from)) != *turn {
continue;
let vertex_to = Vertex { size, x, y };
if vertex_to.x != vertex_from.x && vertex_to.y != vertex_from.y {
let play = Play {
role: *turn,
from: vertex_from,
to: vertex_to,
if let Ok(_board) = self.legal_move(&play, status, turn, previous_boards) {
pub fn captured(&self) -> Captured {
let mut attacker = 0;
let mut defender = 0;
let mut king = true;
for space in &self.spaces {
Space::Attacker => attacker += 1,
Space::King => king = false,
Space::Defender => defender += 1,
match self.size() {
BoardSize::_11 => {
attacker = 24 - attacker;
defender = 12 - defender;
BoardSize::_13 => {
attacker = 32 - attacker;
defender = 16 - defender;
Captured {
attacker,
defender,
king,
fn captures(&mut self, play_to: &Vertex, role_from: Role, captures: &mut Vec<Vertex>) {
self.captures_(play_to, role_from, captures, super::play::Vertex::up);
self.captures_(play_to, role_from, captures, super::play::Vertex::left);
self.captures_(play_to, role_from, captures, super::play::Vertex::down);
self.captures_(play_to, role_from, captures, super::play::Vertex::right);
fn captures_<T: Fn(&Vertex) -> Option<Vertex>>(
&mut self,
play_to: &Vertex,
role_from: Role,
captures: &mut Vec<Vertex>,
over: T,
) {
if let Some(right_1) = over(play_to) {
let space = self.get(&right_1);
if space != Space::King
&& Role::from(space) == role_from.opposite()
&& let Some(right_2) = over(&right_1)
&& ((right_2.on_restricted_square() && self.get(&right_2) != Space::King)
|| Role::from(self.get(&right_2)) == role_from)
&& self.set_if_not_king(&right_1, Space::Empty)
captures.push(right_1);
// y counts up going down.
#[allow(clippy::too_many_lines)]
fn captures_shield_wall(
vertex_to: &Vertex,
// bottom row
for x_1 in 0..board_size_usize {
let vertex_1 = Vertex {
size,
x: x_1,
y: board_size_usize - 1,
if Role::from(self.get(&vertex_1)) == role_from || vertex_1.on_restricted_square() {
let mut count = 0;
if x_1 == board_size_usize - 1 {
break;
let start = x_1 + 1;
for x_2 in start..board_size_usize {
let vertex_2 = Vertex {
x: x_2,
let vertex_3 = Vertex {
y: board_size_usize - 2,
let role_2 = Role::from(self.get(&vertex_2));
let role_3 = Role::from(self.get(&vertex_3));
if role_2 == role_from.opposite() && role_3 == role_from {
count += 1;
let finish = start + count;
x: finish,
let role = Role::from(self.get(&vertex));
if count > 1
&& (role == role_from || vertex.on_restricted_square())
&& (vertex_to
== &(Vertex {
x: start - 1,
|| vertex_to
}))
for x_2 in start..finish {
if self.set_if_not_king(&vertex, Space::Empty) {
captures.push(vertex);
// top row
let vertex_1 = Vertex { size, x: x_1, y: 0 };
let vertex_2 = Vertex { size, x: x_2, y: 0 };
let vertex_3 = Vertex { size, x: x_2, y: 1 };
y: 0,
let vertex = Vertex { size, x: x_2, y: 0 };
// left row
for y_1 in 0..board_size_usize {
let vertex_1 = Vertex { size, x: 0, y: y_1 };
if y_1 == board_size_usize - 1 {
let start = y_1 + 1;
for y_2 in start..board_size_usize {
let vertex_2 = Vertex { size, x: 0, y: y_2 };
let vertex_3 = Vertex { size, x: 1, y: y_2 };
x: 0,
y: finish,
y: start - 1,
for y_2 in start..finish {
let vertex = Vertex { size, x: 0, y: y_2 };
// right row
x: board_size_usize - 1,
y: y_1,
y: y_2,
x: board_size_usize - 2,
#[allow(clippy::unwrap_used)]
fn closed_off_exit(&self, exit: Vertex) -> bool {
let hasher = FxBuildHasher;
let mut already_checked =
FxHashSet::with_capacity_and_hasher(board_size_usize * board_size_usize, hasher);
already_checked.insert(exit);
let mut pre_stack = Vec::with_capacity(board_size_usize * board_size_usize);
let up = expand_flood_fill(exit.up(), &mut already_checked, &mut pre_stack);
let left = expand_flood_fill(exit.left(), &mut already_checked, &mut pre_stack);
let down = expand_flood_fill(exit.down(), &mut already_checked, &mut pre_stack);
let right = expand_flood_fill(exit.right(), &mut already_checked, &mut pre_stack);
if up
&& left
&& self.get(&pre_stack[0]) == Space::Attacker
&& self.get(&pre_stack[1]) == Space::Attacker
&& self.get(&pre_stack[0].up().unwrap()) == Space::Attacker
&& self.get(&pre_stack[1].left().unwrap()) == Space::Attacker
&& right
&& self.get(&pre_stack[1].right().unwrap()) == Space::Attacker
if left
&& down
&& self.get(&pre_stack[0].left().unwrap()) == Space::Attacker
&& self.get(&pre_stack[1].down().unwrap()) == Space::Attacker
if down
&& self.get(&pre_stack[0].down().unwrap()) == Space::Attacker
let mut stack = Vec::with_capacity(board_size_usize * board_size_usize);
for vertex in pre_stack {
let space = self.get(&vertex);
if space == Space::Empty || space == Space::Attacker {
let _ = expand_flood_fill(vertex.up(), &mut already_checked, &mut stack);
let _ = expand_flood_fill(vertex.left(), &mut already_checked, &mut stack);
let _ = expand_flood_fill(vertex.down(), &mut already_checked, &mut stack);
let _ = expand_flood_fill(vertex.right(), &mut already_checked, &mut stack);
while !stack.is_empty() {
if let Some(vertex) = stack.pop() {
if space == Space::Empty {
} else if Into::<Role>::into(space) == Role::Defender {
return false;
true
pub fn closed_off_exits(&self) -> u8 {
let mut closed_off_exits = 0;
for exit in self.exit_squares() {
if self.closed_off_exit(exit) {
closed_off_exits += 1;
closed_off_exits
pub fn difference(&self, other: &Board) -> Option<Plae> {
let size_usize = size.into();
let mut role = None;
let mut from = None;
let mut to = None;
for y in 0..size_usize {
for x in 0..size_usize {
let vertex = Vertex { size, x, y };
let a = self.get(&vertex);
let b = other.get(&vertex);
if a != b {
if a == Space::Empty {
to = Some(vertex);
role = Some(b.into());
if b == Space::Empty {
from = Some(vertex);
if let (Some(role), Some(from), Some(to)) = (role, from, to) {
Some(Plae::Play(Play { role, from, to }))
None
pub fn exit_squares(&self) -> Vec<Vertex> {
BoardSize::_11 => EXIT_SQUARES_11X11.into(),
BoardSize::_13 => EXIT_SQUARES_13X13.into(),
pub fn find_the_king(&self) -> Option<Vertex> {
let v = Vertex { size, x, y };
if self.get(&v) == Space::King {
return Some(v);
pub fn captured_the_king(&self) -> bool {
if *space == Space::King {
fn capture_the_king(
if let Some(kings_vertex) = self.find_the_king()
&& role_from == Role::Attacker
let mut attacker_moved = false;
let (move_to_capture, surrounded) =
self.capture_the_king_space(play_to, kings_vertex.up());
if !surrounded {
if move_to_capture {
attacker_moved = true;
self.capture_the_king_space(play_to, kings_vertex.left());
self.capture_the_king_space(play_to, kings_vertex.down());
self.capture_the_king_space(play_to, kings_vertex.right());
if attacker_moved {
self.set(&kings_vertex, Space::Empty);
captures.push(kings_vertex);
pub fn capture_the_king_one_move(&self) -> Option<Vertex> {
let mut spaces_left = 4;
let mut capture = None;
if let Some(kings_vertex) = self.find_the_king() {
if let Some(vertex) = kings_vertex.up() {
if vertex.on_throne() || self.get(&vertex) == Space::Attacker {
spaces_left -= 1;
capture = Some(vertex);
if let Some(vertex) = kings_vertex.left() {
if let Some(vertex) = kings_vertex.down() {
if let Some(vertex) = kings_vertex.right() {
if spaces_left == 1 { capture } else { None }
#[inline]
fn capture_the_king_space(&self, play_to: &Vertex, direction: Option<Vertex>) -> (bool, bool) {
if let Some(surround_king) = direction {
let move_to_capture = *play_to == surround_king;
let surrounded = move_to_capture
|| surround_king.on_throne()
|| self.get(&surround_king) == Space::Attacker;
(move_to_capture, surrounded)
(false, false)
fn exit_forts(&self) -> bool {
match self.find_the_king() {
Some(kings_vertex) => {
kings_vertex.touches_wall()
&& self.able_to_move(&kings_vertex)
&& self.flood_fill_defender_wins(&kings_vertex)
None => false,
fn flood_fill_attacker_wins(&self) -> bool {
let mut already_checked = FxHashSet::with_capacity_and_hasher(
board_size_usize * board_size_usize,
hasher,
);
already_checked.insert(kings_vertex);
stack.push(kings_vertex);
if space == Space::Empty || Role::from(space) == Role::Defender {
if !expand_flood_fill(vertex.up(), &mut already_checked, &mut stack) {
if !expand_flood_fill(vertex.left(), &mut already_checked, &mut stack) {
if !expand_flood_fill(vertex.down(), &mut already_checked, &mut stack) {
if !expand_flood_fill(vertex.right(), &mut already_checked, &mut stack)
if Role::from(self.get(&vertex)) == Role::Defender
&& !already_checked.contains(&vertex)
pub fn flood_fill_defender_wins(&self, vertex: &Vertex) -> bool {
let board_size_usize = size.into();
let mut attacker_has_enough_pieces = false;
'outer: for y in 0..board_size_usize {
if Role::from(self.get(&vertex)) == Role::Attacker {
if count > 1 {
attacker_has_enough_pieces = true;
break 'outer;
let mut already_checked = FxHashSet::default();
let mut stack = vec![];
if let Some(vertex) = vertex.up() {
stack.push((vertex, Direction::LeftRight));
if let Some(vertex) = vertex.left() {
stack.push((vertex, Direction::UpDown));
if let Some(vertex) = vertex.down() {
if let Some(vertex) = vertex.right() {
if let Some((vertex, direction)) = stack.pop() {
if let Some(vertex) = vertex.up()
already_checked.insert(vertex);
if let Some(vertex) = vertex.left()
if let Some(vertex) = vertex.down()
if let Some(vertex) = vertex.right()
} else if Role::from(space) == Role::Attacker {
} else if direction == Direction::UpDown {
let mut vertex_1 = false;
let mut vertex_2 = false;
if Role::from(self.get(&vertex)) == Role::Defender {
vertex_1 = true;
vertex_2 = true;
if !vertex_1 && !vertex_2 && attacker_has_enough_pieces {
pub fn get(&self, vertex: &Vertex) -> Space {
self.spaces[vertex.y * board_size + vertex.x]
pub fn get_neighbors(
starts: &Vec<Vertex>,
visited: &HashMap<Vertex, (u8, Option<Vertex>)>,
) -> Vec<Vertex> {
let mut neighbors = Vec::new();
let board_usize = size.into();
for start in starts {
for x in 1..=start.x {
let index = start.x - x;
x: index,
y: start.y,
if self.get(&vertex) != Space::Empty {
if !visited.contains_key(&vertex) {
neighbors.push(vertex);
for x in (start.x + 1)..board_usize {
for y in 1..=start.y {
let index = start.y - y;
x: start.x,
y: index,
for y in (start.y + 1)..board_usize {
neighbors
pub fn size(&self) -> BoardSize {
let len = self.spaces.len();
if len == 11 * 11 {
BoardSize::_11
} else if len == 13 * 13 {
BoardSize::_13
unreachable!()
/// # Errors
///
/// If the move is illegal.
#[allow(
clippy::cast_possible_truncation,
clippy::cast_possible_wrap,
clippy::cast_sign_loss
)]
pub fn legal_move(
play: &Play,
) -> Result<Board, InvalidMove> {
if *status != Status::Ongoing {
return Err(InvalidMove::GameOver);
let space_from = self.get(&play.from);
let role_from = Role::from(space_from);
if role_from == Role::Roleless {
return Err(InvalidMove::Role);
} else if *turn != role_from {
return Err(InvalidMove::Turn);
let x_diff = play.from.x as i32 - play.to.x as i32;
let y_diff = play.from.y as i32 - play.to.y as i32;
if x_diff != 0 && y_diff != 0 {
return Err(InvalidMove::StraightLine);
if x_diff == 0 && y_diff == 0 {
return Err(InvalidMove::Location);
if x_diff != 0 {
let x_diff_sign = x_diff.signum();
for x_diff in 1..=x_diff.abs() {
x: (play.from.x as i32 - (x_diff * x_diff_sign)) as usize,
y: play.from.y,
if space != Space::Empty {
return Err(InvalidMove::Empty);
let y_diff_sign = y_diff.signum();
for y_diff in 1..=y_diff.abs() {
x: play.from.x,
y: (play.from.y as i32 - (y_diff * y_diff_sign)) as usize,
if space_from != Space::King && play.to.on_restricted_square() {
return Err(InvalidMove::Restricted);
let mut board = self.clone();
board.set(&play.from, Space::Empty);
board.set(&play.to, space_from);
if turn == &Role::Defender && previous_boards.0.contains(&board) {
return Err(InvalidMove::RepeatMove);
Ok(board)
fn no_attacker_pieces_left(&self) -> bool {
if Role::from(self.get(&v)) == Role::Attacker {
pub fn play(
play: &Plae,
previous_boards: &mut PreviousBoards,
) -> anyhow::Result<(Vec<Vertex>, Status)> {
let (board, captures, status) = self.play_internal(play, status, turn, previous_boards)?;
previous_boards.0.insert(board.clone());
*self = board;
Ok((captures, status))
pub fn play_internal(
) -> anyhow::Result<(Board, Vec<Vertex>, Status)> {
"play: the game has to be ongoing to play",
let play = match play {
Plae::AttackerResigns => return Ok((self.clone(), Vec::new(), Status::DefenderWins)),
Plae::DefenderResigns => return Ok((self.clone(), Vec::new(), Status::AttackerWins)),
Plae::Play(play) => play,
let mut board = self.legal_move(play, status, turn, previous_boards)?;
let mut captures = Vec::new();
board.captures(&play.to, role_from, &mut captures);
board.captures_shield_wall(role_from, &play.to, &mut captures);
if play.to.on_exit_square() {
return Ok((board, captures, Status::DefenderWins));
if board.capture_the_king(role_from, &play.to, &mut captures) {
return Ok((board, captures, Status::AttackerWins));
if board.exit_forts() {
if board.flood_fill_attacker_wins() {
if board.no_attacker_pieces_left() {
Ok((board, captures, Status::Ongoing))
fn set(&mut self, vertex: &Vertex, space: Space) {
self.spaces[vertex.y * board_size + vertex.x] = space;
fn set_if_not_king(&mut self, vertex: &Vertex, space: Space) -> bool {
if self.get(vertex) == Space::King {
self.set(vertex, space);
pub fn spaces_around_the_king(&self) -> Option<u8> {
let king = self.find_the_king()?;
let Some(up) = king.up() else {
return Some(5);
let Some(left) = king.left() else {
let Some(down) = king.down() else {
let Some(right) = king.right() else {
let mut sum = 4;
for vertex in [up, left, down, right] {
if self.get(&vertex) == Space::Attacker || vertex.on_throne() {
sum -= 1;
Some(sum)
#[derive(
Clone, Copy, Debug, Default, Deserialize, Eq, Hash, Ord, PartialEq, PartialOrd, Serialize,
pub enum BoardSize {
#[default]
_11,
_13,
impl fmt::Display for BoardSize {
match self {
BoardSize::_11 => write!(f, "11"),
BoardSize::_13 => write!(f, "13"),
impl From<BoardSize> for usize {
fn from(size: BoardSize) -> Self {
match size {
BoardSize::_11 => 11,
BoardSize::_13 => 13,
impl FromStr for BoardSize {
type Err = anyhow::Error;
fn from_str(s: &str) -> Result<Self, Self::Err> {
match s {
"11" => Ok(BoardSize::_11),
"13" => Ok(BoardSize::_13),
_ => Err(anyhow::Error::msg(format!("expected 11 or 13, got {s}"))),
impl TryFrom<usize> for BoardSize {
fn try_from(value: usize) -> Result<Self, Self::Error> {
match value {
11 => Ok(BoardSize::_11),
13 => Ok(BoardSize::_13),
_ => Err(anyhow::Error::msg(format!(
"an invalid board size was passed: {value}"
))),
#[allow(clippy::missing_panics_doc)]
fn board_11x11() -> Board {
let spaces: Vec<Space> = STARTING_POSITION_11X11
.iter()
.flat_map(|space| space.chars().map(|ch| ch.try_into().unwrap()))
.collect();
Board {
fn board_13x13() -> Board {
let spaces: Vec<Space> = STARTING_POSITION_13X13
pub struct Captured {
pub attacker: u8,
pub defender: u8,
pub king: bool,
impl Captured {
pub fn attacker(&self, chars: &Characters) -> String {
format!("{} {}", chars.attacker, self.attacker)
pub fn defender(&self, chars: &Characters) -> String {
let mut string = format!("{} {}", chars.defender, self.defender);
if self.king {
string.push(' ');
string.push_str(&chars.king);
string
#[derive(Clone, Debug, Eq, PartialEq)]
enum Direction {
LeftRight,
UpDown,
#[derive(Error, Debug)]
pub enum InvalidMove {
#[error("play: the game is already over")]
GameOver,
#[error("play: you have to play through empty locations")]
Empty,
#[error("play: you have to change location")]
Location,
#[error("play: you already reached that position")]
RepeatMove,
#[error("play: only the king may move to a restricted square")]
Restricted,
#[error("play: you didn't select a role")]
Role,
#[error("play: you can only play in a straight line")]
StraightLine,
#[error("play: it isn't your turn")]
Turn,
fn expand_flood_fill(
vertex: Option<Vertex>,
already_checked: &mut FxHashSet<Vertex>,
stack: &mut Vec<Vertex>,
if let Some(vertex) = vertex {
if !already_checked.contains(&vertex) {
stack.push(vertex);