I am implementing a tic tac toe game for n * n
board in Haskell and i need to generate all board configurations that i can get from next move.
I have board defined as follows:
data Cell = E
| X
| O
deriving (Eq,Show)
type Row a = [a]
type Board = Row (Row Cell)
iniBoard :: Int -> Board
iniBoard n = let row = replicate n E in replicate n row
I can determine, whether given board configuration is winning for player x
, so i have
win :: Cell -> Board -> Bool
win E _ = False
win x brd = any full $ diags brd ++ rows brd ++ cols brd
where
diags brd = mainDiag : [secondDiag]
mainDiag = zipWith (!!) brd [0..]
secondDiag = zipWith (!!) revBrd [0..]
revBrd = do
xs <- brd
return (reverse xs)
rows = id
cols = transpose
full xs = all (==x) xs
But i have no idea, how to generate all board configurations that player x
can make as next move.
I understand, that i need to traverse all cells and check, if cell is empty, then i can place mark here and return new configuration. If i have already winning configuration, then there is no next move, and i must return empty list
I have a code like this:
nxt :: Cell -> Board -> [Board]
nxt x brd = do
if (win x brd || win (switch x) brd)
then
[]
else
undefined
How can i do it, using list monad? Thanks for help!