import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
import java.io.*;

public class EternityII
{
    public static void main(String... args) throws IOException
    {
        for (int id = 0; id < 1; id++)
        {
            Solver solver = new Solver(id, true, 2, "A6x6With1Hint.txt", "sol1_11.txt");
            solver.solve();
            solver.storeNumSolutions();
            solver.printStats();

			/*            solver = new Solver(id, true, 0, "tiles2_11_5.17", "sol2_11.txt");
            solver.solve();
            solver.storeNumSolutions();
            solver.printStats();
            solver = new Solver(id, true, 0, "tiles3_11_5.17", "sol3_11.txt");

            solver.solve();
            solver.storeNumSolutions();
            solver.printStats();
            solver = new Solver(id, true, 0, "tiles4_11_5.17", "sol4_11.txt");

            solver.solve();
            solver.storeNumSolutions();
            solver.printStats();
            solver = new Solver(id, true, 0, "tiles5_11_5.17", "sol5.txt");

            solver.solve();
            solver.storeNumSolutions();
            solver.printStats();


            solver = new Solver(id, true, 0, "tiles1_12_5.17", "sol1_l2.txt");

            solver.solve();
            solver.storeNumSolutions();
            solver.printStats();
            solver = new Solver(id, true, 0, "tiles2_12_5.17", "sol2_l2.txt");

            solver.solve();
            solver.storeNumSolutions();
            solver.printStats();
            solver = new Solver(id, true, 0, "tiles3_12_5.17", "sol3_12.txt");

            solver.solve();
            solver.storeNumSolutions();
            solver.printStats();
            solver = new Solver(id, true, 0, "tiles5_12_5.17", "sol5_12.txt");

            solver.solve();
            solver.storeNumSolutions();
            solver.printStats();

            solver = new Solver(id, true, 5, "tiles2_13_5.17_9hints_1", "sol13_9_15.txt");
            solver.solve();
            solver.storeNumSolutions();
            solver.printStats();

            solver = new Solver(id, true, 5, "tiles2_13_5.17_9hints_2", "sol13_9_25.txt");
            solver.solve();
            solver.storeNumSolutions();
            solver.printStats();

            solver = new Solver(id, true, 7, "tiles_12_5.17.txt_hints", "sol12_hints.txt");

            solver.solve();
            solver.storeNumSolutions();
            solver.printStats();

            solver =  new Solver(id, true, 4, "tiles1_13_5.17_manyhints", "sol1_13_manyhints.txt");

            solver.solve();
            solver.storeNumSolutions();
            solver.printStats(); */
        }
    }
}

final class Solver {

    // defines
    public static boolean STATS = false;
    public static boolean STOP_AFTER_FIRST_CORNER_PIECE = false;
    public static boolean DUMP_SOLUTION_FOUND = true;
    public static boolean DUMP_MIN_DEPTH = true;

    public static final int NORMAL = 0;
    public static final int BORDER = 1;
    public static final int CORNER = 2;
    public static final int HINT = 3;

    public static final int TO_RIGHT_BOTTOM = 0;
    public static final int TO_LEFT = 1;
    public static final int TO_TOP = 2;
    public static final int TO_ALL = 3;

    public static final int CHECK_ALL = 0;
    public static final int CHECK_LT = 1;
    public static final int CHECK_TR = 2;
    public static final int CHECK_BL = 3;
    public static final int CHECK_LTB = 4;
    public static final int CHECK_LTR = 5;
    public static final int CHECK_TRB = 6;
    public static final int CHECK_RBL = 7;

    private static long _startTime;

    int _solverId;
	int _sizeX;
	int _sizeY;
	int _numEdgeTypes;
	int _numPieces;
	int _numEdges;
	boolean _useHints;
	int[][] _hintAdjustment;

	long  _numPiecesPlaced;

	//CHECK_RBL
	List<PieceRotation> _allPieceRotations;
	List<PieceRotation>[][] _pieceMatchesLT;
	List<PieceRotation>[][] _pieceMatchesTR;
	List<PieceRotation>[][] _pieceMatchesBL;
	List<PieceRotation>[][][] _pieceMatchesLTB;
	List<PieceRotation>[][][] _pieceMatchesLTR;
	List<PieceRotation>[][][] _pieceMatchesTRB;
	List<PieceRotation>[][][] _pieceMatchesRBL;
	List<PieceRotation>[][][][] _pieceMatches;

    List<HintPiece> _hintPieces;
	FileWriter _boardFile;
	IntegerRef _boardEdges[];
	int _numSolutions;
	PieceLocation[] _rowScanVector;
	String _piecesFileName;
	int _maxDepth;

    private List<PieceLocation> _hintStrategy;

//#ifdef STATS
	int[] _nodeCounts;
	int[] _xPlaced;
	int[] _yPlaced;
	int[][] _xyCount;
//#endif

    final static class PieceLocation {

        private final IntegerRef top;
        private final IntegerRef right;
        private final IntegerRef bottom;
        private final IntegerRef left;
        public boolean isUsed;
        public int type;
        public int check;
        public int direction;
        public int pos;

        PieceLocation(IntegerRef theTop, IntegerRef theRight, IntegerRef theBottom,
                IntegerRef theLeft, int thePos) {
            top = theTop;
            right = theRight;
            bottom = theBottom;
            left = theLeft;
            pos = thePos;
            type = NORMAL;
            check = CHECK_LT;
            direction = TO_RIGHT_BOTTOM;
            isUsed = false;
        }

        public int top() { return top.getValue(); }
        public int right() { return right.getValue(); }
        public int bottom() { return bottom.getValue(); }
        public int left() { return left.getValue(); }

