SAT очень важен, потому что это NP-Complete. Чтобы понять, что это значит, вам необходимо четкое представление о классах сложности. Вот краткое изложение:
P - это класс всех задач, которые могут быть решены за полиномиальное время (т.е. быстро).
NP - класс всех задач, решение которых можно проверить за полиномиальное время. Это означает, что очень быстро найти конкретное решение очень быстро, но найти его обычно медленно (чаще всего экспоненциальное время). Если, конечно, проблема не в P-части NP (как указано ниже, P является частью NP, как вы можете легко проверить).
Тогда есть множество задач NP-Complete. Этот набор содержит все проблемы, которые являются настолько общими, что вы можете решить эти проблемы вместо одной из NP (это называется сведение проблемы к другой). Это означает, что вы можете преобразовать задачу из одного домена в другую задачу NP-Complete, получить ответ и преобразовать ответ обратно.
Однако часто можно доказать, что задача является NP-полной, но преобразования неясны для другой данной проблемы.
SAT так хорош, потому что он NP-Complete, то есть вы можете решить его вместо любой другой проблемы в NP, а также сокращение не так сложно сделать. TSP - еще одна проблема NP-Complete, но преобразования чаще всего гораздо сложнее.
Так что, да, SAT может использоваться для всех упомянутых вами проблем. Часто, однако, это неосуществимо. Где это возможно, когда не известен другой быстрый алгоритм, такой как упомянутая вами головоломка. В этом случае вам не нужно разрабатывать алгоритм для головоломки, но вы можете использовать любой из высоко оптимизированных SAT-Solvers, и в итоге вы получите разумный быстрый алгоритм для вашей головоломки.
Например, обход древовидной структуры настолько прост, что любое преобразование из и в SAT, скорее всего, будет гораздо более сложным, чем простая запись обхода напрямую.