VIER und NEUN

1. Aufgabe

Diese Aufgabe stellt ein Zahlenrätsel dar, dessen Lösung durch eine C#-Anwendung zu bestimmen ist. Lesen Sie die nachfolgende Aufgabenstellung konzentriert durch und entwickeln Sie Ihr Konzept zunächst auf dem Papier, bevor Sie mit der Entwicklung starten.

Wir betrachten folgendes Zahlenpuzzle: VIER und NEUN repräsentieren zwei vierstellige Zahlen, die aus der Quadratur zweier natürlicher Zahlen x und y gewonnen werden.

Also: Es gibt ein x ∈ N mit x2 = VIER und es gibt ein y ∈ N mit y2 = NEUN.

Jeder Buchstabe aus „VIER“ und „NEUN“ stellt eine Ziffer dar.

  • Gleiche Buchstaben sind gleiche Ziffern.

  • Ungleiche Buchstaben sind ungleiche Ziffern.

Bestimmen Sie x und y! Setzen Sie in Ihrer Realisierung das Zahlenpuzzle in ein objektorientiertes Programm um und zerlegen Sie zur Vereinfachung die Aufgabe in mehrere Teilschritte.

1.1. Klasse Candidate

Das Rätsel ist nicht eindeutig lösbar, d.h. es gibt mehrere Zahlenpaare (x,y), die die Aufgabenstellung erfüllen. Wir fangen deshalb mit einer Klasse Candidate an. Ein Candidate-Objekt beschreibt zwei natürliche Zahlen x und y, deren Quadrate vierstellig sind und die somit ein möglicher Lösungskandidat für das Zahlenrätsel sein könnten (Tabelle 1):

Element

Beschreibung

Eigenschaft X

public int X { get; }

Erste Zahl x des Paares (x,y).

Eigenschaft Y

public int Y { get; }

Zweite Zahl y des Paares (x,y).

Tabelle 1. Öffentliche Elemente der Klasse Candidate.

1.2. Klasse VierNeun

Mit Hilfe der Klasse VierNeun berechnen wir sukzessive alle Candidate-Objekte, die als Lösung des Vier-Neun-Puzzles in Betracht kommen. Implementieren Sie zunächst eine Klasse VierNeun mit einer Methode ComputeCandidates gemäß Tabelle 2:

Element

Beschreibung

Methode ComputeCandidates

public void ComputeCandidates();

Berechnet eine Liste aller Candidate-Objekte, deren x- und y-Element ein vierstelliges Quadrat besitzen.

Eigenschaft Candidates

public List<Candidate> Candidates { get; }

Liefert das Resultat eines ComputeCandidates-Methodenaufrufs zurück.

Tabelle 2. Klasse VierNeun


Bringen Sie den nachfolgenden Testrahmen für die zwei Klassen Candidate und VierNeun zum Laufen:

VierNeun vn = new VierNeun();
vn.ComputeCandidates();
Console.WriteLine("Initial Candidates: {0}", vn.Count);

Kontrollfrage: Wie viele Candidate-Objekte gibt es?

1.3. Schnittstelle IConstraint

Wir gehen nun auf die Randbedingungen ein, die an ein Candidate-Objekt gestellt werden, wenn es eine Lösung des Vier-Neun-Puzzles sein soll. Da es mehrere Randbedingungen gibt, definieren wir zunächst eine Schnittstelle IConstraint. Sie definiert für alle noch zu beschreibenden Randbedingungen einen leicht lesbaren Namen (Eigenschaft Name) sowie eine Methode Check zum Überprüfen einer Randbedingung (Tabelle 3):

Element

Beschreibung

Methode Check

bool Check (Candidate c);

Methode zum Überprüfen einer Randbedingung.

Eigenschaft Name

String Name { get; }

Lesbarer Name für eine Randbedingung.

Tabelle 3. Schnittstelle IConstraint.

1.4. Randbedingung „Vier

Implementieren Sie in diesem Teilabschnitt eine Klasse CheckVier, die einen Vertrag mit der Schnittstelle IConstraint eingeht. Der Name des Vertrags lautet "Constraint-VIER". Die Realisierung der Check-Methode überprüft alle Ziffern, ob sie das Muster „Vier“ erfüllen. In einfachen Worten: Alle vier Ziffern müssen verschieden sein.

1.5. Klasse VierNeun: Methode ApplyConstraint