        public void setTop(int i) { top.setValue(i); }
        public void setRight(int i) { right.setValue(i); }
        public void setBottom(int i) {  bottom.setValue(i); }
        public void setLeft(int i) { left.setValue(i); }
    }

    final static class PieceRotation {

        public int top;
        public int right;
        public int bottom;
        public int left;
        private BooleanRef isUsed;
        public int type;

        PieceRotation(int theTop, int theRight, int theBottom, int theLeft, BooleanRef theIsUsed) {
            top = theTop;
            right = theRight;
            bottom = theBottom;
            left = theLeft;
            isUsed = theIsUsed;
            type = NORMAL;
            if (top == 1 || right == 1 || bottom == 1 || left == 1)
                type = BORDER;
            if ( (top == 1 && right == 1) || (right == 1 && bottom == 1) ||
                    (bottom == 1 && left == 1) || (left == 1 && top == 1) )
                type = CORNER;
        }

        public boolean isUsed() { return isUsed.getValue(); }
        public void setUsed(boolean b) {  isUsed.setValue(b); }
    }

    final static class HintPiece {

        final int posX;
        final int posY;
        final int id;
        final int rotation;

        HintPiece(int thePosX, int thePosY, int theId, int theRotation) {
            posX = thePosX;
            posY = thePosY;
            id = theId;
            rotation = theRotation;
        }
    }

    static void setStartTime() {
        _startTime = System.currentTimeMillis();
    }

    static long usedTime() {
        return  System.currentTimeMillis() - _startTime;
    }

    static long usedMsecs() {
        return usedTime();
    }

    void shuffleVector(List<PieceRotation> pieces) {
        Collections.shuffle(pieces, new Random());
	}

	List<PieceRotation> getMatches(PieceLocation solutionPiece) {
		return _pieceMatches[solutionPiece.left.getValue()][solutionPiece.top.getValue()][solutionPiece.right.getValue()][solutionPiece.bottom.getValue()];
	}

	List<PieceRotation> getMatchesFast(PieceLocation solutionPiece) {
		switch (solutionPiece.check) {
			case CHECK_LT: {
				return _pieceMatchesLT[solutionPiece.left.getValue()][solutionPiece.top.getValue()];
			}
			case CHECK_TR: {
				return _pieceMatchesTR[solutionPiece.top.getValue()][solutionPiece.right.getValue()];
			}
			case CHECK_BL: {
				return _pieceMatchesBL[solutionPiece.bottom.getValue()][solutionPiece.left.getValue()];
			}
			case CHECK_LTB: {
				return _pieceMatchesLTB[solutionPiece.left.getValue()][solutionPiece.top.getValue()][solutionPiece.bottom.getValue()];
			}
			case CHECK_LTR: {
				return _pieceMatchesLTR[solutionPiece.left.getValue()][solutionPiece.top.getValue()][solutionPiece.right.getValue()];
			}
			case CHECK_TRB: {
				return _pieceMatchesTRB[solutionPiece.top.getValue()][solutionPiece.right.getValue()][solutionPiece.bottom.getValue()];
			}
			case CHECK_RBL: {
				return _pieceMatchesRBL[solutionPiece.right.getValue()][solutionPiece.bottom.getValue()][solutionPiece.left.getValue()];
			}
			case CHECK_ALL: {
				return _pieceMatches[solutionPiece.left.getValue()][solutionPiece.top.getValue()][solutionPiece.right.getValue()][solutionPiece.bottom.getValue()];
			}
		}
		return null;
	}

	int getMatchCount(PieceLocation solutionPiece) {
		return getMatches(solutionPiece).size();
	}

	int getMatchCountFast(PieceLocation solutionPiece) {
		return getMatchesFast(solutionPiece).size();
	}

	public Solver(int solverId, boolean useHints, int numRotations,
			String pieceFileName, String solutionFileName) throws IOException
    {
		_solverId = solverId;
		_sizeX = 0;
		_sizeY = 0;
		_numSolutions = 0;
		_piecesFileName = pieceFileName;
		_boardFile= new FileWriter(solutionFileName);
		_useHints = useHints;
		_numPiecesPlaced = 0;
		readPieceFile(numRotations);
	}

	void storeBoard() throws IOException
    {
		int numEdgesBoard = (_sizeX+1)*(_sizeY)+ (_sizeX)*(_sizeY+1);
		int i;
		int edgePos = 0;
        _boardFile.write( String.format("\nSolution %d:\n", _numSolutions) );
		while (edgePos<numEdgesBoard) {
			_boardFile.write("\n");
			_boardFile.write("  ");
			for (i=0; i<_sizeY; i++) {
				_boardFile.write(" |");
				if (_boardEdges[i+edgePos].getValue()<=0)
					_boardFile.write("  | ");
				else {
					if (_boardEdges[i+edgePos].getValue()<=10)
						_boardFile.write("0");
					_boardFile.write( String.format("%d| ", _boardEdges[i+edgePos].getValue() - 1) );
				}
			}
			_boardFile.write("\n");
			edgePos+=_sizeY;
			if (edgePos>=numEdgesBoard)
				break;
			for (i=0; i<_sizeY+1; i++) {
				_boardFile.write("|");
				if (_boardEdges[i+edgePos].getValue()<=0)
					_boardFile.write("  |  ");
				else {
					if (_boardEdges[i+edgePos].getValue()<=10)
						_boardFile.write("0");
					_boardFile.write( String.format("%d|  ", _boardEdges[i+edgePos].getValue() - 1) );
				}
			}
			edgePos+=_sizeY+1;
		}
		storeStats();
        _boardFile.flush();
	}

