Puzzle game solver via Backtracking
isFull fires when assembleBoards returns an empty list; we'd expect to be able to ask that question only once. newBoards and validBoards do not deserve names - if you want the reader to be able to tell what the value means, comments are more appropriate.

Most of the rest of backtrack is about descending into a nested data structure and changing a small part, which lens specializes in: traverse . traverse . filtered (==E) descends into the board, then each of its elements, then each of their E cells. holesOf gives you, roughly speaking, the positions of the targets in the original board - it separates the board into a Cell and a Cell -&gt; Board for each target. peek lets you forget there was an E.

import Control.Comonad.Representable.Store (peek)
import Control.Lens (holesOf, filtered)

backtrack :: Board -&gt; [Board]
backtrack b = case setFirstE b of
  -- board has no more empty cells
  Nothing -&gt; [b]
  -- we only need to place X and O in the first occurence of E, because one of them MUST be correct
  Just setter -&gt; nub $ concatMap backtrack $ filter isValid $ map setter [X,O]

-- Punches the first E out of the board, if any.
setFirstE :: Board -&gt; Maybe (Cell -&gt; Board)
setFirstE = listToMaybe . map (flip peek) . holesOf (traverse . traverse . filtered (==E))