? users online
  • Logout
    • Open hangout
    • Open chat for current file
<div class="notebook">

<div class="nb-cell program" name="p1">
:- use_module(library(clpfd)). % we're working with numbers, this makes it easier.

clue_1([9, 2, 8, 5]). % one number correct, but in the wrong place
clue_2([1, 9, 3, 7]). % two numbers are correct, but in the wrong place
clue_3([5, 2, 0, 1]). % one number is correct, and is also in the right place
clue_4([6, 5, 0, 7]). % none of the numbers are correct, anywhere
clue_5([8, 5, 2, 4]). % two numbers are correct, but in the wrong place

% rule: a digit is correct but it is in the wrong place
wrong_place(Digit, Index, Digits) :- nth1(Index1, Digits, Digit), Index \== Index1.

% rule: a digit is correct and it is in the right place
right_place(Digit, Index, Digits) :- nth1(Index, Digits, Digit).

% rule: the digit is wrong.
wrong(_, []).
wrong(Digit, [D|Ds]) :- Digit #\= D, wrong(Digit, Ds).

crack_code(Code) :-
    % A, B, C and D represent the four digits of the code, which are all between 0 and 9.
    A in 0..9,
    B in 0..9,
    C in 0..9,
    D in 0..9,

    % ';' means 'or', whereas ',' means 'and'

    % one digit in D1 is correct, but in the wrong place
    % the other three digits must therefore be incorrect
    % query this for each digit.
    clue_1(D1),
    (
        wrong_place(A, 1, D1), wrong(B, D1), wrong(C, D1), wrong(D, D1);
        wrong_place(B, 2, D1), wrong(A, D1), wrong(C, D1), wrong(D, D1);
        wrong_place(C, 3, D1), wrong(A, D1), wrong(B, D1), wrong(D, D1);
        wrong_place(D, 4, D1), wrong(A, D1), wrong(B, D1), wrong(C, D1)
    ),

    % two digits are correct this time, and they are both in the wrong place
    % exhaustively check every combination where two numbers are correct, and the other two are incorrect.
    clue_2(D2),
    (
        wrong_place(A, 1, D2), wrong_place(B, 2, D2), wrong(C, D2), wrong(D, D2);
        wrong_place(A, 1, D2), wrong_place(C, 3, D2), wrong(B, D2), wrong(D, D2);
        wrong_place(A, 1, D2), wrong_place(D, 4, D2), wrong(B, D2), wrong(C, D2);

        wrong_place(B, 2, D2), wrong_place(A, 1, D2), wrong(C, D2), wrong(D, D2);
        wrong_place(B, 2, D2), wrong_place(C, 3, D2), wrong(A, D2), wrong(D, D2);
        wrong_place(B, 2, D2), wrong_place(D, 4, D2), wrong(A, D2), wrong(C, D2);

        wrong_place(C, 3, D2), wrong_place(A, 1, D2), wrong(B, D2), wrong(D, D2);
        wrong_place(C, 3, D2), wrong_place(B, 2, D2), wrong(A, D2), wrong(D, D2);
        wrong_place(C, 3, D2), wrong_place(D, 4, D2), wrong(A, D2), wrong(B, D2);

        wrong_place(D, 4, D2), wrong_place(A, 1, D2), wrong(B, D2), wrong(C, D2);
        wrong_place(D, 4, D2), wrong_place(B, 2, D2), wrong(A, D2), wrong(C, D2);
        wrong_place(D, 4, D2), wrong_place(C, 3, D2), wrong(A, D2), wrong(B, D2)
    ),

    % one digit is correct, and also in the right place
    % as above, we still don't know which digit that is, so we check each one.
    clue_3(D3),
    (
        right_place(A, 1, D3), wrong(B, D3), wrong(C, D3), wrong(D, D3);
        right_place(B, 2, D3), wrong(A, D3), wrong(C, D3), wrong(D, D3);
        right_place(C, 3, D3), wrong(A, D3), wrong(B, D3), wrong(D, D3);
        right_place(D, 4, D3), wrong(A, D3), wrong(B, D3), wrong(C, D3)
    ),

    % none of the digits are correct, so they can be completely excluded
    % we know for a fact the final result will not contain any of these digits.
    clue_4(D4),
    (
        wrong(A, D4), wrong(B, D4), wrong(C, D4), wrong(D, D4)
    ),

    % again, two digits are correct but not in the right order
    % we do a similar check as before but also need to look
    % back into the previous clue to eliminate wrong candidates;
    % this is why we query D2, as well as D5.
    clue_5(D5),
    (
        wrong_place(A, 1, D5), wrong_place(B, 2, D5), wrong(C, D5), wrong(D, D5);
        wrong_place(A, 1, D5), wrong_place(C, 3, D5), wrong(B, D5), wrong(D, D5);
        wrong_place(A, 1, D5), wrong_place(D, 4, D5), wrong(B, D2), wrong(C, D2);

        wrong_place(B, 2, D5), wrong_place(A, 1, D5), wrong(C, D5), wrong(D, D5);
        wrong_place(B, 2, D5), wrong_place(C, 3, D5), wrong(A, D5), wrong(D, D5);
        wrong_place(B, 2, D5), wrong_place(D, 4, D5), wrong(A, D2), wrong(C, D2);

        wrong_place(C, 3, D5), wrong_place(A, 1, D5), wrong(B, D5), wrong(D, D5);
        wrong_place(C, 3, D5), wrong_place(B, 2, D5), wrong(A, D5), wrong(D, D5);
        wrong_place(C, 3, D5), wrong_place(D, 4, D5), wrong(A, D2), wrong(B, D2);

        wrong_place(D, 4, D5), wrong_place(A, 1, D5), wrong(B, D5), wrong(C, D5);
        wrong_place(D, 4, D5), wrong_place(B, 2, D5), wrong(A, D5), wrong(C, D5);
        wrong_place(D, 4, D5), wrong_place(C, 3, D5), wrong(A, D2), wrong(B, D2)
    ),

    % Take (or cut) the first result, no need for continued backtracking
    % this is probably most similar to an early return or short-circuit.
    !,

    % we've cracked the code! A, B, C, and D each refer to
    % the only answer that makes sense given the previous
    % rules.
    Code = [A, B, C, D].
</div>

</div>