	void storeStats() throws IOException
    {
        if( STATS ) {
            _boardFile.write("\nNodeCounts:\n");
            for (int d = 1; d <= _numPieces; d++) {
                _boardFile.write(String.format("\n%3d %9d x=%d y=%d", d, _nodeCounts[d], _xPlaced[d], _yPlaced[d]));
            }
            _boardFile.write("\n\nxyNodeCounts:\n");
            _boardFile.write("\nY=   ");
            for (int y = 0; y < _sizeY; y++) {
                _boardFile.write(String.format("%12d", y));
            }
            for (int x = 0; x < _sizeX; x++) {
                _boardFile.write(String.format("\nX=%2d ", x));
                for (int y = 0; y < _sizeY; y++) {
                    _boardFile.write(String.format("%12d", _xyCount[x][y]));
                }
            }
            _boardFile.write("\n");
        }
	}

	void storeStrategy(List<PieceLocation> scanVector)
    {
        try
        {
            _boardFile.write("\nStrategy:\n");
            for (int p = 0; p < _numPieces; p++) {
                PieceLocation piece = scanVector.get(p);
                _boardFile.write(String.format("\n %d  x=%d y=%d", p+1, piece.pos / _sizeY, piece.pos % _sizeY));
            }
        }
        catch(IOException ex)
        {
            throw new RuntimeException(ex);
        }
    }

	void storeNumSolutions() throws IOException
    {
		_boardFile.write(String.format("\n number of solutions: %d\n", _numSolutions));
		storeStats();
		_boardFile.flush();
	}

	void printStats() {
		System.out.print(String.format("\nSolver %d -%s- Time: %d msec Solutions: %d",
				_solverId, _piecesFileName, usedMsecs(), _numSolutions) );
		System.out.print(String.format("\n Number of placements : %d", _numPiecesPlaced) );
		System.out.print(String.format("\n Millions placements per sec: %f", ((double) (_numPiecesPlaced
				/ (usedMsecs()+1)) / 1000)));
		System.out.flush();
	}

	int initHintFactor(int x, int y) {
		return x+y;
	}

	@SuppressWarnings({"unchecked"})
    void createArrays() {
		_allPieceRotations = new ArrayList<PieceRotation>();
		_pieceMatches = new ArrayList[_numEdgeTypes][_numEdgeTypes][_numEdgeTypes][_numEdgeTypes];
		_pieceMatchesLT = new ArrayList[_numEdgeTypes][_numEdgeTypes];
		_pieceMatchesTR = new ArrayList[_numEdgeTypes][_numEdgeTypes];
		_pieceMatchesBL = new ArrayList[_numEdgeTypes][_numEdgeTypes];
		_pieceMatchesLTR = new ArrayList[_numEdgeTypes][_numEdgeTypes][_numEdgeTypes];
		_pieceMatchesLTB = new ArrayList[_numEdgeTypes][_numEdgeTypes][_numEdgeTypes];
		_pieceMatchesTRB = new ArrayList[_numEdgeTypes][_numEdgeTypes][_numEdgeTypes];
		_pieceMatchesRBL = new ArrayList[_numEdgeTypes][_numEdgeTypes][_numEdgeTypes];
		_hintAdjustment = new int[_sizeX][_sizeY];
		for (int i=0; i < _numEdgeTypes; i++) {
			for (int j=0; j<_numEdgeTypes; j++) {
				_pieceMatchesLT[i][j] = new ArrayList<PieceRotation>();
				_pieceMatchesTR[i][j] = new ArrayList<PieceRotation>();
				_pieceMatchesBL[i][j] = new ArrayList<PieceRotation>();
				for (int k=0; k<_numEdgeTypes; k++) {
					_pieceMatchesLTR[i][j][k] = new ArrayList<PieceRotation>();
					_pieceMatchesLTB[i][j][k] = new ArrayList<PieceRotation>();
					_pieceMatchesTRB[i][j][k] = new ArrayList<PieceRotation>();
					_pieceMatchesRBL[i][j][k] = new ArrayList<PieceRotation>();
					for (int l=0; l<_numEdgeTypes; l++) {
						_pieceMatches[i][j][k][l]= new ArrayList<PieceRotation>();
					}
				}
			}
		}
		int x;
		for (x = 0; x < _sizeX; x++) {
			for (int y = 0; y < _sizeY; y++) {
				_hintAdjustment[x][y] = initHintFactor(x,y);
			}
		}
if( STATS ) {
		_nodeCounts = new int[_numPieces+1];
		_xPlaced = new int[_numPieces+1];
		_yPlaced = new int[_numPieces+1];
		for (int d = 0; d <= _numPieces; d++) {
			_nodeCounts[d] = 0;
			_xPlaced[d] = 0;
			_xPlaced[d] = 0;
		}
		_xyCount = new int[_sizeX][_sizeY];
		for (x = 0; x < _sizeX; x++) {
			for (int y = 0; y < _sizeY; y++) {
				_xyCount[x][y] = 0;
			}
		}
}
    }

