Speeding up naive backtracking Sudoku Solver in Haskell
It turns out I made some crucial mistakes: The iteration in solve can stop as soon we have tried all possibilities for one coordinate (x,y) that is not set yet. If we iterate further over (x,y) we get duplicate solutions which makes things blow up, so with following little modification we get results immediately:

isEmpty :: Board -&gt; Coordinates -&gt; Bool
isEmpty b coords = b ! coords == 0

-- check whether board is already full
full :: Board -&gt; Bool
full b = 0 `notElem` [b ! (i,j) | i&lt;-[0..8], j&lt;-[0..8]]

-- recursion to find all solutions to a given board
solve :: Board -&gt; [Board]
solve b
 |full b = [b]
 |otherwise =  concat[ solve $! (insert b (x, y) n)|
                       (x,y) &lt;- take 1 empty,
                       n &lt;- [1..9],
                       possible b (x,y) n]
   where empty = [(x,y) | x&lt;-[0..8],y&lt;-[0..8], isEmpty b (x, y)]


Try it online!