Solving the “Miracle Sudoku” in Prolog
Very nicely done, thank you for sharing this!<p>A CLP(FD&#x2F;ℤ) solution such as this one has two parts: First, the relevant constraints are posted. Second, a <i>search</i> tries to find concrete solutions. In general, a search is necessary because the constraints by themselves are not sufficient to deduce the unique solution as that would be computationally prohibitive.<p>You can therefore influence the speed of the logic program in two categorically distinct ways: First, you can post different constraints or try a different formulation altogether. Second, you can try different <i>search heuristics</i> that try to find concrete solutions more efficiently.<p>Regarding constraint propagation, there is a clear trade-off between <i>strength</i> and <i>efficiency</i> of propagation. For instance, the all_distinct&#x2F;1 constraint that is used in the sample solution propagates <i>very strongly</i>, and is therefore <i>much slower</i> than the <i>weaker</i> all_different&#x2F;1 constraint, even though they are completely equivalent from a semantic perspective: Both are true if and only if the given integers are pairwise distinct. It depends on the problem at hand whether the stronger propagation pays off, or whether the weaker propagation is in fact sufficient to quickly find solutions.<p>Especially for very simple tasks such as Sudoku, quick and weak propagation may well outperform strong and slow propagation.<p>In this concrete example, I easily achieved a 20-fold speedup by replacing the all_distinct&#x2F;1 constraint with all_different&#x2F;1, and using the <i>ff</i> labeling strategy to search for concrete solutions. <i>ff</i> means <i>first-fail</i>, and is often a very good strategy. To get this, I simply textually replaced all occurrences of all_distinct with all_different in the source code, and posted:<p><pre><code>    ?- problem(1, Rows),
       sudoku(Rows),
       append(Rows, Vs),
       labeling([ff], Vs),
       maplist(portray_clause, Rows).
</code></pre>
Also, in less than 5 minutes, I just produced all 88 solutions for problem 3 which is shown at the end of the article. This is only due to using <i>less</i> powerful propagation, and a better search heuristic.<p>And this is one of the key attractions of constraint logic programming (CLP): You can relatively easily try different search strategies <i>while keeping the model the same</i>.<p>In Hakan&#x27;s very nice Picat solution, you see that a specific search heuristic is used, specified as:<p><pre><code>    solve([ffd,down], Vars).
</code></pre>
In addition, Hakan&#x27;s program uses all_different&#x2F;1. For a fair comparison between the solutions, constraints with the same propagation strength, and the same search heuristic must be used in both approaches.