import Data.List (nub)

data Move
  = Maxi Int
  | Mini Int

instance Show Move where
    show (Mini n) = "Mini " ++ (show n)
    show (Maxi n) = "Maxi " ++ (show n)

instance Eq Move where
  (==) (Mini n1) (Mini n2) = (n1 == n2)
  (==) (Maxi n1) (Maxi n2) = (n1 == n2)
  (==) _a _b = False
  (/=) (Maxi n1) (Mini n2) = (n1 /= n2)
  (/=) (Mini n1) (Maxi n2) = (n1 /= n2)
  (/=) _a _b = False

nextConfigs :: [Move] -> [[Move]]
nextConfigs [] = fmap (\y -> [(Maxi y)]) ([1 .. 9] :: [Int])
nextConfigs moves =
  case (last moves) of
    (Maxi n) -> [moves ++ [(Mini n)] | n <- [1 .. 9], (Mini n) `notElem` moves]
    (Mini n) -> [moves ++ [(Maxi n)] | n <- [1 .. 9], (Maxi n) `notElem` moves]

winsMaxi :: [Move] -> Bool
winsMaxi moves =
  (all id [((Maxi x) `elem` moves) | x <- [1 .. 3]]) ||
  (all id [((Maxi x) `elem` moves) | x <- [4 .. 6]]) ||
  (all id [((Maxi x) `elem` moves) | x <- [7 .. 9]]) ||
  (all id [((Maxi x) `elem` moves) | x <- [1, 4, 7]]) ||
  (all id [((Maxi x) `elem` moves) | x <- [2, 5, 8]]) ||
  (all id [((Maxi x) `elem` moves) | x <- [3, 6, 9]])

winsMini :: [Move] -> Bool
winsMini moves =
  (all id [((Mini x) `elem` moves) | x <- [1 .. 3]]) ||
  (all id [((Mini x) `elem` moves) | x <- [4 .. 6]]) ||
  (all id [((Mini x) `elem` moves) | x <- [7 .. 9]]) ||
  (all id [((Mini x) `elem` moves) | x <- [1, 4, 7]]) ||
  (all id [((Mini x) `elem` moves) | x <- [2, 5, 8]]) ||
  (all id [((Mini x) `elem` moves) | x <- [3, 6, 9]])

isTerminal :: [Move] -> Bool
isTerminal moves = winsMaxi moves || winsMini moves || isDraw moves

isDraw :: [Move] -> Bool
isDraw moves = length moves == 9 && not (winsMaxi moves) && not (winsMini moves)

main :: IO ()
main = do
  print $ show $ nextConfigs [(Maxi 1), (Mini 5)]