% ==============================================================================
%
%  FILE
%    einstein.m
%
%  PURPOSE
%    Lösung des "Einstein-Rätsels"
%    (Siehe http://www.meyer-hilberg.de/pdf/NstRtsFsh.pdf!)
%
%    Die "Originalversion" dieses Rätsels enthält den Hinweis, daß "das grüne
%    Haus LINKS VOM weißen Haus steht". Der korrekte Hinweis sollte
%    wahrscheinlich lauten, daß "das grüne Haus LINKS NEBEN dem weißen Haus
%    steht". Beim "korrekten" Hinweis ergibt sich genau eine Lösung, bei der
%    "Originalversion" mindestens zwei. Dieses Octave-/Matlab-Programm sucht
%    alle Lösungen! (Zum kostenlosen Octave siehe http://www.octave.org/!)
%
%    Es gibt fünf Häuser mit je einer anderen Farbe.
%    In jedem Haus wohnt eine Person einer anderen Nationalität.
%    Jeder Hausbewohner bevorzugt ein bestimmtes Getränk, raucht eine bestimmte
%    Zigarettenmarke und hält ein bestimmtes Haustier.
%    Keine der 5 Personen trinkt das gleiche Getränk, raucht die gleichen
%    Zigaretten oder hält das gleiche Tier wie einer seiner Nachbarn.
%
%
%  MODIFICATION HISTORY
%
%  Version |   Date   |    Author     |   Modification
%  -----------------------------------------------------------------------------
%      1   | 05.06.03 | Meyer-Hilberg | Draft
%      2   | 21.06.03 | Meyer-Hilberg | Final
%      3   | 23.11.20 | Meyer-Hilberg | Aufgeräumt
%
% ==============================================================================
%
%einstein;

function einstein

Text = ['Farbe       '; ...
        'Nationalität'; ...
        'Getränk     '; ...
        'Zigaretten  '; ...
        'Haustier    '; ...
        'Rot         '; ...
        'Grün        '; ...
        'Weiß        '; ...
        'Gelb        '; ...
        'Blau        '; ...
        'Brite       '; ...
        'Schwede     '; ...
        'Däne        '; ...
        'Norweger    '; ...
        'Deutscher   '; ...
        'Tee         '; ...
        'Kaffee      '; ...
        'Milch       '; ...
        'Bier        '; ...
        'Wasser      '; ...
        'Pall Mall   '; ...
        'Dunhill     '; ...
        'Marlboro    '; ...
        'Winfield    '; ...
        'Rothmanns   '; ...
        'Hund        '; ...
        'Vogel       '; ...
        'Katze       '; ...
        'Pferd       '; ...
        'Fisch       '; ...
        '            '];

Jawoll    = 1;
Goatnetta = 0;

Passt   = Jawoll;
Hinweis = 0;

Minimum = zeros (1, 18);
Maximum = zeros (1, 18);
Nummer  = zeros (1, 18);

Matrix = zeros (5, 5);

Versuch = 0;
Loesung = 0;

while 1

  Versuch = Versuch + 1;

  if Passt

    Hinweis = Hinweis + 1;

    if     Hinweis ==  4
      Minimum (Hinweis) = 1;
      Maximum (Hinweis) = 4;
    elseif Hinweis ==  5
      Minimum (Hinweis) = Nummer (4) + 1;
%      Maximum (Hinweis) = Nummer (4) + 1;
      Maximum (Hinweis) = 5;
    elseif Hinweis ==  6
      Minimum (Hinweis) = Nummer (4);
      Maximum (Hinweis) = Nummer (4);
    elseif Hinweis ==  8
      Minimum (Hinweis) = 3;
      Maximum (Hinweis) = 3;
    elseif Hinweis == 10
      Minimum (Hinweis) = 1;
      Maximum (Hinweis) = 1;
    elseif Hinweis == 12
      Minimum (Hinweis) = Nummer (11) - 1;
      Maximum (Hinweis) = Nummer (11) + 1;
    elseif Hinweis == 13
      Minimum (Hinweis) = Nummer (9) - 1;
      Maximum (Hinweis) = Nummer (9) + 1;
    elseif Hinweis == 15
      Minimum (Hinweis) = Nummer (10) - 1;
      Maximum (Hinweis) = Nummer (10) + 1;
    elseif Hinweis == 17
      Minimum (Hinweis) = Nummer (11) - 1;
      Maximum (Hinweis) = Nummer (11) + 1;
    else
      Minimum (Hinweis) = 1;
      Maximum (Hinweis) = 5;
    end

    if Minimum (Hinweis) < 1

      if (Hinweis == 12) || (Hinweis == 13) || ...
         (Hinweis == 15) || (Hinweis == 17)
        Minimum (Hinweis) = Minimum (Hinweis) + 2;
      else
        Minimum (Hinweis) = Minimum (Hinweis) + 1;
      end

    end

    if Maximum (Hinweis) > 5

      if (Hinweis == 12) || (Hinweis == 13) || ...
         (Hinweis == 15) || (Hinweis == 17)
        Maximum (Hinweis) = Maximum (Hinweis) - 2;
      else
        Maximum (Hinweis) = Maximum (Hinweis) - 1;
      end

    end

    Nummer (Hinweis) = Minimum (Hinweis);

  else

    if (Hinweis == 12) || (Hinweis == 13) || (Hinweis == 15) || (Hinweis == 17)
      Nummer (Hinweis) = Nummer (Hinweis) + 2;
    else
      Nummer (Hinweis) = Nummer (Hinweis) + 1;
    end

    while Nummer (Hinweis) > Maximum (Hinweis)

      Hinweis = Hinweis - 1;

      if     Hinweis ==  1
% Der Brite lebt im roten Haus.
        Matrix (2, Nummer (Hinweis)) = 0;
        Matrix (1, Nummer (Hinweis)) = 0;

      elseif Hinweis ==  2
% Der Schwede hält einen Hund.
        Matrix (2, Nummer (Hinweis)) = 0;
        Matrix (5, Nummer (Hinweis)) = 0;

      elseif Hinweis ==  3
% Der Däne trinkt gerne Tee.
        Matrix (2, Nummer (Hinweis)) = 0;
        Matrix (3, Nummer (Hinweis)) = 0;

      elseif Hinweis ==  4
% Das grüne Haus steht links vom weißen Haus.
        Matrix (1, Nummer (Hinweis)) = 0;

      elseif Hinweis ==  5
% Das grüne Haus steht links vom weißen Haus.
        Matrix (1, Nummer (Hinweis)) = 0;

      elseif Hinweis ==  6
% Der Besitzer des grünen Hauses trinkt Kaffee.
        Matrix (3, Nummer (Hinweis)) = 0;

      elseif Hinweis ==  7
% Die Person, die Pall Mall raucht, hält einen Vogel.
        Matrix (4, Nummer (Hinweis)) = 0;
        Matrix (5, Nummer (Hinweis)) = 0;

      elseif Hinweis ==  8
% Der Mann, der im mittleren Haus wohnt, trinkt Milch.
        Matrix (3, Nummer (Hinweis)) = 0;

      elseif Hinweis ==  9
% Der Besitzer des gelben Hauses raucht Dunhill.
        Matrix (1, Nummer (Hinweis)) = 0;
        Matrix (4, Nummer (Hinweis)) = 0;

      elseif Hinweis == 10
% Der Norweger wohnt im ersten Haus.
        Matrix (2, Nummer (Hinweis)) = 0;

      elseif Hinweis == 11
% Der Marlboro-Raucher wohnt neben dem, der eine Katze hält.
        Matrix (4, Nummer (Hinweis)) = 0;

      elseif Hinweis == 12
% Der Marlboro-Raucher wohnt neben dem, der eine Katze hält.
        Matrix (5, Nummer (Hinweis)) = 0;

      elseif Hinweis == 13
% Der Mann, der ein Pferd hält, wohnt neben dem, der Dunhill raucht.
        Matrix (5, Nummer (Hinweis)) = 0;

      elseif Hinweis == 14
% Der Winfield-Raucher trinkt gerne Bier.
        Matrix (4, Nummer (Hinweis)) = 0;
        Matrix (3, Nummer (Hinweis)) = 0;

      elseif Hinweis == 15
% Der Norweger wohnt neben dem blauen Haus.
        Matrix (1, Nummer (Hinweis)) = 0;

      elseif Hinweis == 16
% Der Deutsche raucht Rothmanns.
        Matrix (2, Nummer (Hinweis)) = 0;
        Matrix (4, Nummer (Hinweis)) = 0;

      elseif Hinweis == 17
% Der Marlboro-Raucher hat einen Nachbarn, der Wasser trinkt.
        Matrix (3, Nummer (Hinweis)) = 0;

      else

        break;

      end

      if (Hinweis == 12) || (Hinweis == 13) || ...
         (Hinweis == 15) || (Hinweis == 17)
        Nummer (Hinweis) = Nummer (Hinweis) + 2;
      else
        Nummer (Hinweis) = Nummer (Hinweis) + 1;
      end

    end

    if Hinweis < 1
      break;
    end

  end

  Passt = Goatnetta;

  if     Hinweis ==  1
% Der Brite lebt im roten Haus.
    if (Matrix (2, Nummer (Hinweis)) == 0) && ...
       (Matrix (1, Nummer (Hinweis)) == 0)
      Matrix (2, Nummer (Hinweis)) = 1;
      Matrix (1, Nummer (Hinweis)) = 1;
      Passt = Jawoll;
    end

  elseif Hinweis ==  2
% Der Schwede hält einen Hund.
    if (Matrix (2, Nummer (Hinweis)) == 0) && ...
       (Matrix (5, Nummer (Hinweis)) == 0)
      Matrix (2, Nummer (Hinweis)) = 2;
      Matrix (5, Nummer (Hinweis)) = 1;
      Passt = Jawoll;
    end

  elseif Hinweis ==  3
% Der Däne trinkt gerne Tee.
    if (Matrix (2, Nummer (Hinweis)) == 0) && ...
       (Matrix (3, Nummer (Hinweis)) == 0)
      Matrix (2, Nummer (Hinweis)) = 3;
      Matrix (3, Nummer (Hinweis)) = 1;
      Passt = Jawoll;
    end

  elseif Hinweis ==  4
% Das grüne Haus steht links vom weißen Haus.
    if Matrix (1, Nummer (Hinweis)) == 0
      Matrix (1, Nummer (Hinweis)) = 2;
      Passt = Jawoll;
    end

  elseif Hinweis ==  5
% Das grüne Haus steht links vom weißen Haus.
    if Matrix (1, Nummer (Hinweis)) == 0
      Matrix (1, Nummer (Hinweis)) = 3;
      Passt = Jawoll;
    end

  elseif Hinweis ==  6
% Der Besitzer des grünen Hauses trinkt Kaffee.
    if Matrix (3, Nummer (Hinweis)) == 0
      Matrix (3, Nummer (Hinweis)) = 2;
      Passt = Jawoll;
    end

  elseif Hinweis ==  7
% Die Person, die Pall Mall raucht, hält einen Vogel.
    if (Matrix (4, Nummer (Hinweis)) == 0) && ...
       (Matrix (5, Nummer (Hinweis)) == 0)
      Matrix (4, Nummer (Hinweis)) = 1;
      Matrix (5, Nummer (Hinweis)) = 2;
      Passt = Jawoll;
    end

  elseif Hinweis ==  8
% Der Mann, der im mittleren Haus wohnt, trinkt Milch.
    if Matrix (3, Nummer (Hinweis)) == 0
      Matrix (3, Nummer (Hinweis)) = 3;
      Passt = Jawoll;
    end

  elseif Hinweis ==  9
% Der Besitzer des gelben Hauses raucht Dunhill.
    if (Matrix (1, Nummer (Hinweis)) == 0) && ...
       (Matrix (4, Nummer (Hinweis)) == 0)
      Matrix (1, Nummer (Hinweis)) = 4;
      Matrix (4, Nummer (Hinweis)) = 2;
      Passt = Jawoll;
    end

  elseif Hinweis == 10
% Der Norweger wohnt im ersten Haus.
    if Matrix (2, Nummer (Hinweis)) == 0
      Matrix (2, Nummer (Hinweis)) = 4;
      Passt = Jawoll;
    end

  elseif Hinweis == 11
% Der Marlboro-Raucher wohnt neben dem, der eine Katze hält.
    if Matrix (4, Nummer (Hinweis)) == 0
      Matrix (4, Nummer (Hinweis)) = 3;
      Passt = Jawoll;
    end

  elseif Hinweis == 12
% Der Marlboro-Raucher wohnt neben dem, der eine Katze hält.
    if Matrix (5, Nummer (Hinweis)) == 0
      Matrix (5, Nummer (Hinweis)) = 3;
      Passt = Jawoll;
    end

  elseif Hinweis == 13
% Der Mann, der ein Pferd hält, wohnt neben dem, der Dunhill raucht.
    if Matrix (5, Nummer (Hinweis)) == 0
      Matrix (5, Nummer (Hinweis)) = 4;
      Passt = Jawoll;
    end

  elseif Hinweis == 14
% Der Winfield-Raucher trinkt gerne Bier.
    if (Matrix (4, Nummer (Hinweis)) == 0) && ...
       (Matrix (3, Nummer (Hinweis)) == 0)
      Matrix (4, Nummer (Hinweis)) = 4;
      Matrix (3, Nummer (Hinweis)) = 4;
      Passt = Jawoll;
    end

  elseif Hinweis == 15
% Der Norweger wohnt neben dem blauen Haus.
    if Matrix (1, Nummer (Hinweis)) == 0
      Matrix (1, Nummer (Hinweis)) = 5;
      Passt = Jawoll;
    end

  elseif Hinweis == 16
% Der Deutsche raucht Rothmanns.
    if (Matrix (2, Nummer (Hinweis)) == 0) && ...
       (Matrix (4, Nummer (Hinweis)) == 0)
      Matrix (2, Nummer (Hinweis)) = 5;
      Matrix (4, Nummer (Hinweis)) = 5;
      Passt = Jawoll;
    end

  elseif Hinweis == 17
% Der Marlboro-Raucher hat einen Nachbarn, der Wasser trinkt.
    if Matrix (3, Nummer (Hinweis)) == 0
      Matrix (3, Nummer (Hinweis)) = 5;
      Passt = Jawoll;
    end

  elseif Hinweis == 18
% Frage: Wem gehört der Fisch?
    if Matrix (5, Nummer (Hinweis)) == 0
      Matrix (5, Nummer (Hinweis)) = 5;
      Passt = Jawoll;
    end

  else

    error ('Dumm gelaufen!');

  end

  if (Hinweis > 17) && Passt

    Loesung = Loesung + 1;

    disp (sprintf ('\nLösung %d (%d Versuche):\n', Loesung, Versuch));

    for Index = 1:5

      Zeile = sprintf ('%s : ', Text (Index, :));

      for Haus = 1:5

        if Matrix (Index, Haus) > 0
          Eintrag = 5 * Index + Matrix (Index, Haus);
          Zeile = sprintf ('%s %s', Zeile, Text (Eintrag, :));
        else
          Zeile = sprintf ('%s %s', Zeile, Text (31, :));
        end

      end

      disp (Zeile);

    end

    Matrix (5, Nummer (Hinweis)) = 0;
    Passt = Goatnetta;

  end

end

disp (sprintf ('\nEs gibt insgesamt %d Lösungen! (%d Versuche)\n', ...
               Loesung, Versuch));

end