Added unit tests

10 files changed, 652 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
index 8004ac7..ea2c9f4 100644
--- a/.gitignore
+++ b/.gitignore
@@ -8,3 +8,4 @@
 *~
 debian
 sudoku_generator
+testrunner*
diff --git a/HISTORY b/HISTORY
index e0e8a35..162d282 100644
--- a/HISTORY
+++ b/HISTORY
@@ -95,3 +95,4 @@ ____-__-__: Version 0.3.5
 - Added method Pos::interacts_with.
 - Removed compatibility to VDR < 1.6.0.
 - Converted documentation and source files to UTF-8.
+- Added unit tests.
diff --git a/Makefile b/Makefile
index 658a0ab..f380edb 100644
--- a/Makefile
+++ b/Makefile
@@ -111,6 +111,10 @@ libvdr-$(PLUGIN).so: $(OBJS)
 	$(CXX) $(CXXFLAGS) -shared $^ -o $@
 	@cp --remove-destination $@ $(LIBDIR)/$@.$(APIVERSION)
 
+.PHONY: tests
+tests:
+	@cd $@ && $(MAKE)
+
 dist: clean
 	@-rm -rf $(TMPDIR)/$(ARCHIVE)
 	@mkdir $(TMPDIR)/$(ARCHIVE)
@@ -126,3 +130,4 @@ clean:
 	@-rm -f $(DEPFILE) *.o *.so $(I18Npot) *.tgz core* *~
 	@-rm -rf srcdoc
 	@cd tools && $(MAKE) clean
+	@cd tests && $(MAKE) clean
diff --git a/README b/README
index 9137688..7e6ac33 100644
--- a/README
+++ b/README
@@ -27,6 +27,10 @@ Requirements:
 
 - VDR >= 1.3.47
 
+- (optionally) CxxTest for unit tests (tested with version 3.10.1)
+  http://cxxtest.tigris.org/
+  On Debian systems you could download the RPM file and install it with alien.
+
 
 Description:
 ------------