Mit Hilfe eines CheckVier-Objekts verkleinern wir nun die Menge aller Kandidaten eines VierNeun-Objekts, so dass sie die "Constraint-VIER"-Randbedingung erfüllen. Erweitern Sie zu diesem Zweck die VierNeun-Klasse um die Methode ApplyConstraint (Tabelle 4):

Element

Beschreibung

Methode ApplyConstraint

public void ApplyConstraint (IConstraint c);

Die Methode Check des übergebenen Objekts c wird auf die komplette Liste der vorhandenen Candidate-Objekte angewendet. Candidate-Objekte, die die Bedingung nicht erfüllen, werden aus der Liste entfernt.

Tabelle 4. Klasse VierNeun


Testrahmen:

VierNeun vn = new VierNeun();
vn.ComputeCandidates();
Console.WriteLine("Initial Candidates:       {0}", vn.Count);

IConstraint c1 = new CheckVier();
Console.WriteLine("Processing constraint:   '{0}'", c1.Name);
vn.ApplyConstraint(c1);
Console.WriteLine("-> Remaining candidates:  {0}", vn.Count);

Kontrollfrage: Wie viele Candidate-Objekte sind in diesem Teilabschnitt noch übrig?

1.6. Randbedingung „Neun

Implementieren Sie in diesem Teilabschnitt eine Klasse CheckNeun, die einen Vertrag mit der Schnittstelle IConstraint eingeht. Der Name des Vertrags lautet "Constraint-NEUN". Die Realisierung der Check-Methode überprüft alle Ziffern, ob sie das Muster „Neun“ erfüllen. In einfachen Worten: Die erste und vierte Ziffer müssen übereinstimmen, die anderen Ziffern müssen verschieden sein.

Wenden Sie nun ein CheckNeun-Objekt auf die Liste der noch vorhandenen Candidate-Objekte an. Wie viele Candidate-Objekte sind nun noch vorhanden?

1.7. Randbedingung „Correlation

Implementieren Sie in diesem Teilabschnitt eine Klasse CheckCorrelation, die einen Vertrag mit der Schnittstelle IConstraint eingeht. Der Name des Vertrags lautet "Constraint-CORRELATION". Die Realisierung der Check-Methode überprüft die Ziffern von x und y auf Korrelation. In einfachen Worten: Die zweite Ziffer von NEUN muss mit der dritten Ziffer von VIER übereinstimmen, alle anderen Ziffern müssen verschieden sein.

Testrahmen:

VierNeun vn = new VierNeun();

vn.ComputeCandidates();
Console.WriteLine("Initial Candidates:       {0}", vn.Count);

IConstraint c1 = new CheckVier();
Console.WriteLine("Processing constraint:   '{0}'", c1.Name);
vn.ApplyConstraint(c1);
Console.WriteLine("-> Remaining candidates:  {0}", vn.Count);
        
IConstraint c2 = new CheckNeun();
Console.WriteLine("Processing constraint:   '{0}'", c2.Name);
vn.ApplyConstraint(c2);
Console.WriteLine("-> Remaining candidates:  {0}", vn.Count);

IConstraint c3 = new CheckCorrelation();
Console.WriteLine("Processing constraint:   '{0}'", c3.Name);
vn.ApplyConstraint(c3);
Console.WriteLine("-> Remaining candidates:  {0}", vn.Count);

Frage: Wie viele Candidate-Objekte sind in diesem Teilabschnitt noch übrig?

1.8. Eineindeutige Lösung

Wenn Sie alle bislang berechneten Zahlenpaare betrachten, können Sie die folgende Beobachtung machen: Es existiert genau eine Lösung mit der Eigenschaft:

Ist von einem Zahlenpaar die eine Zahl bekannt, so kennt man auch die andere Zahl und umgekehrt!

Frage: Welches Candidate-Objekt erfüllt das Rätsel eindeutig?

2. Lösung

Quellcode: Siehe auch github.com/peterloos/CSharp_VierNeun.git.

Es folgen die Realisierungen der beteiligten Klassen Candidate (Listing 2), CheckVier (Listing 3), CheckNeun (Listing 4), CheckCorrelation (Listing 5), VierNeun (Listing 6) sowie der Schnittstelle IConstraint (Listing 1):

01: interface IConstraint
02: {
03:     bool Check(Candidate c);
04: 
05:     String Name { get; }
06: }

Beispiel 1. Definition der Schnittstelle IConstraint.