	void computePieceMatches() {
		for (int i = 0; i < _allPieceRotations.size(); i++) {
			PieceRotation p = _allPieceRotations.get(i);
			// eliminate symmetries
			boolean symmetric = false;
			for (int j = 1; j <= 3 && i-j >= 0; j++) {
				PieceRotation p2 = _allPieceRotations.get(i-j);
				if (p.left == p2.left && p.top == p2.top &&
					p.right == p2.right && p.bottom == p2.bottom) {
					symmetric = true;
					break;
				}
			}
			if (!symmetric) {
				_pieceMatches[p.left][p.top][p.right][p.bottom].add(p);
				_pieceMatches[0][p.top][p.right][p.bottom].add(p);
				_pieceMatches[p.left][0][p.right][p.bottom].add(p);
				_pieceMatches[p.left][p.top][0][p.bottom].add(p);
				_pieceMatches[p.left][p.top][p.right][0].add(p);
				_pieceMatches[0][0][p.right][p.bottom].add(p);
				_pieceMatches[0][p.top][0][p.bottom].add(p);
				_pieceMatches[0][p.top][p.right][0].add(p);
				_pieceMatches[p.left][0][0][p.bottom].add(p);
				_pieceMatches[p.left][0][p.right][0].add(p);
				_pieceMatches[p.left][p.top][0][0].add(p);
				_pieceMatches[0][0][0][p.bottom].add(p);
				_pieceMatches[0][0][p.right][0].add(p);
				_pieceMatches[0][p.top][0][0].add(p);
				_pieceMatches[p.left][0][0][0].add(p);
				_pieceMatches[0][0][0][0].add(p);

				if (p.type != HINT) {
					if (p.right > 1 && p.bottom > 1)
						_pieceMatchesLT[p.left][p.top].add(p);
					if (p.bottom > 1 && p.left > 1)
						_pieceMatchesTR[p.top][p.right].add(p);
					if (p.top > 1 && p.right > 1)
						_pieceMatchesBL[p.bottom][p.left].add(p);
					if (p.bottom > 1)
						_pieceMatchesLTR[p.left][p.top][p.right].add(p);
					if (p.right > 1)
						_pieceMatchesLTB[p.left][p.top][p.bottom].add(p);
					if (p.left > 1)
						_pieceMatchesTRB[p.top][p.right][p.bottom].add(p);
					if (p.top > 1)
						_pieceMatchesRBL[p.right][p.bottom][p.left].add(p);
				}
			}
		}
	}

	void readPieceFile(int numRotations) throws IOException
    {
		LineNumberReader f = new LineNumberReader(new FileReader(_piecesFileName));

			List<Integer> pieces = new ArrayList<Integer>();

            String line = f.readLine();
            while( line != null ) {
				String[] desc = line.split(" ");
                for( String i : desc ) {
                    if( !i.trim().equals("") )
                        pieces.add(new Integer(i));
                }
                line = f.readLine();
            }
			f.close();
			int[] pieceArr = new int[pieces.size()];
			int i = 0;
            for( Integer ip : pieces )
                pieceArr[i++] = ip;
            readPieces(pieceArr, numRotations);
	}

	void readEdges(/*int[] pieces, IntegerRef pos*/) {
		_numPieces = _sizeX*_sizeY;
		_numEdges = (_sizeX+1)*(_sizeY)+ (_sizeX)*(_sizeY+1);
		_boardEdges = new IntegerRef[_numEdges];
		createArrays();
		int i, numEdgesAtLine = 1+2*_sizeY;
		for (i=0; i<_numEdges; i++) {
			if ((i<_sizeY)|| ( (i%numEdgesAtLine)==(_sizeY))||
				( (i%numEdgesAtLine)==(numEdgesAtLine-1))||
				( (i>(_numEdges-_sizeY-1))))
				_boardEdges[i] = new IntegerRef(1); // border
			else
				_boardEdges[i] = new IntegerRef(0); // wildcard
		}
	}

	void readEdgesNoHint(int[] pieces, IntegerRef pos) {
		_sizeX = pieces[pos.getValue()]; pos.plusplus();
		_sizeY = pieces[pos.getValue()]; pos.plusplus();
		_numEdgeTypes = pieces[pos.getValue()] + 2; // 0=wildcard 1=border
        pos.plusplus();
        readEdges(/*pieces, pos*/);
	}

	void readEdgesHint(int[] pieces, IntegerRef pos) {
		int i;
		_sizeX = _sizeY = pieces[pos.getValue()]; pos.plusplus();
		_numEdgeTypes =  pieces[pos.getValue()] + 2; // 0=wildcard 1=border
        pos.plusplus();
        int numHints = pieces[pos.getValue()]; pos.plusplus();
		_hintPieces = new ArrayList<HintPiece>();
		for (i = 0; i < numHints; i++) {
            int posX = pieces[pos.getValue()]; pos.plusplus();
            int posY = pieces[pos.getValue()]; pos.plusplus();
            int id = pieces[pos.getValue()]; pos.plusplus();
            int rotation = pieces[pos.getValue()]; pos.plusplus();
            HintPiece hpiece = new HintPiece(posX, posY, id, rotation);
			_hintPieces.add(hpiece);
		}
		readEdges(/*pieces, pos*/);
	}

	void adjustHintFactor(int x, int y) {
		int ix,iy;
		if ((x <= _sizeX/2+1 && y <= _sizeY/2+1) ||
				Math.abs(x-y) <= (_sizeX+_sizeY) / 6) {
			for (ix = 0; ix < x; ix++) {
				for (iy = 0; iy < y; iy++)
					_hintAdjustment[ix][iy] += -1000;
			}
		}
	}

    void adjustHintFactors() {
		for (int x = 0; x < _sizeX; x++) {
			for (int y = 0; y < _sizeY; y++)
				_hintAdjustment[x][y] = initHintFactor(x,y);
		}
 	    for (int p=0; p<_numPieces; p++) {
	    	if (_rowScanVector[p].type == HINT) {
	 	       int x = p / _sizeY;
	 	       int y = p % _sizeY;
	 	       adjustHintFactor(x, y);
	    	}
		}
    }

	void setHintPieces() {
        for (HintPiece hpiece : _hintPieces) {
            int x = hpiece.posX - 1;
            int y = hpiece.posY - 1;
            int p = y + _sizeY * x;
            PieceLocation solPiece = _rowScanVector[p];
            // our rotation is counter clockwise
            int prIndex = 4 * (hpiece.id - 1);
            for (int j = 0; j < 4; j++)
                _allPieceRotations.get(prIndex + j).type = HINT;
            int hintRotation = (4 - hpiece.rotation) % 4;
            PieceRotation pieceRotation =
                    _allPieceRotations.get(prIndex + hintRotation);
            solPiece.setLeft(pieceRotation.left);
            solPiece.setTop(pieceRotation.top);
            solPiece.setRight(pieceRotation.right);
            solPiece.setBottom(pieceRotation.bottom);
            solPiece.type = HINT;
        }
        adjustHintFactors();
	}