diff --git a/tests/Makefile b/tests/Makefile
new file mode 100644
index 0000000..112cc9e
--- /dev/null
+++ b/tests/Makefile
@@ -0,0 +1,52 @@
+#
+# Sudoku: A plug-in for the Video Disk Recorder
+#
+# Copyright (C) 2010, Thomas Günther <tom@toms-cafe.de>
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License along
+# with this program; if not, write to the Free Software Foundation, Inc.,
+# 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+
+PROGRAM = testrunner
+
+SRCS = ../puzzle.cpp ../generator.cpp ../solver.cpp ../backtrack.cpp \
+       ../history.cpp
+
+TESTGEN  ?= cxxtestgen.py
+CXX      ?= g++
+CXXFLAGS ?= -g -O2 -Wall -Woverloaded-virtual
+DEFINES  += -D_GNU_SOURCE
+
+### The main target:
+
+all: $(PROGRAM)
+	./$<
+
+### Dependencies:
+
+DEPFILE = .dependencies
+$(DEPFILE): Makefile
+	@$(CXX) -MM -MG $(SRCS) | sed -e "s/\(.*: .*\)/..\/\1/" > $@
+
+-include $(DEPFILE)
+
+### Targets:
+
+$(PROGRAM).cpp: test_*.h
+	$(TESTGEN) -o $@ --error-printer $^
+
+$(PROGRAM): $(PROGRAM).cpp $(SRCS:%.cpp=%.o)
+	$(CXX) $(CXXFLAGS) $(DEFINES) $(INCLUDES) -o $@ $^
+
+clean:
+	@-rm -f $(PROGRAM) $(PROGRAM).cpp $(SRCS:%.cpp=%.o) $(DEPFILE) core* *~
diff --git a/tests/test_backtrack.h b/tests/test_backtrack.h
new file mode 100644
index 0000000..2f9c646
--- /dev/null
+++ b/tests/test_backtrack.h
@@ -0,0 +1,104 @@
+/*
+ * Sudoku: A plug-in for the Video Disk Recorder
+ *
+ * Copyright (C) 2010, Thomas Günther <tom@toms-cafe.de>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+#include <cxxtest/TestSuite.h>
+#include "../backtrack.h"
+
+using namespace BackTrack;
+
+template<typename Type, unsigned int Size>
+  class Permutation : public Solution
+  {
+    Type (&list)[Size];
+  public:
+    Permutation(Type (&list)[Size]) : list(list) {}
+    virtual void set_first_at(unsigned int level) { list[level] = (Type)0; }
+    virtual void set_next_at(unsigned int level) { ++list[level]; }
+    virtual void reset_at(unsigned int level) {}
+    virtual bool is_last_at(unsigned int level) const
+    {
+      return list[level] >= (Type)Size-1;
+    }
+    virtual bool is_valid_at(int level) const
+    {
+      for (int idx = 0; idx < level; ++idx)
+        if (list[idx] == list[level])
+          return false;
+      return true;
+    }
+    virtual bool is_last_level(int level) const { return level >= int(Size)-1; }
+  };
+
+class Test_BackTrack : public CxxTest::TestSuite
+{
+public:
+  void test_PermutationBackTrack()
+  {
+    int list[3];
+    Permutation<int, 3> perm(list);
+    Algorithm algorithm(perm);
+    algorithm.find_next_solution();
+
+    bool first_permutation = algorithm.solution_is_valid();
+    TS_ASSERT(first_permutation);
+    TS_ASSERT_EQUALS(list[0], 0);
+    TS_ASSERT_EQUALS(list[1], 1);
+    TS_ASSERT_EQUALS(list[2], 2);
+    algorithm.find_next_solution();
+
+    bool second_permutation = algorithm.solution_is_valid();
+    TS_ASSERT(second_permutation);
+    TS_ASSERT_EQUALS(list[0], 0);
+    TS_ASSERT_EQUALS(list[1], 2);
+    TS_ASSERT_EQUALS(list[2], 1);
+    algorithm.find_next_solution();
+
+    bool third_permutation = algorithm.solution_is_valid();
+    TS_ASSERT(third_permutation);
+    TS_ASSERT_EQUALS(list[0], 1);
+    TS_ASSERT_EQUALS(list[1], 0);
+    TS_ASSERT_EQUALS(list[2], 2);
+    algorithm.find_next_solution();
+
+    bool fourth_permutation = algorithm.solution_is_valid();
+    TS_ASSERT(fourth_permutation);
+    TS_ASSERT_EQUALS(list[0], 1);
+    TS_ASSERT_EQUALS(list[1], 2);
+    TS_ASSERT_EQUALS(list[2], 0);
+    algorithm.find_next_solution();
+
+    bool fifth_permutation = algorithm.solution_is_valid();
+    TS_ASSERT(fifth_permutation);
+    TS_ASSERT_EQUALS(list[0], 2);
+    TS_ASSERT_EQUALS(list[1], 0);
+    TS_ASSERT_EQUALS(list[2], 1);
+    algorithm.find_next_solution();
+
+    bool sixth_permutation = algorithm.solution_is_valid();
+    TS_ASSERT(sixth_permutation);
+    TS_ASSERT_EQUALS(list[0], 2);
+    TS_ASSERT_EQUALS(list[1], 1);
+    TS_ASSERT_EQUALS(list[2], 0);
+    algorithm.find_next_solution();
+
+    bool too_many_permutations = algorithm.solution_is_valid();
+    TS_ASSERT(!too_many_permutations);
+  }
+};
diff --git a/tests/test_generator.h b/tests/test_generator.h
new file mode 100644
index 0000000..9e8a154
--- /dev/null
+++ b/tests/test_generator.h
@@ -0,0 +1,63 @@
+/*
+ * Sudoku: A plug-in for the Video Disk Recorder
+ *
+ * Copyright (C) 2010, Thomas Günther <tom@toms-cafe.de>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+#include <cxxtest/TestSuite.h>
+#include "../generator.h"
+#include "../solver.h"
+
+using namespace Sudoku;
+
+class Test_Generator : public CxxTest::TestSuite
+{
+public:
+  void test_GenerateSymmetricSudoku()
+  {
+    // Generate a random Sudoku with 36 symmetric givens.
+    Puzzle puzzle;
+    Generator generator(puzzle, 36);
+    generator.find_next_solution();
+    TS_ASSERT(generator.solution_is_valid());
+
+    // Solve the generated Sudoku.
+    Solver solver(puzzle);
+    solver.find_next_solution();
+    TS_ASSERT(solver.solution_is_valid());
+    solver.find_next_solution();
+    bool only_one_solution = !solver.solution_is_valid();
+    TS_ASSERT(only_one_solution);
+  }
+
+  void test_GenerateNonSymmetricSudoku()
+  {
+    // Generate a random Sudoku with 26 non-symmetric givens.
+    Puzzle puzzle;
+    Generator generator(puzzle, 26, false);
+    generator.find_next_solution();
+    TS_ASSERT(generator.solution_is_valid());
+
+    // Solve the generated Sudoku.
+    Solver solver(puzzle);
+    solver.find_next_solution();
+    TS_ASSERT(solver.solution_is_valid());
+    solver.find_next_solution();
+    bool only_one_solution = !solver.solution_is_valid();
+    TS_ASSERT(only_one_solution);
+  }
+};
diff --git a/tests/test_history.h b/tests/test_history.h
new file mode 100644
index 0000000..bd2f255
--- /dev/null
+++ b/tests/test_history.h
@@ -0,0 +1,115 @@
+/*
+ * Sudoku: A plug-in for the Video Disk Recorder
+ *
+ * Copyright (C) 2010, Thomas Günther <tom@toms-cafe.de>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+#include <cxxtest/TestSuite.h>
+#include "../history.h"
+#include "../puzzle.h"
+
+using namespace Sudoku;
+
+class Test_History : public CxxTest::TestSuite
+{
+public:
+  void test_HistoryEmpty()
+  {
+    History history;
+    TS_ASSERT(!history.movesExecuted());
+    TS_ASSERT(!history.movesToExecute());
+    history.backward();
+    TS_ASSERT(!history.movesExecuted());
+    TS_ASSERT(!history.movesToExecute());
+    history.forward();
+    TS_ASSERT(!history.movesExecuted());
+    TS_ASSERT(!history.movesToExecute());
+    history.reset();
+    TS_ASSERT(!history.movesExecuted());
+    TS_ASSERT(!history.movesToExecute());
+  }
+
+  void test_HistoryNull()
+  {
+    History history;
+    TS_ASSERT_EQUALS(history.current(), (Move*)0);
+    history.add(0);
+    TS_ASSERT(!history.movesExecuted());
+    TS_ASSERT(!history.movesToExecute());
+  }
+
+  void test_HistoryAdd()
+  {
+    History history;
+    PuzzleGame puzzle;
+
+    SetMove* move1 = new SetMove(puzzle, 1);
+    history.add(move1);
+    TS_ASSERT_EQUALS(history.current(), move1);
+    TS_ASSERT(history.movesExecuted());
+    TS_ASSERT(!history.movesToExecute());
+
+    SetMove* move2 = new SetMove(puzzle, 2);
+    history.add(move2);
+    TS_ASSERT_EQUALS(history.current(), move2);
+    TS_ASSERT(history.movesExecuted());
+    TS_ASSERT(!history.movesToExecute());
+
+    history.backward();
+    TS_ASSERT_EQUALS(history.current(), move1);
+    TS_ASSERT(history.movesExecuted());
+    TS_ASSERT(history.movesToExecute());
+
+    history.forward();
+    TS_ASSERT_EQUALS(history.current(), move2);
+    TS_ASSERT(history.movesExecuted());
+    TS_ASSERT(!history.movesToExecute());
+
+    history.backward();
+    TS_ASSERT_EQUALS(history.current(), move1);
+    TS_ASSERT(history.movesExecuted());
+    TS_ASSERT(history.movesToExecute());
+
+    SetMove* move3 = new SetMove(puzzle, 3);
+    history.add(move3);
+    TS_ASSERT_EQUALS(history.current(), move3);
+    TS_ASSERT(history.movesExecuted());
+    TS_ASSERT(!history.movesToExecute());
+
+    history.backward();
+    TS_ASSERT_EQUALS(history.current(), move1);
+    TS_ASSERT(history.movesExecuted());
+    TS_ASSERT(history.movesToExecute());
+
+    history.backward();
+    TS_ASSERT_EQUALS(history.current(), (Move*)0);
+    TS_ASSERT(!history.movesExecuted());
+    TS_ASSERT(history.movesToExecute());
+  }
+
+  void test_SetMove()
+  {
+    PuzzleGame puzzle;
+    SetMove move = SetMove(puzzle, 9);
+    Pos pos = puzzle.get_pos();
+    TS_ASSERT_EQUALS(puzzle.get(pos), 0u);
+    move.execute();
+    TS_ASSERT_EQUALS(puzzle.get(pos), 9u);
+    move.takeBack();
+    TS_ASSERT_EQUALS(puzzle.get(pos), 0u);
+  }
+};
diff --git a/tests/test_puzzle.h b/tests/test_puzzle.h
new file mode 100644
index 0000000..b28f0b9
--- /dev/null
+++ b/tests/test_puzzle.h
@@ -0,0 +1,184 @@
+/*
+ * Sudoku: A plug-in for the Video Disk Recorder
+ *
+ * Copyright (C) 2010, Thomas Günther <tom@toms-cafe.de>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+#include <cxxtest/TestSuite.h>
+#include "../puzzle.h"
+
+using namespace Sudoku;
+
+class Test_Puzzle : public CxxTest::TestSuite
+{
+public:
+  void test_Pos()
+  {
+    Pos pos;
+    TS_ASSERT_EQUALS(pos, Pos::first());
+    TS_ASSERT_EQUALS(pos, 0u);
+    TS_ASSERT_EQUALS(pos.col(), 0u);
+    TS_ASSERT_EQUALS(pos.row(), 0u);
+    TS_ASSERT_EQUALS(pos.reg(), 0u);
+    TS_ASSERT_EQUALS(pos, Pos(0, 0));
+
+    TS_ASSERT_EQUALS(pos.prev_col(), pos);
+    TS_ASSERT_EQUALS(pos.prev_row(), pos);
+
+    TS_ASSERT_EQUALS(pos.next(), Pos(1, 0));
+    TS_ASSERT_EQUALS(pos.next_col(), Pos(1, 0));
+    TS_ASSERT_EQUALS(pos.next_row(), Pos(0, 1));
+
+    pos = pos.symmetric();
+    TS_ASSERT_EQUALS(pos, Pos::last());
+    TS_ASSERT_EQUALS(pos, 80u);
+    TS_ASSERT_EQUALS(pos.col(), 8u);
+    TS_ASSERT_EQUALS(pos.row(), 8u);
+    TS_ASSERT_EQUALS(pos.reg(), 8u);
+    TS_ASSERT_EQUALS(pos, Pos(8, 8));
+
+    TS_ASSERT_EQUALS(pos.next(), Pos::last()+1);
+    TS_ASSERT_EQUALS(pos.next_col(), pos);
+    TS_ASSERT_EQUALS(pos.next_row(), pos);
+
+    TS_ASSERT_EQUALS(pos.prev_col(), Pos(7, 8));
+    TS_ASSERT_EQUALS(pos.prev_row(), Pos(8, 7));
+
+    pos = Pos(0, 4);
+    TS_ASSERT_EQUALS(pos.prev_col(), pos);
+    pos = Pos(4, 0);
+    TS_ASSERT_EQUALS(pos.prev_row(), pos);
+    pos = Pos(4, 8);
+    TS_ASSERT_EQUALS(pos.next_row(), pos);
+    pos = Pos(8, 4);
+    TS_ASSERT_EQUALS(pos.next_col(), pos);
+    TS_ASSERT_EQUALS(pos.next(), Pos(0, 5));
+
+    pos = Pos::center();
+    TS_ASSERT_EQUALS(pos, 40u);
+    TS_ASSERT_EQUALS(pos.col(), 4u);
+    TS_ASSERT_EQUALS(pos.row(), 4u);
+    TS_ASSERT_EQUALS(pos.reg(), 4u);
+    TS_ASSERT_EQUALS(pos, Pos(4, 4));
+
+    pos = pos.next().next_col().next_row();
+    TS_ASSERT_EQUALS(pos, Pos(6, 5));
+    TS_ASSERT_EQUALS(pos, 51u);
+    TS_ASSERT_EQUALS(pos.col(), 6u);
+    TS_ASSERT_EQUALS(pos.row(), 5u);
+    TS_ASSERT_EQUALS(pos.reg(), 5u);
+
+    pos = pos.prev_col().prev_row();
+    TS_ASSERT_EQUALS(pos, Pos(5, 4));
+
+    for (Pos p = Pos::first(); p <= Pos::last(); p = p.next())
+      if (p == pos)
+        { TS_ASSERT(!p.interacts_with(pos)); }
+      else if (p.col() == pos.col())
+        { TS_ASSERT(p.interacts_with(pos)); }
+      else if (p.row() == pos.row())
+        { TS_ASSERT(p.interacts_with(pos)); }
+      else if (p.reg() == pos.reg())
+        { TS_ASSERT(p.interacts_with(pos)); }
+      else
+        { TS_ASSERT(!p.interacts_with(pos)); }
+  }
+
+  void test_NumbersEmptyDump()
+  {
+    Numbers numbers;
+    const char dump[] = "_________+"
+                        "_________+"
+                        "_________+"
+                        "_________+"
+                        "_________+"
+                        "_________+"
+                        "_________+"
+                        "_________+"
+                        "_________";
+    TS_ASSERT_SAME_DATA(numbers.get_dump(), dump, sizeof(dump));
+  }
+
+  void test_NumbersConstruct()
+  {
+    const char dump[] = "________9+"
+                        "_______8_+"
+                        "______7__+"
+                        "_____6___+"
+                        "____5____+"
+                        "___4_____+"
+                        "__3______+"
+                        "_2_______+"
+                        "1________";
+    Numbers numbers(dump);
+    for (Pos p = Pos::first(); p <= Pos::last(); p = p.next())
+      if (p.col() == DIM - 1 - p.row())
+        { TS_ASSERT_EQUALS(numbers.get(p), p.col()+1); }
+      else
+        { TS_ASSERT_EQUALS(numbers.get(p), 0u); }
+    TS_ASSERT_SAME_DATA(numbers.get_dump(), dump, sizeof(dump));
+  }
+
+  void test_NumbersSetGet()
+  {
+    Numbers numbers;
+    numbers.set(Pos(0, 0), 1);
+    numbers.set(Pos(1, 1), 2);
+    numbers.set(Pos(2, 2), 3);
+    numbers.set(Pos(3, 3), 4);
+    numbers.set(Pos(4, 4), 5);
+    numbers.set(Pos(5, 5), 6);
+    numbers.set(Pos(6, 6), 7);
+    numbers.set(Pos(7, 7), 8);
+    numbers.set(Pos(8, 8), 9);
+    for (Pos p = Pos::first(); p <= Pos::last(); p = p.next())
+      if (p.col() == p.row())
+        { TS_ASSERT_EQUALS(numbers.get(p), p.col()+1); }
+      else
+        { TS_ASSERT_EQUALS(numbers.get(p), 0u); }
+  }
+
+  void test_PuzzleEmpty()
+  {
+    Puzzle puzzle;
+    for (Pos p = Pos::first(); p <= Pos::last(); p = p.next())
+    {
+      TS_ASSERT_EQUALS(puzzle.get(p), 0u);
+      TS_ASSERT(!puzzle.given(p));
+    }
+  }
+
+  void test_PuzzleNumbers()
+  {
+    const char dump[] = "________9+"
+                        "_______8_+"
+                        "______7__+"
+                        "_____6___+"
+                        "____5____+"
+                        "___4_____+"
+                        "__3______+"
+                        "_2_______+"
+                        "1________";
+    Numbers numbers(dump);
+    Puzzle puzzle(dump);
+    for (Pos p = Pos::first(); p <= Pos::last(); p = p.next())
+    {
+      TS_ASSERT_EQUALS(puzzle.get(p), numbers.get(p));
+      TS_ASSERT_EQUALS(puzzle.given(p), numbers.get(p) != 0u);
+    }
+  }
+};
diff --git a/tests/test_solver.h b/tests/test_solver.h
new file mode 100644
index 0000000..af066a4
--- /dev/null
+++ b/tests/test_solver.h
@@ -0,0 +1,123 @@
+/*
+ * Sudoku: A plug-in for the Video Disk Recorder
+ *
+ * Copyright (C) 2010, Thomas Günther <tom@toms-cafe.de>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+#include <cxxtest/TestSuite.h>
+#include "../solver.h"
+
+using namespace Sudoku;
+
+class Test_Solver : public CxxTest::TestSuite
+{
+public:
+  void test_SearchFirstSudoku()
+  {
+    Puzzle puzzle;
+    Solver solver(puzzle);
+    solver.find_next_solution();
+    TS_ASSERT(solver.solution_is_valid());
+    const char dump[] = "_________+"
+                        "_________+"
+                        "_________+"
+                        "_________+"
+                        "_________+"
+                        "_________+"
+                        "_________+"
+                        "_________+"
+                        "_________:"
+                        "123456789+"
+                        "456789123+"
+                        "789123456+"
+                        "231674895+"
+                        "875912364+"
+                        "694538217+"
+                        "317265948+"
+                        "542897631+"
+                        "968341572:"
+                        "_________+"
+                        "_________+"
+                        "_________+"
+                        "_________+"
+                        "_________+"
+                        "_________+"
+                        "_________+"
+                        "_________+"
+                        "_________";
+    TS_ASSERT_SAME_DATA(puzzle.get_dump(), dump, sizeof(dump));
+    solver.find_next_solution();
+    bool more_than_one_solution = solver.solution_is_valid();
+    TS_ASSERT(more_than_one_solution);
+  }
+
+  void test_SearchRandomSudoku()
+  {
+    Puzzle puzzle;
+    Solver solver(puzzle, true);
+    solver.find_next_solution();
+    TS_ASSERT(solver.solution_is_valid());
+  }
+
+  void test_SolveHardSudoku()
+  {
+    // Hardest Sudoku from sudokusolver.co.uk (nologic, score 80197, 77 guesses)
+    Puzzle puzzle("1____7_9_+"
+                  "_3__2___8+"
+                  "__96__5__+"
+                  "__53__9__+"
+                  "_1__8___2+"
+                  "6____4___+"
+                  "3______1_+"
+                  "_4______7+"
+                  "__7___3__");
+    Solver solver(puzzle);
+    solver.find_next_solution();
+    TS_ASSERT(solver.solution_is_valid());
+    const char dump[] = "1____7_9_+"
+                        "_3__2___8+"
+                        "__96__5__+"
+                        "__53__9__+"
+                        "_1__8___2+"
+                        "6____4___+"
+                        "3______1_+"
+                        "_4______7+"
+                        "__7___3__:"
+                        "162857493+"
+                        "534129678+"
+                        "789643521+"
+                        "475312986+"
+                        "913586742+"
+                        "628794135+"
+                        "356478219+"
+                        "241935867+"
+                        "897261354:"
+                        "_________+"
+                        "_________+"
+                        "_________+"
+                        "_________+"
+                        "_________+"
+                        "_________+"
+                        "_________+"
+                        "_________+"
+                        "_________";
+    TS_ASSERT_SAME_DATA(puzzle.get_dump(), dump, sizeof(dump));
+    solver.find_next_solution();
+    bool only_one_solution = !solver.solution_is_valid();
+    TS_ASSERT(only_one_solution);
+  }
+};