Чем отличается головоломка от обычной сложной задачи?

Не совсем так: к головоломкам относятся не только всякие да-нетки и всякие загадки, но и известные по школе пятнашки, кубик Рубика, японские головоломки и иные задачи, для решения которых люди используют отработанные (в большинстве случаев пусть и личным опытом) алгоритмы решения.
Обратные примеры: задачи программирования нейронных сетей, олимпиадные задачи по математике. Не являются головоломками, но готовых алгоритмов для решения у участников нет, если организаторы олимпиады правильно подошли к организации.
То есть, требование к креативности - ещё не показатель, что перед Вами головоломка.