DFS.java

// square 1 2  rectangle  5  rectangle 7 8  fringe -1 untouched 0
//        3 4             6

package szte.mi.tiles;


public class DFSTreeTiles extends AbstractTiles {

// ------------------------------------------------------------------

/** Calls super constructor. */
public DFSTreeTiles(int x, int y) { super(x,y); }

// ------------------------------------------------------------------
/* az szte.mi.tiles.DFSTreeTiles
osztály, amely megvalósít egy naív mélységi bejárást. Ez a megoldás nem üti meg az elégséges
szintet. */

@Override
public boolean getTiling() {
	
	int i=0, j=0;
	int cnt=0;
	
	// we search for a possible next move
search:
	for(i=0; i < tiles.length; ++i)
	for(j=0; j < tiles[i].length; ++j)
	{
		if(tiles[i][j] != -1) continue;
		
		cnt++;
		for(int t=1; t <= DFSTreeTiles.TYPES; ++t)
			if(possible(i,j,t)) break search;
	}
	
	if(i<tiles.length) // there are possible moves
	{
		for(int t=1; t <= DFSTreeTiles.TYPES; ++t)
		{
			if(possible(i,j,t))
			{
				// this is ugly but memory management is our
				// smaller problem
				DFSTreeTiles tclone = (DFSTreeTiles)this.clone();
				tclone.setTile(i,j,t);
				if( tclone.getTiling() ) // clone contains solution
				{
					this.copyTiles(tclone);
					return true;
				}
			}
		}
	}
	else if(cnt==0) // the tiling is complete
	{
		//System.err.println(this);
		return true;
	}
	
	// otherwise no luck here, stepping back
	return false;
}

}