Resolvendo o Problema das Rainhas do LinkedIn com SMT: Mais Fácil que SAT!

Este artigo descreve como resolver o quebra-cabeça das 'Rainhas do LinkedIn' — uma variação do clássico problema das N-Rainhas com restrições regionais adicionais — usando o resolvedor SMT Z3. O autor demonstra que expressar o problema em SMT, utilizando variáveis ​​inteiras e restrições, é significativamente mais simples do que a formulação SAT equivalente, que requer muitas cláusulas booleanas. Embora os resolvedores SMT possam ser mais lentos do que os resolvedores SAT altamente otimizados como o Glucose, a facilidade de codificação torna o SMT preferível para muitos. A postagem inclui código completo e verificações de sanidade úteis para verificar a correção do modelo. Isso fornece uma explicação convincente para a preferência da indústria por ferramentas que compilam para SAT em vez de usar SAT diretamente.