    void assignType(PieceLocation piece, int p, int x, int y) {
    	if (piece.type != HINT) {
    		if ((x==0 && y==0) || (x==_sizeX-1 && y==_sizeY-1) ||
    				(x==0 && y==_sizeY-1) || (x==_sizeX-1 && y==0))
    			piece.type = CORNER;
    		else  if (x==0 || y==0 || x==_sizeX-1 || y==_sizeY-1)
       			piece.type = BORDER;
        	else
      			piece.type = NORMAL;
     	}
	}

    void assignCheck(PieceLocation piece, int p, int x, int y) {
    	if (piece.type != HINT) {
    		boolean checkLeft = (y==0);
       		boolean checkTop = (x==0);
       		boolean checkRight = (y==(_sizeY-1));
        	boolean checkBottom = (x==(_sizeX-1));
    		if (!checkLeft)
    			checkLeft = (_rowScanVector[p-1].type==HINT);
    		if (!checkRight)
    			checkRight = (_rowScanVector[p+1].type==HINT);
    		if (!checkBottom)
    			checkBottom = (_rowScanVector[p+_sizeY].type==HINT);
    		if (!checkTop)
    			checkTop = (_rowScanVector[p-_sizeY].type==HINT);
    		switch (piece.direction) {
				case TO_LEFT: {
					if (checkLeft && checkBottom)
						piece.check = CHECK_ALL;
					else if (checkLeft)
						piece.check = CHECK_LTR;
					else if (checkBottom)
						piece.check = CHECK_TRB;
					else
						piece.check = CHECK_TR;
					break;
				}
				case TO_TOP: {
					if (checkTop && checkRight)
						piece.check = CHECK_ALL;
					else if (checkTop)
						piece.check = CHECK_LTB;
					else if (checkRight)
						piece.check = CHECK_RBL;
					else
						piece.check = CHECK_BL;
					break;
				}
				case TO_RIGHT_BOTTOM: {
					if (checkRight && checkBottom)
						piece.check = CHECK_ALL;
					else if (checkRight)
						piece.check = CHECK_LTR;
					else if (checkBottom)
						piece.check = CHECK_LTB;
					else
						piece.check = CHECK_LT;
					break;
				}
				case TO_ALL: {
					piece.check = CHECK_ALL;
					break;
				}
    		}
    	} else
			piece.check = CHECK_ALL;
     }

     void assignTypes(PieceLocation[] pieces) {
 	    for (int p=0; p<_numPieces; p++) {
 	       int x = p / _sizeY;
 	       int y = p % _sizeY;
 	       assignType(pieces[p], p, x, y);
 	       assignCheck(pieces[p], p, x, y);
 	    }
     }

    @SuppressWarnings({"SuspiciousNameCombination"})
    void rotateSolutionVector() {
		PieceLocation[] scanVector = new PieceLocation[_numPieces];
	    int p;
	    for (p=0; p<_numPieces; p++) {
	       int x = p / _sizeY;
	       int y = p % _sizeY;
	       // 90 degree clockwise
	       int dx = _sizeY-y-1;
	       int dy = x;
	       int dp = _sizeX * dx + dy;
	       PieceLocation piece = _rowScanVector[p];
	       scanVector[dp] =
	    	   new PieceLocation(piece.right,piece.bottom,piece.left,
	    			   piece.top, dp);
	       scanVector[dp].type = piece.type;
	       _hintAdjustment[x][y] = initHintFactor(x,y);
	    }
	    for (p=0; p<_numPieces; p++)
	    	_rowScanVector[p] = scanVector[p];
	    adjustHintFactors();
    }

    @SuppressWarnings({"SuspiciousNameCombination"})
    void mirrorSolutionVector() {
		PieceLocation[] scanVector = new PieceLocation[_numPieces];
	    int p;
	    for (p=0; p<_numPieces; p++) {
	       int x = p / _sizeY;
	       int y = p % _sizeY;
	       // mirror along NW-SE diagonal
	       int dx = y;
	       int dy = x;
	       int dp = _sizeX * dx + dy;
	       PieceLocation piece = _rowScanVector[p];
	       scanVector[dp] =
	    	   new PieceLocation(piece.left,piece.bottom,piece.right,
	    			   piece.top, dp);
	       scanVector[dp].type = piece.type;
	       _hintAdjustment[x][y] = initHintFactor(x,y);
	    }
	    for (p=0; p<_numPieces; p++)
	    	_rowScanVector[p] = scanVector[p];
	    adjustHintFactors();
	    // mirror all piece rotations
        for (PieceRotation pr : _allPieceRotations) {
            int top = pr.top;
            pr.top = pr.left;
            pr.left = top;
            int right = pr.right;
            pr.right = pr.bottom;
            pr.bottom = right;
        }
    }

    void createSolutionVector() {
		_rowScanVector = new PieceLocation[_numPieces];
		int numEdgesAtLine = 1+2*_sizeY;
		for (int p=0; p<_numPieces; p++) {
			int x = p / _sizeY;
			int y = p % _sizeY;
			_rowScanVector[p] = new PieceLocation(
				_boardEdges[x*numEdgesAtLine+y],
				_boardEdges[x*numEdgesAtLine+y+_sizeY+1],
				_boardEdges[x*numEdgesAtLine+numEdgesAtLine+y],
				_boardEdges[x*numEdgesAtLine+y+_sizeY], p);
		}
	}

