Also known as Noughts and Crosses.
A Rust program to generate all terminal positions of the game of Tic-Tac-Toe. Rotations, transpositions, games-still-in-progress and impossible board states are not shown.
github.com/bakert/boards
use std::collections::HashMap;
const EMPTY: char = ' ';
const X: char = 'X';
const O: char = 'O';
type Boards = HashMap;
type Board = [[char; 3]; 3];
type Representations = [String; 8];
trait BoardMethods {
fn display(&self) -> String;
fn is_terminal(&self) -> bool;
fn representation(&self) -> String;
fn all_representations(&self) -> Representations;
fn rotate(&self) -> Board;
fn transpose(&self) -> Board;
}
trait BoardsMethods {
fn contains(&self, b: Board) -> bool;
fn insert_board(&mut self, b: Board);
}
fn main() {
test();
let empty_board: Board = [[EMPTY; 3]; 3];
let mut final_boards: Boards = HashMap::new();
let boards: Vec = all_boards(empty_board, X);
for board in boards {
if board.is_terminal() && !final_boards.contains(board) {
final_boards.insert_board(board);
}
}
println!("{} unique terminal boards found\n", final_boards.len());
for (_, board) in final_boards {
println!("{}", board.display());
}
}
fn all_boards(board: Board, to_play: char) -> Vec {
let to_play_next: char = if to_play == X { O } else { X };
let mut boards: Vec = Vec::new();
for x in 0..board.len() {
let row = board[x];
for y in 0..row.len() {
if board[x][y] == EMPTY {
let mut b: Board = board.clone();
b[x][y] = to_play;
boards.push(b);
if !b.is_terminal() {
boards.append(&mut all_boards(b, to_play_next));
}
}
}
}
return boards;
}
impl BoardMethods for Board {
fn display(&self) -> String {
let mut s = String::new();
for row in self {
for square in row {
s.push('|');
s.push(*square);
}
s.push_str("|\n");
}
return s;
}
fn is_terminal(&self) -> bool {
for i in 0..3 {
if self[i][0] != EMPTY && self[i][0] == self[i][1] && self[i][1] == self[i][2] {
return true;
}
if self[0][i] != EMPTY && self[0][i] == self[1][i] && self[1][i] == self[2][i] {
return true;
}
}
if self[0][0] != EMPTY && self[0][0] == self[1][1] && self[1][1] == self[2][2] {
return true;
}
if self[0][2] != EMPTY && self[0][2] == self[1][1] && self[1][1] == self[2][0] {
return true;
}
for row in self {
for square in row {
if *square == EMPTY {
return false;
}
}
}
return true;
}
fn all_representations(&self) -> Representations {
let mut r: Representations = Default::default();
r[0] = self.representation();
r[1] = self.rotate().representation();
r[2] = self.rotate().rotate().representation();
r[3] = self.rotate().rotate().rotate().representation();
r[4] = self.transpose().representation();
r[5] = self.rotate().transpose().representation();
r[6] = self.rotate().rotate().transpose().representation();
r[7] = self.rotate().rotate().rotate().transpose().representation();
return r;
}
fn representation(&self) -> String {
let mut s = String::new();
for row in self {
for square in row {
s.push(*square);
}
}
return s;
}
fn rotate(&self) -> Board {
let mut b: Board = [[EMPTY, EMPTY, EMPTY]; 3];
for x in 0..self.len() {
let row = self[x];
for y in 0..row.len() {
b[x][y] = self[row.len() - y - 1][x];
}
}
return b
}
fn transpose(&self) -> Board {
let mut b: Board = [[EMPTY, EMPTY, EMPTY]; 3];
for x in 0..self.len() {
let row = self[x];
for y in 0..row.len() {
b[y][x] = self[x][y];
}
}
return b;
}
}
impl BoardsMethods for Boards {
fn contains(&self, board: Board) -> bool {
for repr in board.all_representations() {
if self.contains_key(&repr) {
return true;
}
}
return false;
}
fn insert_board(&mut self, b: Board) {
self.insert(b.representation(), b);
}
}
fn test() {
test_rotate();
test_transpose();
}
fn test_rotate() {
// XXX _OX
// OOO => _OX
// ___ _OX
let b: Board = [[X, X, X], [O, O, O], [EMPTY, EMPTY, EMPTY]];
let rotated: Board = b.rotate();
assert!(rotated[0] == [EMPTY, O, X]);
assert!(rotated[1] == [EMPTY, O, X]);
assert!(rotated[2] == [EMPTY, O, X]);
}
fn test_transpose() {
// X_O XO_
// OX_ => _X_
// __X O_X
let b: Board = [[X, EMPTY, O], [O, X, EMPTY], [EMPTY, EMPTY, X]];
let transposed: Board = b.transpose();
assert!(transposed == [[X, O, EMPTY], [EMPTY, X, EMPTY], [O, EMPTY, X]]);
}
