Logic programming is overrated, at least for logic puzzles (2013)

Prolog comes from the era (the 70s) where computationally interesting and algorithmically complex problems were a proportionately much larger part of the computing scene than they are today, what with our personal computers, data crunching, and web applications. It’s not really that those kinds of computing paradigms are bad so much as they aren’t nearly as relevant as they were. And a typical programmer, even if they do encounter a problem appropriate for that kind of approach, is much better off using the typical software they have tons of experience with, rather than attempting to learn a new paradigm and uncovering all its pitfalls in the process of learning it.

Exhaustively searching an exponential space with no heuristics for reducing the search space is obviously gonna be way easier in a familiar language than in a new language.

The one use case I do see for prolog and similar tools in the modern day is for Constraint Satisfaction programming. Obviously, exhaustively searching an exponential solution space won’t be better for that, but typically you can use concepts like Edge and Arc consistency (which are core to CSP solvers) to greatly reduce the actual search space. Implementing those algorithms from scratch in an imperative language is annoyingly hard, so reaching for optimized, generalized implementations can be a good choice.

For something like a Sudoku solver, edge/arc consistency can greatly improve compute times. If you’re good at sudoku, you are already implementing these techniques when solving puzzles, just like good chess players implement minimax search without having to be told what minimax search is.

https://www.sciencedirect.com/topics/computer-science/arc-co...

>> I think a lot of people mistakenly believe that core.logic is working some magic behind the scenes to solve puzzles in some amazingly efficient manner. On the contrary, it's just brute force search, using complex machinery which just slows it down versus a for comprehension.

If that's what core.logic is, then core.logic is not logic programming.

Logic programming refers to one of two things: either Prolog-like languages where programs are sets of definite clauses executed by SLD-Refutation of a goal, and evaluation returns all bindings of the variables in the goal that make the goal true; or Answer Set Programming (ASP), where programs are similar to definite programs, but the semantics are stable model semantics and evaluation finds all the stable models of a program.

Both of these approaches incorporate search, but neither is "just brute force search", in any way, shape or form.

How is that "easier" than the following straightforward Prolog code?

    zebra(Houses) :-
        houses(Houses),
        member(house(red, english, _, _, _), Houses),
        member(house(_, spanish, dog, _, _), Houses),
        member(house(green, _, _, coffee, _), Houses),
        member(house(_, ukrainian, _, tea, _), Houses),
        right_of(house(green,_,_,_,_),
          house(ivory,_,_,_,_), Houses),
        member(house(_, _, snails, _, winstons), Houses),
        member(house(yellow, _, _, _, kools), Houses),
        Houses = [_, _, house(_, _, _, milk, _), _,_],
        Houses = [house(_, norwegian, _, _, _)|_],
        next_to(house(_,_,_,_,chesterfields),
          house(_,_,fox,_,_), Houses),
        next_to(house(_,_,_,_,kools),
          house(_,_,horse,_,_), Houses),
        member(house(_, _, _, orange_juice, lucky_strikes), Houses),
        member(house(_, japanese, _, _, parliaments), Houses),
        next_to(house(_,norwegian,_,_,_),
          house(blue,_,_,_,_), Houses),
        member(house(_, _, zebra, _, _), Houses),
        member(house(_, _, _, water, _), Houses).

    houses([
        house(_, _, _, _, _),
        house(_, _, _, _, _),
        house(_, _, _, _, _),
        house(_, _, _, _, _),
        house(_, _, _, _, _)]).
    
    right_of(A, B, [B, A | _]).
    right_of(A, B, [_ | Y]) :- right_of(A, B, Y).
    
    next_to(A, B, [A, B | _]).
    next_to(A, B, [B, A | _]).
    next_to(A, B, [_ | Y]) :- next_to(A, B, Y).
    
    member(X, [X|_]).
    member(X, [_|Y]) :- member(X, Y).
    
    ?- zebra(Houses) 

To check it out yourself, copy/paste this into https://quantumprolog.sgml.io/browser-demo/browser-demo.html and execute on your browser.

  solution(Pairs, Water, Zebra, Vs) :-
          Table   = [Houses,Nations,Drinks,Smokes,Animals],
          Houses  = [Red,Green,Yellow,Blue,Ivory],
          Nations = [England,Spain,Ukraine,Norway,Japan],
          Names   = [england,spain,ukraine,norway,japan],
          Drinks  = [Coffee,Milk,OrangeJuice,Tea,Water],
          Smokes  = [OldGold,Kools,Chesterfield,LuckyStrike,Parliaments],
          Animals = [Dog,Snails,Horse,Fox,Zebra],
          pairs_keys_values(Pairs, Nations, Names),
          maplist(all_distinct, Table),
          append(Table, Vs),
          Vs ins 1..5,
          England #= Red,               % hint 1
          Spain #= Dog,                 % hint 2
          Coffee #= Green,              % hint 3
          Ukraine #= Tea,               % hint 4
          Green #= Ivory + 1,           % hint 5
          OldGold #= Snails,            % hint 6
          Kools #= Yellow,              % hint 7
          Milk #= 3,                    % hint 8
          Norway #= 1,                  % hint 9
          next_to(Chesterfield, Fox),   % hint 10
          next_to(Kools, Horse),        % hint 11
          LuckyStrike #= OrangeJuice,   % hint 12
          Japan #= Parliaments,         % hint 13
          next_to(Norway, Blue).        % hint 14

  next_to(H, N) :- abs(H-N) #= 1.

It's subjective, but the above is far clearer about the rules to me. Compare `next_to` in both:

  next_to(Kools, Horse)
  next_to(house(_,_,_,_,kools),
          house(_,_,horse,_,_), Houses)

The former is much more straightforward as a representation of the hint. You don't need to know which entry in a `house` corresponds to cigarette brand and animal, you can just directly compare the two and say Kools is next to Horse.