Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveBreadthFirstSearch.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveBreadthFirstSearch.cs	(revision 11690)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveBreadthFirstSearch.cs	(revision 11690)
@@ -0,0 +1,65 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.GrammaticalOptimization {
+  public class ExhaustiveBreadthFirstSearch {
+    public event Action<string, double> FoundNewBestSolution;
+    public event Action<string, double> SolutionEvaluated;
+
+    private readonly int maxLen;
+    private readonly Queue<string> bfsQueue = new Queue<string>();
+
+    public ExhaustiveBreadthFirstSearch(int maxLen) {
+      this.maxLen = maxLen;      
+    }
+
+    public void Run(IProblem problem, int maxIterations) {
+      double bestQuality = double.MinValue;
+      bfsQueue.Enqueue(problem.Grammar.SentenceSymbol.ToString());
+      var sentences = GenerateLanguage(problem.Grammar);
+      var sentenceEnumerator = sentences.GetEnumerator();
+      for (int i = 0; sentenceEnumerator.MoveNext() && i < maxIterations; i++) {
+        var sentence = sentenceEnumerator.Current;
+        var quality = problem.Evaluate(sentence);
+        RaiseSolutionEvaluated(sentence, quality);
+
+        if (quality > bestQuality) {
+          bestQuality = quality;
+          RaiseFoundNewBestSolution(sentence, quality);
+        }
+      }
+    }
+
+    // create sentences lazily
+    private IEnumerable<string> GenerateLanguage(IGrammar grammar) {
+      while (bfsQueue.Any()) {
+        var phrase = bfsQueue.Dequeue();
+
+        var nt = phrase.First(grammar.IsNonTerminal);
+        var ntIdx = phrase.IndexOf(nt); // TODO perf
+        var alts = grammar.GetAlternatives(nt);
+        foreach (var alt in alts) {
+          var newPhrase = phrase.Remove(ntIdx, 1).Insert(ntIdx, alt);
+          if (newPhrase.All(grammar.IsTerminal)) {
+            yield return newPhrase;
+          } else if (grammar.MinPhraseLength(newPhrase) <= maxLen) {
+            bfsQueue.Enqueue(newPhrase);
+          }
+        }
+      }
+    }
+
+
+    private void RaiseSolutionEvaluated(string sentence, double quality) {
+      var handler = SolutionEvaluated;
+      if (handler != null) handler(sentence, quality);
+    }
+    private void RaiseFoundNewBestSolution(string sentence, double quality) {
+      var handler = FoundNewBestSolution;
+      if (handler != null) handler(sentence, quality);
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveDepthFirstSearch.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveDepthFirstSearch.cs	(revision 11690)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveDepthFirstSearch.cs	(revision 11690)
@@ -0,0 +1,65 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.GrammaticalOptimization {
+  public class ExhaustiveDepthFirstSearch {
+    public event Action<string, double> FoundNewBestSolution;
+    public event Action<string, double> SolutionEvaluated;
+
+    private readonly int maxLen;
+    private readonly Stack<string> stack = new Stack<string>();
+
+    public ExhaustiveDepthFirstSearch(int maxLen) {
+      this.maxLen = maxLen;      
+    }
+
+    public void Run(IProblem problem, int maxIterations) {
+      double bestQuality = double.MinValue;
+      stack.Push(problem.Grammar.SentenceSymbol.ToString());
+      var sentences = GenerateLanguage(problem.Grammar);
+      var sentenceEnumerator = sentences.GetEnumerator();
+      for (int i = 0; sentenceEnumerator.MoveNext() && i < maxIterations; i++) {
+        var sentence = sentenceEnumerator.Current;
+        var quality = problem.Evaluate(sentence);
+        RaiseSolutionEvaluated(sentence, quality);
+
+        if (quality > bestQuality) {
+          bestQuality = quality;
+          RaiseFoundNewBestSolution(sentence, quality);
+        }
+      }
+    }
+
+    // create sentences lazily
+    private IEnumerable<string> GenerateLanguage(IGrammar grammar) {
+      while (stack.Any()) {
+        var phrase = stack.Pop();
+
+        var nt = phrase.First(grammar.IsNonTerminal);
+        var ntIdx = phrase.IndexOf(nt); // TODO perf
+        var alts = grammar.GetAlternatives(nt);
+        foreach (var alt in alts) {
+          var newPhrase = phrase.Remove(ntIdx, 1).Insert(ntIdx, alt);
+          if (newPhrase.All(grammar.IsTerminal)) {
+            yield return newPhrase;
+          } else if (grammar.MinPhraseLength(newPhrase) <= maxLen) {
+            stack.Push(newPhrase);
+          }
+        }
+      }
+    }
+
+
+    private void RaiseSolutionEvaluated(string sentence, double quality) {
+      var handler = SolutionEvaluated;
+      if (handler != null) handler(sentence, quality);
+    }
+    private void RaiseFoundNewBestSolution(string sentence, double quality) {
+      var handler = FoundNewBestSolution;
+      if (handler != null) handler(sentence, quality);
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization.csproj	(revision 11689)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization.csproj	(revision 11690)
@@ -43,4 +43,6 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="ExhaustiveDepthFirstSearch.cs" />
+    <Compile Include="ExhaustiveBreadthFirstSearch.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
     <Compile Include="RandomSearch.cs" />
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/RandomSearch.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/RandomSearch.cs	(revision 11689)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/RandomSearch.cs	(revision 11690)
@@ -1,3 +1,4 @@
 ﻿using System;
+using System;
 using System.Collections.Generic;
 using System.Linq;
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs	(revision 11689)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs	(revision 11690)
@@ -10,5 +10,5 @@
   class Program {
     static void Main(string[] args) {
-      int maxIterations = 100000;
+      int maxIterations = 10000000;
       int iterations = 0;
       var sw = new Stopwatch();
@@ -16,5 +16,5 @@
       string bestSentence = "";
 
-      var rs = new RandomSearch(100);
+      var rs = new ExhaustiveDepthFirstSearch(17);
 
       rs.FoundNewBestSolution += (sentence, quality) => {
@@ -25,5 +25,5 @@
       rs.SolutionEvaluated += (sentence, quality) => {
         iterations++;
-        if (iterations % 1000 == 0) {
+        if (iterations % 10000 == 0) {
           Console.WriteLine("{0,10} {1,10:F5} {2,10:F5} {3}", iterations, bestQuality, quality, sentence);
         }