01: class Candidate
02: {
03:     private int x;
04:     private int y;
05: 
06:     // c'tor
07:     public Candidate(int x, int y)
08:     {
09:         this.x = x;
10:         this.y = y;
11:     }
12: 
13:     // properties
14:     public int X
15:     {
16:         get
17:         {
18:             return this.x;
19:         }
20:     }
21: 
22:     public int Y
23:     {
24:         get
25:         {
26:             return this.y;
27:         }
28:     }
29: 
30:     // contract with base class 'Object'
31:     public override String ToString()
32:     {
33:         return String.Format("{0}, {1} -> [{2}, {3}]",
34:             this.x, this.y, this.x * this.x, this.y * this.y);
35:     }
36: }

Beispiel 2. Implementierung der Klasse Candidate.


01: class CheckVier : IConstraint
02: {
03:     public String Name
04:     {
05:         get
06:         {
07:             return "Constraint-VIER";
08:         }
09:     }
10: 
11:     public bool Check(Candidate cand)
12:     {
13:         int square = cand.X * cand.X;
14: 
15:         int[] four = new int[]
16:         {
17:             square / 1000,
18:             (square % 1000) / 100,
19:             (square % 100) / 10,
20:             (square % 10)
21:         };
22: 
23:         if (four[0] == four[1] ||
24:             four[0] == four[2] ||
25:             four[0] == four[3])
26:             return false;
27: 
28:         if (four[1] == four[2] ||
29:             four[1] == four[3])
30:             return false;
31: 
32:         if (four[2] == four[3])
33:             return false;
34: 
35:         return true;
36:     }
37: }

Beispiel 3. Implementierung der Klasse CheckVier.


01: class CheckNeun : IConstraint
02: {
03:     public String Name
04:     {
05:         get
06:         {
07:             return "Constraint-NEUN";
08:         }
09:     }
10: 
11:     public bool Check(Candidate cand)
12:     {
13:         int square = cand.Y * cand.Y;
14: 
15:         int[] nine = new int[]
16:         {
17:             square / 1000,
18:             (square % 1000) / 100,
19:             (square % 100) / 10,
20:             (square % 10)
21:         };
22: 
23:         if (nine[0] != nine[3])
24:             return false;
25: 
26:         if (nine[1] == nine[2])
27:             return false;
28: 
29:         if (nine[0] == nine[1] || nine[0] == nine[2])
30:             return false;
31: 
32:         if (nine[1] == nine[3] || nine[2] == nine[3])
33:             return false;
34: 
35:         return true;
36:     }
37: }

Beispiel 4. Implementierung der Klasse CheckNeun.


01: class CheckCorrelation : IConstraint
02: {
03:     public String Name
04:     {
05:         get
06:         {
07:             return "Constraint-CORRELATION";
08:         }
09:     }
10: 
11:     public bool Check(Candidate cand)
12:     {
13:         int squareX = cand.X * cand.X;
14:         int squareY = cand.Y * cand.Y;
15: 
16:         int[] four = new int[]
17:         {
18:             squareX / 1000,
19:             (squareX % 1000) / 100,
20:             (squareX % 100) / 10,
21:             (squareX % 10)
22:         };
23: 
24:         int[] nine = new int[]
25:         {
26:             squareY / 1000,
27:             (squareY % 1000) / 100,
28:             (squareY % 100) / 10,
29:             (squareY % 10)
30:         };
31: 
32: 
33:         if (nine[1] != four[2])
34:             return false;
35: 
36:         if (nine[0] == four[0] ||
37:             nine[0] == four[1] ||
38:             nine[0] == four[2] ||
39:             nine[0] == four[3])
40:             return false;
41: 
42:         if (nine[2] == four[0] ||
43:             nine[2] == four[1] ||
44:             nine[2] == four[2] ||
45:             nine[2] == four[3])
46:             return false;
47: 
48:         return true;
49:     }
50: }

Beispiel 5. Implementierung der Klasse CheckCorrelation.


