}
static bool dfs(const Move& lastMove) {    DEBUG0(spaces(state.moves()) << "dfs: moves =  "	   << state.moves() << " state = " << state);#ifdef DO_CACHING    IDAStarCacheState cacheState(state);    IDAStarCacheState* cachedState = cachedStates.find(cacheState);    if (cachedState != NULL) {	DEBUG0("found" << state << " in cache");	if (cachedState->minMovesFromStart <= state.moves())	    return false;	else if (cachedState->minMovesFromStart > state.moves())	    cachedState->minMovesFromStart = state.moves();	if (state.moves() + cachedState->minMovesLeft > maxMoves)	    return false;    }    if (cachedStates.size() < cachedStates.capacity() - 10#ifdef DO_STOCHASTIC_CACHING	&& double(rand()) / double(RAND_MAX) <= CACHE_INSERT_PROBABILITY#endif	)	cachedStates.insert(cacheState);#endif    if ((Statistics::statesExpanded & 0xfffff) == 0) {	cout << state << " / " << maxMoves << endl#ifdef DO_CACHING	     << " cached: " << cachedStates.size()	     << " / " << cachedStates.capacity()#endif#ifdef DO_PARTIAL	     << " cached: " << numBitsSet	     << " / " << maxBitsSet#endif	     << " moves = " << state.moves()	     << endl;	Statistics::print(cout);    }    // generate all moves...    ++Statistics::statesExpanded;    static const int MAX_BUCKET_SIZE = NUM_ATOMS * 4;    Move buckets[3][MAX_BUCKET_SIZE];    int bucketsize[3] = { };    for (int atomNr = 0; atomNr < NUM_ATOMS; ++atomNr) {	Pos startPos = state.atomPosition(atomNr);	for (int dirNo = 0; dirNo < 4; ++dirNo) {	    Dir dir = DIRS[dirNo];	    if (!mayMove[atomNr][dirNo])		continue;	    	    DEBUG0(spaces(moves) << "moving " << atomNr << " @ " << startPos		   << ' ' << dir);	    Pos pos;	    for (pos = startPos + dir; !state.isBlocking(pos); pos += dir) { }	    Pos newPos = pos - dir;	    if (newPos == startPos)		continue;	    	    ++Statistics::numChildren;	    DEBUG0(spaces(moves) << "moves to " << newPos);	    Move move(atomNr, startPos, newPos, dir);#ifdef DO_MOVE_PRUNING	    if (state.moves() > 0) {		if (atomNr == lastMove.atomNr() && dir == -lastMove.dir()) {		    ++Statistics::numPruned;		    continue;		}		if (atomNr < lastMove.atomNr()) {		    // this is only allowed if the two moves are not independent.		    if (!(between(lastMove.pos1(), lastMove.pos2(),				  lastMove.dir(), newPos)			  || newPos + dir == lastMove.pos2()			  || between(startPos, newPos, dir, lastMove.pos1())			  || startPos == lastMove.pos2() + lastMove.dir())) {			++Statistics::numPruned;			continue;		    }		}	    }#endif	    int oldMinMovesLeft = state.minMovesLeft();	    int bucketNr;	    state.apply(move);	    ++Statistics::statesGenerated;	    ++Statistics::statesGeneratedAtDepth[maxMoves];	    if (state.minMovesLeft() == 0) {		solution.push_front(move);	    		return true; // not true for all heuristics, but for this one	    }	    if (state.minTotalMoves() > maxMoves)		goto skip;#ifdef DO_PARTIAL	    // ugh... 64 bit modulo is dog slow on i386...	    uint64_t hash1 = newState.hash64_1() % stateBits.numBits();	    uint64_t hash2 = newState.hash64_2() % stateBits.numBits();	    DEBUG0(newState << " hashes to " << hash1 << " & " << hash2);	    int bitsSet = stateBits.isSet(hash1) + stateBits.isSet(hash2);	    if (bitsSet == 2) {		DEBUG0(" bits already set");		goto skip;	    }	    if (doAddBits) {		stateBits.set(hash1);		stateBits.set(hash2);		numBitsSet += 2 - bitsSet;		if (numBitsSet > maxBitsSet) {		    DEBUG1(" Bit hash table full");		    doAddBits = false;		}	    }#endif	    bucketNr = state.minMovesLeft() - oldMinMovesLeft + 1;	    if (bucketNr < 0 || bucketNr > 2) {		    cerr << "Impossible: old minMovesLeft = " << oldMinMovesLeft			 << ", new minMovesLeft = " << state.minMovesLeft() << endl;		    abort();			    }	    	    buckets[bucketNr][bucketsize[bucketNr]++] = move;	skip:	    state.undo(move, oldMinMovesLeft);	}    }    for (int bucketNr = 0; bucketNr < 3; ++bucketNr) {	for (int i = 0; i < bucketsize[bucketNr]; ++i) {	    int oldMinMovesLeft = state.minMovesLeft();	    const Move& move = buckets[bucketNr][i];	    //////////////////	    bool mayMoveBak[NUM_ATOMS][4];	    for (int i = 0; i < NUM_ATOMS; ++i)		for (int j = 0; j < 4; ++j)		    mayMoveBak[i][j] = mayMove[i][j];	    struct Undo {		Undo() {}		Undo(int natomNr, int ndirNr, bool nval)		    : atomNr(natomNr), dirNr(ndirNr), val(nval) { }		int atomNr;		int dirNr;		bool val;	    };//	    Undo undos[NUM_ATOMS + 8];//	    int numUndos = 0;//			       cout << "  Do: " << (num) << " " << (dir) \//				    << " -> " << (val) << endl; \////			       undos[numUndos++] = Undo(num, dir, mayMove[num][dir]); \	    #define CHANGE(num, dir, val) do { \			       mayMove[num][dir] = val; \			      } while (0)	    	    if (state.moves() > 0) {		if (move.atomNr() == lastMove.atomNr()) {		    for (int d = 0; d < 4; ++d)		    CHANGE(move.atomNr(), d, d != -move.dir());		    //for (int d = 0; d < 4; ++d)		    //CHANGE(move.atomNr(), d, true);		} else {		    //for (int d = 0; d < 4; ++d)		    //CHANGE(lastMove.atomNr(), d, false);		}	    }	    // wake up others	    int moveDirNo = noOfDir(move.dir());	    int mmoveDirNo = noOfOppositeDir(move.dir());	    Dir perpDir;	    int perpDirNr, mperpDirNr;	    if (move.dir() == UP || move.dir() == DOWN) {		perpDir = LEFT;		perpDirNr = 2;		mperpDirNr = 3;	    } else {		perpDir = UP;		perpDirNr = 0;		mperpDirNr = 1;	    }	    // case 1	    Pos pp;	    if (move.pos1() + move.dir() != move.pos2()) { // moved at least 2 fields		for (Pos p = move.pos1() + move.dir();		     p != move.pos2() - move.dir(); p += move.dir()) {		    if (state.isBlocking(p - perpDir)) {			for (pp = p + perpDir; !state.isBlocking(pp);			     pp += perpDir) { }			if (state.isAtom(pp))			    CHANGE(state.atomNr(pp), mperpDirNr, true);		    }		    if (state.isBlocking(p + perpDir)) {			Pos pp;			for (pp = p - perpDir; !state.isBlocking(pp);			     pp -= perpDir) { }			if (state.isAtom(pp))			    CHANGE(state.atomNr(pp), perpDirNr, true);		    }		}	    }	    // case 1 special case	    for (pp = move.pos1() - move.dir(); !state.isBlocking(pp);		 pp -= move.dir()) { }	    if (state.isAtom(pp))		CHANGE(state.atomNr(pp), moveDirNo, true);	    // case 2 & 3 	    for (pp = move.pos1() + perpDir; !state.isBlocking(pp);		 pp += perpDir) { }	    if (state.isAtom(pp))		CHANGE(state.atomNr(pp), mperpDirNr, true);	    for (pp = move.pos1() - perpDir; !state.isBlocking(pp);		 pp -= perpDir) { }	    if (state.isAtom(pp))		CHANGE(state.atomNr(pp), perpDirNr, true);	    // case 4	    if (state.isAtom(move.pos2() + move.dir()))		CHANGE(state.atomNr(move.pos2() + move.dir()), mmoveDirNo, true);	    //////////////////////	    state.apply(move, oldMinMovesLeft + bucketNr - 1);		    if (dfs(move)) {		solution.push_front(move);		return true;	    }	    state.undo(move, oldMinMovesLeft);	    /*	    for (int i = 0; i < numUndos; ++i) {		DEBUG0("Undo: " << undos[i].atomNr << " "		       << undos[i].dirNr << " -> "		       << undos[i].val);		mayMove[undos[i].atomNr][undos[i].dirNr] = undos[i].val;	    }	    */	    for (int i = 0; i < NUM_ATOMS; ++i)		for (int j = 0; j < 4; ++j)		    mayMove[i][j] = mayMoveBak[i][j];	    //for (int i = 0; i < NUM_ATOMS; ++i)	    //for (int j = 0; j < 4; ++j)	    //assert(mayMoveBak[i][j] == mayMove[i][j]);	}    }#ifdef DO_CACHING    if (cachedStates.size() < cachedStates.capacity() - 10#ifdef DO_STOCHASTIC_CACHING	&& double(rand()) / double(RAND_MAX)  <= CACHE_INSERT_PROBABILITY#endif	)	cacheState.minMovesLeft = (maxMoves + 1) - state.moves();	cachedStates.insert(cacheState);#endif    return false;}