Use coordinates with row and column in :
type Place = (Int,Int)
type Places = [Place]
type Board = (Places,Places,Places)
data Player = O | X deriving (Eq,Ord,Show)The components of
Board record the positions occupied by O, occupied by X, and still empty, respectively. On a nonterminal legal board, equal occupied counts mean O moves next; one extra O means X moves next.The type synonym does not enforce the representation invariant: coordinates are in range; each component has no duplicates; the three represented sets form a set partition of the nine positions; and the occupied counts differ as just described. Both players cannot have won. A winning
O board has one extra O, and a winning X board has equal counts. More fundamentally, a legal tic-tac-toe state has a legal alternating history that stops at the first win: satisfying a type alone never licenses continuing an already completed game.The empty occupancy sets leave all nine coordinates available:
empty :: Board
empty = ([],[],[(r,c) | r <- [0..2], c <- [0..2]])This board satisfies the representation invariant and gives
O the next move.Assume the board satisfies the representation invariant. Reject completed boards and occupied or out-of-range coordinates; testing membership in the empty component covers both coordinate failures.
finished :: Board -> Bool
finished (os,xs,es) = won os || won xs || null es
play :: Board -> Place -> Board
play b@(os,xs,es) q
| finished b = error "play: completed game"
| q `notElem` es = error "play: unavailable place"
| length os == length xs = (q:os,xs,rest)
| otherwise = (os,q:xs,rest)
where rest = filter (/=q) esHere
won is defined in part d. Moving one available coordinate into the appropriate occupied component preserves the set partition and the alternating-count rule. Checking completion first preserves the no-moves-after-a-win invariant.Construct each possible winning line, then test whether one is contained in the player's occupancy set:
winningLines :: [Places]
winningLines =
[[(r,c) | c <- [0..2]] | r <- [0..2]] ++
[[(r,c) | r <- [0..2]] | c <- [0..2]] ++
[[(i,i) | i <- [0..2]], [(i,2-i) | i <- [0..2]]]
won :: Places -> Bool
won ps = any (\line -> all (`elem` ps) line) winningLinesThe list comprehension generates three rows, three columns and two diagonals. Each has exactly three coordinates; therefore
all holds precisely when every coordinate of that line is occupied by this player. Taking any over the eight lines proves the win test correct.Record the outcome at the first completed board and otherwise branch over every available move:
data Outcome = Winner Player | Draw deriving (Eq,Ord,Show)
finals :: Board -> [(Board,Outcome)]
finals b@(os,xs,es)
| won os = [(b,Winner O)]
| won xs = [(b,Winner X)]
| null es = [(b,Draw)]
| otherwise = concatMap (\q -> finals (play b q)) esThe recursion terminates because each recursive call decreases the number of empty positions by one. For correctness, induct on that number. A completed board contributes exactly its own outcome. Otherwise every legal continuation has a unique first available move, and the induction hypothesis covers exactly all completions after that move. List concatenation collects these branches without extending completed games. Repeated final positions are allowed here because the computation deliberately explores every legal move sequence.
Different move orders can lead to the same position, and the two occupancy lists also retain irrelevant insertion order. Thus this search tree repeatedly solves the same remaining game. For example, swapping the order of two
O moves while leaving the intervening X moves legal can reach the same occupied sets.Canonicalize each state by sorted occupancy sets, or by two bitboards, and apply memoization or a visited-state set. Expand each canonical position once, stopping at terminal states, and collect terminal positions in a set. There are at most cell assignments, many of which are illegal; this is much smaller than a tree of move permutations. Store positions, not histories, when the requested output is distinct final positions. Board rotations and reflections can reduce work further if handled as an additional equivalence: if the output must retain every oriented board, reconstruct those distinct orientations rather than silently returning one representative per symmetry class.
Articles by others on the same topic
There are currently no matching articles.