001: class VierNeun
002: {
003:     private List<Candidate> candidates;
004: 
005:     public VierNeun()
006:     {
007:         this.candidates = new List<Candidate>();
008:     }
009: 
010:     // properties
011:     public int Count
012:     {
013:         get
014:         {
015:             return this.candidates.Count;
016:         }
017:     }
018: 
019:     public List<Candidate> Candidates
020:     {
021:         get
022:         {
023:             return new List<Candidate>(this.candidates);
024:         }
025:     }
026: 
027:     // public interface
028:     public void ComputeCandidates()
029:     {
030:         // compute all numbers that have squares with 4 digits
031:         List<int> numbers = new List<int>();
032:         for (int i = 1; i < 100; i++)
033:         {
034:             int square = i * i;
035:             if (square >= 1000 && square <= 9999)
036:             {
037:                 numbers.Add(i);
038:             }
039:         }
040: 
041:         // generate cross product (number x number)
042:         for (int i = 0; i < numbers.Count; i++)
043:         {
044:             for (int j = 0; j < numbers.Count; j++)
045:             {
046:                 Candidate c = new Candidate(numbers[i], numbers[j]);
047:                 this.candidates.Add(c);
048:             }
049:         }
050:     }
051: 
052:     public void ApplyConstraint(IConstraint c)
053:     {
054:         List<Candidate> tmp = new List<Candidate>();
055: 
056:         for (int i = 0; i < this.candidates.Count; i++)
057:         {
058:             if (c.Check(this.candidates[i]))
059:                 tmp.Add(this.candidates[i]);
060:         }
061: 
062:         // reduce list of possible candidates
063:         this.candidates = tmp;
064:     }
065: 
066:     public Candidate Unique()
067:     {
068:         for (int i = 0; i < this.candidates.Count; i++)
069:         {
070:             bool unique = true;
071:             for (int j = 0; j < this.candidates.Count; j++)
072:             {
073:                 if (j == i)
074:                     continue;
075: 
076:                 if (this.candidates[i].X == this.candidates[j].X)
077:                 {
078:                     unique = false;
079:                     break;
080:                 }
081:             }
082: 
083:             if (unique)
084:             {
085:                 for (int k = 0; k < this.candidates.Count; k++)
086:                 {
087:                     if (k == i)
088:                         continue;
089: 
090:                     if (this.candidates[k].Y == this.candidates[i].Y)
091:                     {
092:                         unique = false;
093:                         break;
094:                     }
095:                 }
096: 
097:                 if (unique)
098:                     return this.candidates[i];
099:             }
100:         }
101: 
102:         return null;  // should never be reached
103:     }
104: 
105:     // contract with base class 'Object'
106:     public override String ToString()
107:     {
108:         StringBuilder sb = new StringBuilder();
109: 
110:         for (int i = 0; i < this.candidates.Count; i ++)
111:             sb.Append(this.candidates[i].ToString() + Environment.NewLine);
112: 
113:         return sb.ToString();
114:     }
115: }

Beispiel 6. Implementierung der Klasse VierNeun.


Die Menge aller Candidate-Objekte, die das Zahlenpuzzle lösen, erhalten wir mit folgendem Testrahmen:

VierNeun vn = new VierNeun();
vn.ComputeCandidates();
Console.WriteLine("Initial Candidates:      {0}", vn.Count);

// create list of constraints
List<IConstraint> constraints = new List<IConstraint>();
constraints.Add(new CheckVier());
constraints.Add(new CheckNeun());
constraints.Add(new CheckCorrelation());

for (int i = 0; i < constraints.Count; i++)
{
    Console.WriteLine("Processing constraint:   '{0}'",
        constraints[i].Name);
    vn.ApplyConstraint(constraints[i]);
    Console.WriteLine("-> Remaining candidates:  {0}", vn.Count);
}

Ausgabe:

1: Initial Candidates:      4624
2: Processing constraint:   'Constraint-VIER'
3: -> Remaining candidates:  2448
4: Processing constraint:   'Constraint-NEUN'
5: -> Remaining candidates:  180
6: Processing constraint:   'Constraint-CORRELATION'
7: -> Remaining candidates:  9

Bleibt noch offen, welches Candidate-Objekt das Zahlenpuzzle eineindeutig löst.

VierNeun vn = new VierNeun();
vn.ComputeCandidates();

// create list of constraints
List<IConstraint> constraints = new List<IConstraint>();
constraints.Add(new CheckVier());
constraints.Add(new CheckNeun());
constraints.Add(new CheckCorrelation());

// apply constraints
for (int i = 0; i < constraints.Count; i++)
    vn.ApplyConstraint(constraints[i]);

Candidate unique = vn.Unique();
Console.WriteLine("Unique Solution: {0}", unique);

Ausgabe:

Unique Solution: 79, 97 -> [6241, 9409]