module Puzzle
  ( goalState
  , goalPositions
  , isValidState
  ) where

import Control.Arrow
import Data.List

import Data.Map.Strict(Map)
import qualified Data.Map.Strict as Map

goalState::[[Int]]
goalState = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]

goalPositions::Map Int (Int, Int)
goalPositions = (Map.fromList . (makeKeyValue <$>)) [0..8]
  where makeKeyValue 0 = (0, (2, 2))
        makeKeyValue n = (n, (`quot` 3) &&& (`rem` 3) $ pred n)

-- | Checks if a given board position is a solvable 8-Puzzle state.
isValidState::[[Int]] -> Bool
isValidState state = length flatState == 9 && hasAllNums && hasEvenInversions
  where flatState = concat state
        hasAllNums = all (`elem` flatState) [0..(length flatState - 1)]
        squares = filter (/= 0) flatState
        hasEvenInversions =
          even $ length [x' | (x:xs) <- tails squares, x' <- xs, x > x']
