Photoshop

Como no se el conocimiento que tiene sobre photoshop te daré dos soluciones que se me ocurren a "botepronto",
Una fácil: Abre la imagen que vayas a utilizar, aplica filtros/textura/azulejos de mosaico. El resultado se asimilará a una imagen fraccionada en piezas (pero no es un puzzle) se podría mejorar.
La otra solución es algo más compleja. Abre la imagen, y mediante la herramienta de selección crea un cuadrado y después un circulo en la mitad de uno de los lados, te quedará una pieza de puzzle, ahora solo tienes que copiar y pegar (ctrl+c/ctrl+v) y tendrás una pieza independiente de la imagen que has abierto, aplícale efectos de relieve (sin pasarse) y ya está, el manejo de la herramienta de selección (añadir y restar selección es imprescindible mayúscula-Alt)para ir creando las piezas. Otro consejo: la utilización de la cuadrícula y las reglas te ayudarán a no perderte, si no quieres eternizarte las piezas que sean grandes.
Existen más formas pero creo que estas están al alcance de cualquier usuario medio del programa.