   void createPieceRotations(int[] pieces, IntegerRef pos) {
		for (int i = 0; i < _numPieces; i++) {
			int a = pieces[pos.getValue()]; pos.plusplus();
			int b = pieces[pos.getValue()]; pos.plusplus();
			int c = pieces[pos.getValue()]; pos.plusplus();
			int d = pieces[pos.getValue()]; pos.plusplus();

			PieceRotation pieceRotation1 = new PieceRotation((a+1),(b+1),(c+1),(d+1),new BooleanRef(false));
			PieceRotation pieceRotation2 = new PieceRotation((b+1),(c+1),(d+1),(a+1),pieceRotation1.isUsed);
			PieceRotation pieceRotation3 = new PieceRotation((c+1),(d+1),(a+1),(b+1),pieceRotation1.isUsed);
			PieceRotation pieceRotation4 = new PieceRotation((d+1),(a+1),(b+1),(c+1),pieceRotation1.isUsed);

			_allPieceRotations.add(pieceRotation1);
			_allPieceRotations.add(pieceRotation2);
			_allPieceRotations.add(pieceRotation3);
			_allPieceRotations.add(pieceRotation4);
		}
	}

	void readPieces(int[] pieces, int numRotations) {
		IntegerRef pos = new IntegerRef();
        if (null!=pieces) {
			if (_useHints)
				readEdgesHint(pieces, pos);
			else
				readEdgesNoHint(pieces, pos);
			createSolutionVector();
			createPieceRotations(pieces, pos);
			if (_useHints)
				setHintPieces();
			//shuffleVector(_allPieceRotations);
			for (int i = 0; i < numRotations % 4; i++)
				rotateSolutionVector();
			boolean isMirror = numRotations >= 4;
			if (isMirror)
				mirrorSolutionVector();
			assignTypes(_rowScanVector);
			computePieceMatches();
		}
	}

	void dumpMatches(PieceLocation nextPiece) {
		List<PieceRotation> matches = getMatches(nextPiece);
		System.out.print( String.format("\n%d Matches", matches.size()) );
        for (PieceRotation p : matches) {
            System.out.print(String.format("\nMatch %d %d %d %d u=%d h=%d",
                    p.top, p.right, p.bottom, p.left, p.isUsed(), p.type == HINT));
        }
        System.out.print("\n");
        System.out.flush();
	}

	void solve() throws IOException
    {
		 _hintStrategy = hintStrategy2();
//		_hintStrategy = hintStrategy();
//		_hintStrategy = simpleStrategy();
//		_hintStrategy = lineScan();
//		_hintStrategy = rowScan();
//		_hintStrategy = Arrays.asList(_rowScanVector);

        setStartTime();
		_maxDepth = 0;
//		solveTest(1);
		solve(1, 0);
	}

	void pieceToStrategy(List<PieceLocation> scanVector, IntegerRef svp, int x, int y, int dir) {
		if (!isUsed(x,y)) {
			int p = y + _sizeY*x;
			PieceLocation piece = _rowScanVector[p];
		    scanVector.add(svp.getValue(),
		    	   (new PieceLocation(piece.top,piece.right,piece.bottom,
		    			   piece.left, p)));
		    scanVector.get(svp.getValue()).type = piece.type;
		    scanVector.get(svp.getValue()).direction = dir;
		    assignCheck(scanVector.get(svp.getValue()), p, x, y);
		    svp.plusplus();
		    setUsed(x,y);
		}
	}

	List<PieceLocation> lineScan() {
		List<PieceLocation> scanVector = new ArrayList<PieceLocation>(_numPieces);
		IntegerRef svp = new IntegerRef();
		for (int y = 0; y < _sizeY; y++) {
			for (int x = 0; x < _sizeX; x++)
				pieceToStrategy(scanVector, svp, x, y, TO_RIGHT_BOTTOM);
		}
		return scanVector;
	}

	List<PieceLocation>  rowScan() {
		List<PieceLocation> scanVector = new ArrayList<PieceLocation>(_numPieces);
		IntegerRef svp = new IntegerRef();
		for (int x = 0; x < _sizeX; x++) {
			for (int y = 0; y < _sizeY; y++)
				pieceToStrategy(scanVector, svp, x, y, TO_RIGHT_BOTTOM);
		}
		return scanVector;
	}

	List<PieceLocation>  simpleStrategy() {
		List<PieceLocation> scanVector = new ArrayList<PieceLocation>(_numPieces);
		IntegerRef svp = new IntegerRef();
		for (int d = 0; d < _sizeX; d++) {
			for (int x = 0; x < d; x++)
				pieceToStrategy(scanVector, svp, x, d, TO_RIGHT_BOTTOM);
			for (int y = 0; y <= d; y++)
				pieceToStrategy(scanVector, svp, d, y, TO_RIGHT_BOTTOM);
		}
		return scanVector;
	}

	void fillHints(List<PieceLocation> scanVector, IntegerRef svp) {
		for (int x = 0; x < _sizeX; x++) {
			for (int y = 0; y < _sizeY; y++)
			    if (isHint(x,y))
			    	pieceToStrategy(scanVector, svp, x, y, TO_RIGHT_BOTTOM);
		}
	}

	List<PieceLocation> hintStrategy() {
		List<PieceLocation> scanVector = new ArrayList<PieceLocation>(_numPieces);
		IntegerRef svp = new IntegerRef();
		fillHints(scanVector, svp);
		for (int d = 0; d < _sizeX; d++) {
			if (isHint(d,d)) {
				for (int x = d-1; x >= 0; x--)
					pieceToStrategy(scanVector, svp, x, d, TO_TOP);
				for (int y = d-1; y >= 0; y--)
					pieceToStrategy(scanVector, svp, d, y, TO_LEFT);
			} else {
				for (int x = 0; x < d; x++)
					pieceToStrategy(scanVector, svp, x, d, TO_RIGHT_BOTTOM);
				for (int y = 0; y <= d; y++)
					pieceToStrategy(scanVector, svp, d, y, TO_RIGHT_BOTTOM);
			}
		}
		storeStrategy(scanVector);
		return scanVector;
	}

