Энтропия – неплохое начало, но еще стоит посмотреть на средний коэффициент ветвления при работе решателя. Посчитай, сколько кандидатов отсеивается из каждой ячейки на каждом шаге дедукции – это даст тебе конкретную кривую сложности. Добавь штраф за головоломки, требующие возврата, и у тебя получится метрика, которая и основана на данных, и реально полезна. И помни, одна сложная головоломка не так впечатляет, если решателю приходится угадывать, поэтому старайся, чтобы путь решения был детерминированным.