00001 #ifndef FCS_RANDOM_DFS_SOLVING_ALGORITHM_H
00002 #define FCS_RANDOM_DFS_SOLVING_ALGORITHM_H
00003
00011
00012 #include <stdlib.h>
00013 #include "FCSSoftDFSSolvingAlgorithm.h"
00014 #include "FCSRandom.h"
00015 #include "FCHelpingAlgorithms.h"
00016
00018 template <class SolvingAlgorithmType>
00019 class FCSRandomDFSSolvingAlgorithm : public FCSSoftDFSSolvingAlgorithm<SolvingAlgorithmType>
00020 {
00021 public:
00023 FCSRandomDFSSolvingAlgorithm(FCCommandLineArguments* CommandLine);
00024
00026 virtual ~FCSRandomDFSSolvingAlgorithm();
00027
00028 protected:
00030 FCSRandomDFSSolvingAlgorithm();
00031
00033 void InitFCSRandomDFSSolvingAlgorithm();
00034
00039 virtual FCSStateSolvingReturnCodes SolveOrResume(int Depth);
00040
00042 virtual void IncreaseDFSMaxDepth();
00043
00045 int* m_SoftDFSDerivedStatesRandomIndexesMaxSize;
00047 int** m_SoftDFSDerivedStatesRandomIndexes;
00048
00050 FCSRandom* m_RandomGenerator;
00051 };
00052
00053 template <class SolvingAlgorithmType>
00054 FCSRandomDFSSolvingAlgorithm<SolvingAlgorithmType>::FCSRandomDFSSolvingAlgorithm() : FCSSoftDFSSolvingAlgorithm<SolvingAlgorithmType>()
00055 {
00056 InitFCSRandomDFSSolvingAlgorithm();
00057 }
00058
00059 template <class SolvingAlgorithmType>
00060 void FCSRandomDFSSolvingAlgorithm<SolvingAlgorithmType>::InitFCSRandomDFSSolvingAlgorithm()
00061 {
00062 m_SoftDFSDerivedStatesRandomIndexesMaxSize = NULL;
00063 m_SoftDFSDerivedStatesRandomIndexes = NULL;
00064 m_RandomGenerator = NULL;
00065 }
00066
00067 template <class SolvingAlgorithmType>
00068 FCSRandomDFSSolvingAlgorithm<SolvingAlgorithmType>::FCSRandomDFSSolvingAlgorithm(FCCommandLineArguments* CommandLine) : FCSSoftDFSSolvingAlgorithm<SolvingAlgorithmType>(CommandLine)
00069 {
00070 InitFCSRandomDFSSolvingAlgorithm();
00071 m_RandomGenerator = new FCSRandom(CommandLine->GetSeed());
00072 }
00073
00074 template <class SolvingAlgorithmType>
00075 FCSRandomDFSSolvingAlgorithm<SolvingAlgorithmType>::~FCSRandomDFSSolvingAlgorithm()
00076 {
00077 int Depth;
00078
00079 for(Depth=0;Depth<m_NumberOfSolutionStates-1;Depth++)
00080 delete [] m_SoftDFSDerivedStatesRandomIndexes[Depth];
00081
00082 for(;Depth<m_DFSMaxDepth;Depth++)
00083 if (m_SoftDFSDerivedStatesLists[Depth].m_MaxNumberOfStates)
00084 delete [] m_SoftDFSDerivedStatesRandomIndexes[Depth];
00085
00086 delete [] m_SoftDFSDerivedStatesRandomIndexes;
00087 m_SoftDFSDerivedStatesRandomIndexes = NULL;
00088 delete [] m_SoftDFSDerivedStatesRandomIndexesMaxSize;
00089 m_SoftDFSDerivedStatesRandomIndexesMaxSize = NULL;
00090
00091 delete m_RandomGenerator;
00092 }
00093
00094 template <class SolvingAlgorithmType>
00095 FCSStateSolvingReturnCodes FCSRandomDFSSolvingAlgorithm<SolvingAlgorithmType>::SolveOrResume(int Depth)
00096 {
00097 FCSStateWithLocations *StateWithLocations,
00098 *RecursiveStateWithLocations;
00099
00100 int a, j;
00101 FCSStateSolvingReturnCodes Check;
00102
00103
00104 while (Depth >= 0)
00105 {
00106
00107 if (Depth+1 >= m_DFSMaxDepth)
00108 IncreaseDFSMaxDepth();
00109
00110
00111 if (m_SoftDFSCurrentStateIndexes[Depth] == m_SoftDFSDerivedStatesLists[Depth].m_NumberOfStates)
00112 {
00113 if (m_SoftDFSTestIndexes[Depth] >= m_TestsOrderNumber)
00114 {
00115
00116 Depth--;
00117 continue;
00118 }
00119
00120 m_SoftDFSDerivedStatesLists[Depth].m_NumberOfStates = 0;
00121 StateWithLocations = m_SolutionStates->Get(Depth, 0);
00122
00123
00124
00125 if (m_SoftDFSTestIndexes[Depth] == 0)
00126 {
00127 int NumberOfFreeStacks = 0,
00128 NumberOfFreecells = 0;
00129
00130 m_DebugDisplayInfo->Display(m_StateType, m_NumberOfCheckedStates, Depth, StateWithLocations,
00131 ((Depth == 0) ? 0 : m_SolutionStates->Get(Depth-1, 0)->m_VisitIterations), m_NumberOfStatesInCollection);
00132
00133
00134 for(a=0;a<m_NumberOfFreecells;a++)
00135 if (StateWithLocations->GetFreecellCardNumber(a) == 0)
00136 NumberOfFreecells++;
00137
00138
00139 for(a=0;a<m_NumberOfStacks;a++)
00140 if (StateWithLocations->GetStackLength(a) == 0)
00141 NumberOfFreeStacks++;
00142
00143
00144 if ((NumberOfFreeStacks == m_NumberOfStacks) && (NumberOfFreecells == m_NumberOfFreecells))
00145 {
00146 m_FinalState = StateWithLocations;
00147 return FCS_STATE_WAS_SOLVED;
00148 }
00149
00150
00151
00152 m_SoftDFSNumberOfFreecells[Depth] = NumberOfFreecells;
00153 m_SoftDFSNumberOfFreestacks[Depth] = NumberOfFreeStacks;
00154 }
00155
00156 if (m_SoftDFSTestIndexes[Depth] < m_TestsOrderNumber)
00157 {
00158 do
00159 {
00160 Check = RunTest(m_TestsOrder[m_SoftDFSTestIndexes[Depth]] & FCS_TEST_ORDER_NO_FLAGS_MASK,
00161 StateWithLocations, Depth,
00162 m_SoftDFSNumberOfFreestacks[Depth],
00163 m_SoftDFSNumberOfFreecells[Depth],
00164 &(m_SoftDFSDerivedStatesLists[Depth]));
00165
00166 if ((Check == FCS_STATE_BEGIN_SUSPEND_PROCESS) ||
00167 (Check == FCS_STATE_EXCEEDS_MAX_NUM_TIMES) ||
00168 (Check == FCS_STATE_SUSPEND_PROCESS))
00169 {
00170
00171 m_SoftDFSDerivedStatesLists[Depth].m_NumberOfStates = 0;
00172 m_SoftDFSCurrentStateIndexes[Depth] = 0;
00173 m_NumberOfSolutionStates = Depth+1;
00174 return FCS_STATE_SUSPEND_PROCESS;
00175 }
00176
00177
00178 m_SoftDFSTestIndexes[Depth]++;
00179 }
00180 while (
00181
00182 (m_SoftDFSTestIndexes[Depth] < m_TestsOrderNumber) &&
00183
00184 (m_TestsOrder[m_SoftDFSTestIndexes[Depth]] & FCS_TEST_ORDER_FLAG_RANDOM) &&
00185
00186 (! (m_TestsOrder[m_SoftDFSTestIndexes[Depth]] & FCS_TEST_ORDER_FLAG_START_RANDOM_GROUP)));
00187 }
00188
00189 int SwapSave,
00190 *RandomArray;
00191
00192 if (m_SoftDFSDerivedStatesLists[Depth].m_NumberOfStates >
00193 m_SoftDFSDerivedStatesRandomIndexesMaxSize[Depth])
00194 {
00195 Realloc<int>(&m_SoftDFSDerivedStatesRandomIndexes[Depth],
00196 m_SoftDFSDerivedStatesRandomIndexesMaxSize[Depth]+1,
00197 m_SoftDFSDerivedStatesLists[Depth].m_NumberOfStates);
00198
00199 m_SoftDFSDerivedStatesRandomIndexesMaxSize[Depth] =
00200 m_SoftDFSDerivedStatesLists[Depth].m_NumberOfStates;
00201 }
00202
00203 RandomArray = m_SoftDFSDerivedStatesRandomIndexes[Depth];
00204
00205 for (a=0;a<m_SoftDFSDerivedStatesLists[Depth].m_NumberOfStates;a++)
00206 RandomArray[a] = a;
00207
00208
00209
00210 if (m_TestsOrder[m_SoftDFSTestIndexes[Depth]-1] & FCS_TEST_ORDER_FLAG_RANDOM)
00211 {
00212 a = m_SoftDFSDerivedStatesLists[Depth].m_NumberOfStates-1;
00213 while (a > 0)
00214 {
00215 j = m_RandomGenerator->GetRandomNumber() % (a+1);
00216
00217 SwapSave = RandomArray[a];
00218 RandomArray[a] = RandomArray[j];
00219 RandomArray[j] = SwapSave;
00220 a--;
00221 }
00222 }
00223
00224
00225
00226 m_SoftDFSCurrentStateIndexes[Depth] = 0;
00227 }
00228
00229 while (m_SoftDFSCurrentStateIndexes[Depth] < m_SoftDFSDerivedStatesLists[Depth].m_NumberOfStates)
00230 {
00231 RecursiveStateWithLocations = m_SoftDFSDerivedStatesLists[Depth].m_States[
00232 m_SoftDFSDerivedStatesRandomIndexes[Depth][
00233 m_SoftDFSCurrentStateIndexes[Depth]]];
00234
00235 m_SoftDFSCurrentStateIndexes[Depth]++;
00236 if (!RecursiveStateWithLocations->m_Visited)
00237 {
00238 m_NumberOfCheckedStates++;
00239
00240 RecursiveStateWithLocations->m_Visited = FCS_VISITED_VISITED;
00241 RecursiveStateWithLocations->m_VisitIterations = m_NumberOfCheckedStates;
00242 m_SolutionStates->Set(Depth+1, RecursiveStateWithLocations);
00243
00244
00245
00246 Depth++;
00247 m_SoftDFSTestIndexes[Depth] = 0;
00248 m_SoftDFSCurrentStateIndexes[Depth] = 0;
00249 m_SoftDFSDerivedStatesLists[Depth].m_NumberOfStates = 0;
00250 break;
00251 }
00252 }
00253 }
00254
00255 m_NumberOfSolutionStates = 0;
00256
00257 return FCS_STATE_IS_NOT_SOLVEABLE;
00258 }
00259
00260
00261 template <class SolvingAlgorithmType>
00262 void FCSRandomDFSSolvingAlgorithm<SolvingAlgorithmType>::IncreaseDFSMaxDepth()
00263 {
00264 int NewDFSMaxDepth = m_DFSMaxDepth + INCREASE_DFS_MAX_DEPTH_BY;
00265
00266 Realloc<int*>(&m_SoftDFSDerivedStatesRandomIndexes, m_DFSMaxDepth, NewDFSMaxDepth);
00267 Realloc<int>(&m_SoftDFSDerivedStatesRandomIndexesMaxSize, m_DFSMaxDepth, NewDFSMaxDepth);
00268
00269 for(int d=m_DFSMaxDepth; d<NewDFSMaxDepth; d++)
00270 {
00271 m_SoftDFSDerivedStatesRandomIndexes[d] = NULL;
00272 m_SoftDFSDerivedStatesRandomIndexesMaxSize[d] = 0;
00273 }
00274
00275
00276 FCSSoftDFSSolvingAlgorithm<SolvingAlgorithmType>::IncreaseDFSMaxDepth();
00277 }
00278 #endif