	List<PieceLocation> hintStrategy2() {
		List<PieceLocation> scanVector = new ArrayList<PieceLocation>(_numPieces);
		IntegerRef svp = new IntegerRef();
		fillHints(scanVector, svp);
		for (int d = 0; d < _sizeX; d++) {
			if (d < _sizeX-2) {
				for (int i = 0; i < d; i++) {
					int x,y;
					if (isHint(i,d+2)) {
						for (x = 0; x <= i; x++)
							pieceToStrategy(scanVector, svp, x, d, TO_RIGHT_BOTTOM);
						pieceToStrategy(scanVector, svp, i+1, d, TO_ALL);
						pieceToStrategy(scanVector, svp, i, d+1, TO_ALL);
						for (x = i-1; x >= 0 ; x--)
							pieceToStrategy(scanVector, svp, x, d+1, TO_TOP);
					}
					if (isHint(d+2,i)) {
						for (y = 0; y <= i; y++)
							pieceToStrategy(scanVector, svp, d, y, TO_RIGHT_BOTTOM);
						pieceToStrategy(scanVector, svp, d, i+1, TO_ALL);
						pieceToStrategy(scanVector, svp, d+1, i, TO_ALL);
						for (y = i-1; y >= 0; y--)
							pieceToStrategy(scanVector, svp, d+1, y, TO_LEFT);
					}
				}
			}
			if (isHint(d,d)) {
				for (int x = d-1; x >= 0; x--)
					pieceToStrategy(scanVector, svp, x, d, TO_TOP);
				for (int y = d-1; y >= 0; y--)
					pieceToStrategy(scanVector, svp, d, y, TO_LEFT);
			} else {
				for (int x = 0; x < d; x++)
					pieceToStrategy(scanVector, svp, x, d, TO_RIGHT_BOTTOM);
				for (int y = 0; y <= d; y++)
					pieceToStrategy(scanVector, svp, d, y, TO_RIGHT_BOTTOM);
			}
		}
		storeStrategy(scanVector);
		return scanVector;
	}

	PieceLocation getPiece(int x, int y) {
		int p = y + _sizeY*x;
		return _rowScanVector[p];
	}

	boolean isHint(int x, int y) {
		return getPiece(x,y).type == HINT;
	}

	boolean isUsed(int x, int y) {
		return getPiece(x,y).isUsed;
	}

	void setUsed(int x, int y) {
		getPiece(x,y).isUsed = true;
	}

	void doStatistics(PieceLocation nextPiece, int depth) {
if( STATS ) {
	    int x = nextPiece.pos / _sizeY;
	    int y = nextPiece.pos % _sizeY;
		_nodeCounts[depth]++;
		_xyCount[x][y]++;
		_xPlaced[depth] = x;
		_yPlaced[depth] = y;
}
	}

	void solve(int depth, int hintStrategyLoc) throws IOException {
		if (depth>_numPieces) {
			_numSolutions++;
			storeBoard();
			if( DUMP_SOLUTION_FOUND ) {
				printStats();
			}
			return;
		}

		if( DUMP_MIN_DEPTH ) {
			if (depth > _maxDepth) {
				_maxDepth = depth;
				System.out.print( String.format("\nSolver %d Max Depth = %d", _solverId, depth) );
				printStats();
			}
		}

        PieceLocation nextPiece = _hintStrategy.get(hintStrategyLoc);
        List<PieceRotation> matches = getMatchesFast(nextPiece);
   		switch (nextPiece.direction) {
       		case TO_RIGHT_BOTTOM: {
       			int oldRight = nextPiece.right();
       			int oldBottom = nextPiece.bottom();
                   for (PieceRotation p : matches) {
                       if (!p.isUsed())
                       {
                           _numPiecesPlaced++;
                           if (STATS)
                           {
                               doStatistics(nextPiece, depth);
                           }
                           nextPiece.setRight(p.right);
                           nextPiece.setBottom(p.bottom);
                           p.setUsed(true);
                           solve(depth + 1, hintStrategyLoc + 1);
                           p.setUsed(false);
                       }
                       if (STOP_AFTER_FIRST_CORNER_PIECE)
                       {
                           if (depth == 1) return;
                       }
                   }
                   nextPiece.setRight(oldRight);
       			nextPiece.setBottom(oldBottom);
 				break;
    		}
			case TO_LEFT: {
				int oldBottom = nextPiece.bottom();
				int oldLeft = nextPiece.left();
                for (PieceRotation p : matches) {
                    if (!(p.isUsed()))
                    {
                        _numPiecesPlaced++;
                        if (STATS)
                        {
                            doStatistics(nextPiece, depth);
                        }
                        nextPiece.setBottom(p.bottom);
                        nextPiece.setLeft(p.left);
                        p.setUsed(true);
                        solve(depth + 1, hintStrategyLoc + 1);
                        p.setUsed(false);
                    }
                    if (STOP_AFTER_FIRST_CORNER_PIECE)
                    {
                        if (depth == 1) return;
                    }
                }
                nextPiece.setBottom(oldBottom);
       			nextPiece.setLeft(oldLeft);
				break;
			}
       		case TO_TOP: {
       			int oldTop = nextPiece.top();
       			int oldRight = nextPiece.right();
                   for (PieceRotation p : matches) {
                       if (!(p.isUsed()))
                       {
                           _numPiecesPlaced++;
                           if (STATS)
                           {
                               doStatistics(nextPiece, depth);
                           }
                           nextPiece.setTop(p.top);
                           nextPiece.setRight(p.right);
                           p.setUsed(true);
                           solve(depth + 1, hintStrategyLoc + 1);
                           p.setUsed(false);
                       }
                       if (STOP_AFTER_FIRST_CORNER_PIECE)
                       {
                           if (depth == 1) return;
                       }
                   }
                   nextPiece.setTop(oldTop);
       		    nextPiece.setRight(oldRight);
       			break;
        	}
       		case TO_ALL: {
      			int oldTop = nextPiece.top();
       			int oldRight = nextPiece.right();
				int oldBottom = nextPiece.bottom();
				int oldLeft = nextPiece.left();
                   for (PieceRotation p : matches) {
                       if (!(p.isUsed()))
                       {
                           _numPiecesPlaced++;
                           if (STATS)
                           {
                               doStatistics(nextPiece, depth);
                           }
                           nextPiece.setTop(p.top);
                           nextPiece.setRight(p.right);
                           nextPiece.setBottom(p.bottom);
                           nextPiece.setLeft(p.left);
                           p.setUsed(true);
                           solve(depth + 1, hintStrategyLoc + 1);
                           p.setUsed(false);
                       }
                       if (STOP_AFTER_FIRST_CORNER_PIECE)
                       {
                           if (depth == 1) return;
                       }
                   }
                   nextPiece.setTop(oldTop);
       			nextPiece.setRight(oldRight);
     			nextPiece.setBottom(oldBottom);
       			nextPiece.setLeft(oldLeft);
 				break;
       		}
 		}
	}

