My DS, at 1 yr., had a 4 & 6 piece cube puzzle and the design was somewhat disjointed, so he seemed mildly frustrated at times. To my surprise, my DH brought home a 48-piece puzzle on DS's 2nd b-day, and DS became obsessed. I laugh now thinking how I seriously underestimated DS's readiness for more. Melissa & Doug have some very large floor puzzle pieces that are easier for small hands to manipulate.

http://www.amazon.com/Melissa-Doug-...1&keywords=melissa+and+doug+space+puzzle

Although not the puzzle you requested, Wedgits seem to hold the interest of children over a wide age range.
http://www.amazon.com/WEDGiTS-Delux...8&qid=1424388005&sr=8-1&keywords=wedgits