/*************************************************************************************
 *  Copyright (C) 2007 by Oscar Martinez <omllobet@gmail.com>                        *
 *                                                                                   *
 *  This program is free software; you can redistribute it and/or                    *
 *  modify it under the terms of the GNU General Public License                      *
 *  as published by the Free Software Foundation; either version 2                   *
 *  of the License, or (at your option) any later version.                           *
 *                                                                                   *
 *  This program is distributed in the hope that it will be useful,                  *
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of                   *
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the                    *
 *  GNU General Public License for more details.                                     *
 *                                                                                   *
 *  You should have received a copy of the GNU General Public License                *
 *  along with this program; if not, write to the Free Software                      *
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA   *
 *************************************************************************************/

import java.util.*;

public class Solver {
	
	//private final int MAXCALLS = 1000;
	
	public void solve(List<Moves> lm, Table t, SegMov sg, int numrec)
	{
		//if (numrec>=MAXCALLS) return;
		if(sg.getbool() && t.isfinal(sg.getpos()))
		{//is solution
			System.out.println("Solution:");
			for(int i=0; i< lm.size(); i++)
			{
				System.out.println(lm.get(i));	
			}
			return;
		}
		else
		{
			if(lm.isEmpty())
			{
				trymove(Moves.UP,t,lm, numrec);
				trymove(Moves.DOWN,t,lm, numrec);
				trymove(Moves.LEFT,t,lm, numrec);
				trymove(Moves.RIGHT,t,lm, numrec);
			}
			else
			{
				Moves m=lm.get(lm.size()-1);
				if (m==Moves.UP || m==Moves.DOWN)
				{
					trymove(Moves.LEFT,t,lm, numrec);
					trymove(Moves.RIGHT,t,lm, numrec);
				}
				else if (m==Moves.LEFT || m==Moves.RIGHT)
				{
					trymove(Moves.UP,t,lm, numrec);
					trymove(Moves.DOWN,t,lm, numrec);
				}
			}
		}
	}
	
	public void trymove(Moves m,Table t, List<Moves> l, int n)
	{
		SegMov s=t.isapossiblemove(m);
		if (s.getbool())
		{
			l.add(m);
			Position p= t.getcurrentposition();
			t.setcurrentposition(s.getpos());
			solve(l,t,s, n+1);
			t.setcurrentposition(p);
			t.setvisited(p,false);
			l.remove(l.size()-1);
		}
	}
}