	void solveTest(int depth) throws IOException
    {
if( DUMP_MIN_DEPTH ) {
		if (depth > _maxDepth) {
			_maxDepth = depth;
			System.out.print( String.format("\nSolver %d Max Depth = %d", _solverId, depth));
			printStats();
		}
}
		int pos = getNextPieceToAdvance();
		PieceLocation nextPiece =  _rowScanVector[pos];
		List<PieceRotation> matches = getMatches(nextPiece);
		int oldLeft = nextPiece.left();
		int oldTop = nextPiece.top();
		int oldRight = nextPiece.right();
		int oldBottom = nextPiece.bottom();
        for (PieceRotation p : matches) {
            if (!(p.isUsed()) && p.type == nextPiece.type)
            {
                _numPiecesPlaced++;
                if (STATS)
                {
                    int x = pos / _sizeY;
                    int y = pos % _sizeY;
                    _nodeCounts[depth]++;
                    _xyCount[x][y]++;
                    _xPlaced[depth] = x;
                    _yPlaced[depth] = y;
                }
                if (depth == _numPieces)
                {
                    _numSolutions++;
                    storeBoard();
                    if (DUMP_SOLUTION_FOUND)
                    {
                        printStats();
                    }
                    return;
                } else
                {
                    nextPiece.setLeft(p.left);
                    nextPiece.setTop(p.top);
                    nextPiece.setRight(p.right);
                    nextPiece.setBottom(p.bottom);
                    p.setUsed(true);
                    nextPiece.isUsed = true;
                    solveTest(depth + 1);
                    p.setUsed(false);
                    nextPiece.isUsed = false;
                    if (STOP_AFTER_FIRST_CORNER_PIECE)
                    {
                        if (!_useHints && depth == 1)
                            return;
                    }
                }
            }
        }
        nextPiece.setLeft(oldLeft);
		nextPiece.setTop(oldTop);
		nextPiece.setRight(oldRight);
		nextPiece.setBottom(oldBottom);
	}


	int computeMatchCount(PieceLocation piece, int x, int y) {
		//return getMatchCount(piece);
		int count = getMatchCount(piece);
		if (count == 0)
			return -(1<<24);
		else
			return count + _hintAdjustment[x][y];
	}

	int getNextPieceToAdvance() {
		int bestP = 0;
		int bestCount = 1<<24;
		for (int x = 0; x < _sizeX; x++) {
			for (int y = 0; y < _sizeY; y++) {
				int p = y + _sizeY*x;
				PieceLocation piece = _rowScanVector[p];
				if (!piece.isUsed) {
					int matchCount = computeMatchCount(piece, x, y);
					if (matchCount < bestCount) {
						bestCount = matchCount;
						bestP = p;
					}
				}
			}
		}
//		System.out.print( String.format("\n bestCount = %d bestP = %d",bestCount,bestP) );
//		System.out.flush();
		return bestP;
	}

    public static class IntegerRef
    {
        private int value;

        public IntegerRef()
        {
            this(0);
        }

        public IntegerRef(int value)
        {
            this.value = value;
        }

        public int plusplus()
        {
            return ++value;
        }

        public void setValue(int newValue)
        {
            value = newValue;
        }


        public int getValue()
        {
            return value;
        }

        public int hashCode()
        {
            return value;
        }

        public boolean equals(Object anObject)
        {
            IntegerRef integerRef = (IntegerRef) anObject;
            return this.value == integerRef.value;
        }

        public String toString()
        {
            return Integer.toString(value);
        }
    }

    public static class BooleanRef
    {
        private boolean value;

        public BooleanRef()
        {
            this(false);
        }

        public BooleanRef(boolean value)
        {
            this.value = value;
        }

        public void setValue(boolean newValue)
        {
            value = newValue;
        }

        public boolean getValue()
        {
            return value;
        }

        public int hashCode()
        {
            return value ? 1231 : 1237;
        }

        public boolean equals(Object anObject)
        {
            BooleanRef integerRef = (BooleanRef) anObject;
            return this.value == integerRef.value;
        }

        public String toString()
        {
            return Boolean.toString(value);
        }
    }
}