test_backtrack.h

Go to the documentation of this file.
00001 /*
00002  * Sudoku: A plug-in for the Video Disk Recorder
00003  *
00004  * Copyright (C) 2010, Thomas G√ľnther <tom@toms-cafe.de>
00005  *
00006  * This program is free software; you can redistribute it and/or modify
00007  * it under the terms of the GNU General Public License as published by
00008  * the Free Software Foundation; either version 2 of the License, or
00009  * (at your option) any later version.
00010  *
00011  * This program is distributed in the hope that it will be useful,
00012  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00013  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014  * GNU General Public License for more details.
00015  *
00016  * You should have received a copy of the GNU General Public License along
00017  * with this program; if not, write to the Free Software Foundation, Inc.,
00018  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
00019  */
00020 
00021 #include <cxxtest/TestSuite.h>
00022 #include "../backtrack.h"
00023 
00024 using namespace BackTrack;
00025 
00026 template<typename Type, unsigned int Size>
00027   class Permutation : public Solution
00028   {
00029     Type (&list)[Size];
00030   public:
00031     Permutation(Type (&list)[Size]) : list(list) {}
00032     virtual void set_first_at(unsigned int level) { list[level] = (Type)0; }
00033     virtual void set_next_at(unsigned int level) { ++list[level]; }
00034     virtual void reset_at(unsigned int level) {}
00035     virtual bool is_last_at(unsigned int level) const
00036     {
00037       return list[level] >= (Type)Size-1;
00038     }
00039     virtual bool is_valid_at(int level) const
00040     {
00041       for (int idx = 0; idx < level; ++idx)
00042         if (list[idx] == list[level])
00043           return false;
00044       return true;
00045     }
00046     virtual bool is_last_level(int level) const { return level >= int(Size)-1; }
00047   };
00048 
00049 class Test_BackTrack : public CxxTest::TestSuite
00050 {
00051 public:
00052   void test_PermutationBackTrack()
00053   {
00054     int list[3];
00055     Permutation<int, 3> perm(list);
00056     Algorithm algorithm(perm);
00057     algorithm.find_next_solution();
00058 
00059     bool first_permutation = algorithm.solution_is_valid();
00060     TS_ASSERT(first_permutation);
00061     TS_ASSERT_EQUALS(list[0], 0);
00062     TS_ASSERT_EQUALS(list[1], 1);
00063     TS_ASSERT_EQUALS(list[2], 2);
00064     algorithm.find_next_solution();
00065 
00066     bool second_permutation = algorithm.solution_is_valid();
00067     TS_ASSERT(second_permutation);
00068     TS_ASSERT_EQUALS(list[0], 0);
00069     TS_ASSERT_EQUALS(list[1], 2);
00070     TS_ASSERT_EQUALS(list[2], 1);
00071     algorithm.find_next_solution();
00072 
00073     bool third_permutation = algorithm.solution_is_valid();
00074     TS_ASSERT(third_permutation);
00075     TS_ASSERT_EQUALS(list[0], 1);
00076     TS_ASSERT_EQUALS(list[1], 0);
00077     TS_ASSERT_EQUALS(list[2], 2);
00078     algorithm.find_next_solution();
00079 
00080     bool fourth_permutation = algorithm.solution_is_valid();
00081     TS_ASSERT(fourth_permutation);
00082     TS_ASSERT_EQUALS(list[0], 1);
00083     TS_ASSERT_EQUALS(list[1], 2);
00084     TS_ASSERT_EQUALS(list[2], 0);
00085     algorithm.find_next_solution();
00086 
00087     bool fifth_permutation = algorithm.solution_is_valid();
00088     TS_ASSERT(fifth_permutation);
00089     TS_ASSERT_EQUALS(list[0], 2);
00090     TS_ASSERT_EQUALS(list[1], 0);
00091     TS_ASSERT_EQUALS(list[2], 1);
00092     algorithm.find_next_solution();
00093 
00094     bool sixth_permutation = algorithm.solution_is_valid();
00095     TS_ASSERT(sixth_permutation);
00096     TS_ASSERT_EQUALS(list[0], 2);
00097     TS_ASSERT_EQUALS(list[1], 1);
00098     TS_ASSERT_EQUALS(list[2], 0);
00099     algorithm.find_next_solution();
00100 
00101     bool too_many_permutations = algorithm.solution_is_valid();
00102     TS_ASSERT(!too_many_permutations);
00103   }
00104 };
Generated on Mon Apr 5 17:01:07 2010 for VDR plugin 'Sudoku' by  doxygen 1.6.3