/**
	Deboggle.java

	A little cheat program for playing Boggle/Tangleword

	Given a grid, dimension and search depth range,
	Looks through grid and finds all words that can be formed
	and exist in the current WordBank (default.list).

	Juno Suk
	JunoWhoIM@aol.com

*/

import java.awt.*;
import java.awt.event.*;
import java.util.Vector;

public class Deboggle extends Frame implements ActionListener
{
	/** To use Deboggle from commandline,
	Usage: java Deboggle	<dimension>
				<min word length>

	default: dimension = 5, min = 4;

	*/
	public static void main(String[] argv)
	{
		if(argv.length > 3)
		{
			System.out.println("Usage: java Deboggle <dimension> <min word length>");
			System.exit(0);
		}

		int dimension = 5, min = 4;

		String tmpstr = null;

		if(argv.length > 0)
		{
			tmpstr = argv[0];
		}

		Deboggle dbog = new Deboggle(tmpstr);

		dbog.setVisible(true);
	}


	// THE OBJECT STUFF - - - - - - - - - - - - - - - - - - - - - - -
	WordBank wordbank = new WordBank();
	Vector wordvec = new Vector();

	// for grid analysis and search optimizing
	TwoStepAnalysis twostep = new TwoStepAnalysis();
	int[][] finalpaths = null;
	

	char[][] grid = null;

	boolean[][] flag = null;	// to mark letters already used
					// in traversal

	char[] wordarray = null;	// used for Q to QU expansions

	long starttime = System.currentTimeMillis();	// for timing limits
	long currenttime = System.currentTimeMillis();

	int min=4, dim=5, limit=0;
	int wordcount = 0;
	int resultlen = 0;	// for word wrapping in result textarea

	// AWT Components

	Button exitbut = new Button("Exit program");

	Button clearbut = new Button("Clear grid");
	Button randombut = new Button("Random grid");
	Button deboggle = new Button("Deboggle grid");
						// To start the deboggling
	Button existbut = new Button("Word(s) exists?");
	Button addbut = new Button("Add word(s)");
	Button removebut = new Button("Remove word(s)");

	Button loadbut = new Button("Load list");
	Button savebut = new Button("Save list");
	Button showbut = new Button("Show list");

	Choice dimchoice = new Choice();
	Choice minchoice = new Choice();
	Choice timechoice = new Choice();
	Label timelabel = new Label("00:00");

	TextArea gridfield = null;	// where grid is placed
	TextArea results = null;	// where results are placed


	public Deboggle(String dictionary)
	{
		if(dictionary==null) dictionary = "default";

		if(dictionary.endsWith(".bank") || dictionary.endsWith(".list"))
			dictionary = dictionary.substring(0,dictionary.length()-5);
		System.out.println("\nDeboggle");
		System.out.println("by Juno Suk (JunoWhoIM@aol.com)");

		System.out.println("\n\nPlease wait... loading dictionary\n");

		// load up default parameters and word dictionary
		try
		{
			wordbank.load(dictionary + ".bank");
			twostep.load(dictionary + ".step");
		}
		catch(Exception ex)
		{
			System.out.println("Error while loading word list.\nExiting...");
			System.exit(0);
		}

		this.min = min;
		this.dim = dim;


		// SET up window properties and layout
		buildGUI();

		// add event listeners
		buildEvents();

		results.append("\nLoaded word list of\n" + wordbank.size() + " words.\n");
		results.setCaretPosition(results.getText().length());
	}


	private void buildGUI()
	{
		GridBagLayout gbl = new GridBagLayout();
		GridBagConstraints gbc = new GridBagConstraints();

		this.setBackground(new Color(255,255,255));
		this.setLayout(gbl);



		// TOP-RIGHT - Buttons

		GridBagLayout trgbl = new GridBagLayout();
		GridBagConstraints trgbc = new GridBagConstraints();

		Panel topright = new Panel();
		topright.setBackground(new Color(255,255,255));
		topright.setLayout(trgbl);


		Panel toprightX = new Panel();
		toprightX.setBackground(new Color(255,255,255));
		toprightX.setLayout(new GridLayout(1,1));

		Panel toprightA = new Panel();
		toprightA.setBackground(new Color(255,255,255));
		toprightA.setLayout(new GridLayout(3,1));

		Panel toprightB = new Panel();
		toprightB.setBackground(new Color(255,255,255));
		toprightB.setLayout(new GridLayout(3,1));

		Panel toprightC = new Panel();
		toprightC.setBackground(new Color(255,255,255));
		toprightC.setLayout(new GridLayout(3,1));

		exitbut.setBackground(new Color(0,96,96));
		exitbut.setForeground(Color.white);

		loadbut.setBackground(new Color(0,96,96));
		loadbut.setForeground(Color.white);

		savebut.setBackground(new Color(0,96,96));
		savebut.setForeground(Color.white);

		showbut.setBackground(new Color(0,96,96));
		showbut.setForeground(Color.white);

		existbut.setBackground(new Color(0,96,96));
		existbut.setForeground(Color.white);

		addbut.setBackground(new Color(0,96,96));
		addbut.setForeground(Color.white);

		removebut.setBackground(new Color(0,96,96));
		removebut.setForeground(Color.white);

		clearbut.setBackground(new Color(0,96,96));
		clearbut.setForeground(Color.white);

		randombut.setBackground(new Color(0,96,96));
		randombut.setForeground(Color.white);

		deboggle.setBackground(new Color(0,96,96));
		deboggle.setForeground(Color.white);

		toprightX.add(exitbut);	// redundant, but makes sure
					// vertical spacing is equal
					// with other button groups

		toprightA.add(loadbut);
		toprightA.add(savebut);
		toprightA.add(showbut);

		toprightB.add(existbut);
		toprightB.add(addbut);
		toprightB.add(removebut);

		toprightC.add(clearbut);
		toprightC.add(randombut);
		toprightC.add(deboggle);

		trgbc.anchor=GridBagConstraints.CENTER;
		trgbc.fill = GridBagConstraints.HORIZONTAL;
		trgbc.weightx = 1.0; trgbc.weighty = 0.0;
		trgbc.ipadx = 5; trgbc.ipady = 5;
		trgbc.gridwidth = 1; trgbc.gridheight = 1;

		trgbc.gridx = 0; trgbc.gridy = 0;
		trgbl.setConstraints(toprightX,trgbc);
		topright.add(toprightX);

		trgbc.gridy++;
		trgbl.setConstraints(toprightA,trgbc);
		topright.add(toprightA);

		trgbc.gridy++;
		trgbl.setConstraints(toprightB,trgbc);
		topright.add(toprightB);

		trgbc.gridy++;
		trgbl.setConstraints(toprightC,trgbc);
		topright.add(toprightC);


		GridBagLayout topgbl = new GridBagLayout();
		GridBagConstraints topgbc = new GridBagConstraints();

		Panel toppan = new Panel();
		toppan.setLayout(topgbl);

		topgbc.anchor=GridBagConstraints.CENTER;
		topgbc.fill = GridBagConstraints.NONE;
		topgbc.weightx = 1.0; topgbc.weighty = 1.0;
		topgbc.ipadx = 5; topgbc.ipady = 5;
		topgbc.gridwidth = 1; topgbc.gridheight = 1;
		topgbc.gridx = 1; topgbc.gridy = 0;
		topgbl.setConstraints(topright,topgbc);
		toppan.add(topright);


		// TOP-LEFT - Grid array display

		gridfield = new TextArea("",10,15);
		gridfield.setEditable(true);
		gridfield.setFont(new Font("Courier",Font.BOLD,16));
		gridfield.setBackground(new Color(0,0,0));
		gridfield.setForeground(Color.yellow);

		topgbc.fill = GridBagConstraints.NONE;
		topgbc.gridx = 0;
		topgbc.weightx = 1.0; topgbc.weighty = 0.0;
		topgbl.setConstraints(gridfield,topgbc);
		toppan.add(gridfield);



		gbc.anchor=GridBagConstraints.NORTH;
		gbc.fill = GridBagConstraints.HORIZONTAL;
		gbc.weightx = 1.0; gbc.weighty = 1.0;
		gbc.ipadx = 5; gbc.ipady = 5;
		gbc.gridwidth = 1; gbc.gridheight = 1;
		gbc.gridx = 0; gbc.gridy = 0;
		gbl.setConstraints(toppan,gbc);
		this.add(toppan);



		// MID - with date and config

		Panel midpan = new Panel();
		midpan.setLayout(new BorderLayout());

		Panel leftpan = new Panel();
		leftpan.setBackground(new Color(255,255,255));
		leftpan.setLayout(new GridLayout(3,1));
			dimchoice.addItem("Grid dimensions: 3x3");
			dimchoice.addItem("Grid dimensions: 4x4");
			dimchoice.addItem("Grid dimensions: 5x5");
			dimchoice.addItem("Grid dimensions: 6x6");
			dimchoice.addItem("Grid dimensions: 7x7");
			dimchoice.addItem("Grid dimensions: 8x8");
			dimchoice.addItem("Grid dimensions: 9x9");
			dimchoice.addItem("Grid dimensions: 10x10");
			dimchoice.setBackground(new Color(128,0,0));
			dimchoice.setForeground(Color.white);
			dimchoice.select(2);
		leftpan.add(dimchoice);
			minchoice.addItem("Minimum word length: 3");
			minchoice.addItem("Minimum word length: 4");
			minchoice.addItem("Minimum word length: 5");
			minchoice.addItem("Minimum word length: 6");
			minchoice.setBackground(new Color(128,0,0));
			minchoice.setForeground(Color.white);
			minchoice.select(1);
		leftpan.add(minchoice);
			timechoice.addItem("Time limit: :30");
			timechoice.addItem("Time limit: 1:00");
			timechoice.addItem("Time limit: 1:30");
			timechoice.addItem("Time limit: 2:00");
			timechoice.addItem("Time limit: 3:00");
			timechoice.addItem("Time limit: 4:00");
			timechoice.addItem("Time limit: 5:00");
			timechoice.addItem("Time limit: 10:00");
			timechoice.setBackground(new Color(128,0,0));
			timechoice.setForeground(Color.white);
			timechoice.select(3);
		leftpan.add(timechoice);

			timelabel.setForeground(new Color(128,0,0));
			timelabel.setFont(new Font("Helvetica",Font.BOLD,60));

		midpan.add("West",leftpan);
		midpan.add("East",timelabel);

		gbc.anchor = GridBagConstraints.CENTER;
		gbc.fill = GridBagConstraints.HORIZONTAL;
		gbc.gridy++; // y = 1
		gbl.setConstraints(midpan,gbc);
		this.add(midpan);



		// BOTTOM - Show words found
		results = new TextArea("",25,40);// where results are placed
		results.setEditable(false);
		results.setFont(new Font("Helvetica",Font.PLAIN,12));
		results.setBackground(new Color(0,0,0));
		results.setForeground(Color.white);

		gbc.anchor = GridBagConstraints.CENTER;
		gbc.fill = GridBagConstraints.BOTH;
		gbc.gridx = 0; gbc.gridy++; // y = 2
		gbl.setConstraints(results,gbc);
		this.add(results);


		this.setTitle("Deboggle");
		this.pack();
		this.setVisible(true);

		Dimension screendim = Toolkit.getDefaultToolkit().getScreenSize();

		Dimension windowdim = this.getSize();

		// Set to show on lower right hand corner
		this.setLocation(screendim.width-windowdim.width, screendim.height-windowdim.height);

		results.setText("Deboggle v1.0\nby Juno Suk, JunoWhoIM@aol.com\n\n");


	}


	private void buildEvents()
	{
		exitbut.addActionListener(this);
		loadbut.addActionListener(this);
		savebut.addActionListener(this);
		showbut.addActionListener(this);
		existbut.addActionListener(this);
		addbut.addActionListener(this);
		removebut.addActionListener(this);
		clearbut.addActionListener(this);
		randombut.addActionListener(this);
		deboggle.addActionListener(this);
	}


	public void actionPerformed(ActionEvent ex)
	{
		setConfig();

		Object target = ex.getSource();

		if(target == deboggle)
		{
			if(deboggle.getLabel().equals("Deboggle grid"))
			{
				// RESET and SETUP all variables and configurations
				// for deboggle search
				wordvec.removeAllElements();
				deboggle.setLabel("Stop deboggle");
				// button pushed, clear fields and start searching!
				wordcount = 0;
				resultlen = 0;
	
				String gridstr = gridfield.getText();
	
				gridstr = gridstr.toUpperCase();
	
				char[] strarray = gridstr.toCharArray();
				gridstr = "";
				for(int i = 0; i < strarray.length; i++)
				{
					if( ((int)strarray[i]) > 64 &&
					    ((int)strarray[i]) < 91)
						gridstr += "" + (char)strarray[i];
				}
	
				if(gridstr.length() < 1)
				{
					deboggle.setLabel("Deboggle grid");
					return;
				}
	
				gridfield.setText("");
	
				setTime();
	
				while(gridstr.length() < dim*dim)
					gridstr += "X";
	
				startSearch(gridstr);
	
				deboggle.setLabel("Deboggle grid");
			}
			else
			{
				results.append("Stopping search.\n");
				results.setCaretPosition(results.getText().length());
				starttime = currenttime - 6000000;
				deboggle.setLabel("Deboggle grid");
			}
		}	// end deboggle button handler

		else if(target == clearbut)
		{
			resultlen = 0;
			gridfield.setText("");
			results.append("\nCleared grid.\n");
			results.setCaretPosition(results.getText().length());
		}

		else if(target == randombut)
		{
			results.append("\nGenerated random grid.\n");
			results.setCaretPosition(results.getText().length());
		}

		else if(target == exitbut)
		{
			// confirm no save of current word list
			//	(if modified)

			results.append("\nExiting program.\n");
			results.setCaretPosition(results.getText().length());
			System.exit(0);
		}

		else if(target == loadbut)
		{
			results.append("\nLoading file: \n");
			results.setCaretPosition(results.getText().length());

			results.append("\nFinished loading.\n");
			results.append("\n" + " words added.\n");
			results.setCaretPosition(results.getText().length());
		}

		else if(target == savebut)
		{
			results.append("\nSaved word list to file: \n");
			results.setCaretPosition(results.getText().length());
		}

		else if(target == showbut)
		{
			results.append("\nShowing words with prefix: \n");
			results.setCaretPosition(results.getText().length());
		}

		else if(target == existbut)
		{
			results.append("\nWord \"" + " \" exists.\n");
			results.setCaretPosition(results.getText().length());
			results.append("\nWord \"" + " \" does not exist.\n");
			results.setCaretPosition(results.getText().length());
		}

		else if(target == addbut)
		{
			results.append("\nWord \"" + " \" added to word list.\n");
			results.setCaretPosition(results.getText().length());
			results.append("\nWord \"" + " \" could not be added.\n");
			results.setCaretPosition(results.getText().length());
		}

		else if(target == removebut)
		{
			results.append("\nWord \"" + " \" removed from word list.\n");
			results.setCaretPosition(results.getText().length());
			results.append("\nWord \"" + " \" could not be removed.\n");
			results.setCaretPosition(results.getText().length());
		}

	}


	private void setConfig()
	{
		// read in config
		this.dim = dimchoice.getSelectedIndex() + 3;
		this.min = minchoice.getSelectedIndex() + 3;

		int idx = timechoice.getSelectedIndex();
		if(idx==0) this.limit = 30000;
		else if(idx==1) this.limit = 60000;
		else if(idx==2) this.limit = 90000;
		else if(idx==7) this.limit = 600000;
		else this.limit = (idx-1) * 60000;
	}


	public synchronized void startSearch(String wordgrid)
	{
		createGrid(wordgrid);
		analyzeGrid();
		searchGrid();

		results.append("\nFound " + wordcount + " words.\n");
		results.setCaretPosition(results.getText().length());

	}

	private void createGrid(String wordgrid)
	{

		grid = new char[dim][];

		int startidx = 0;
		int endidx = startidx + dim;

		// assuming grid has square dimensions
		
		String tmpstr = null;

		results.setText("Deboggling grid:\n");

		// center grid in gridfield
		int spaces = (10 - dim) / 2;
		for(int i = 0; i < spaces; i++)
			gridfield.append("\n");

		spaces = (15-dim) / 2;

		for(int i = 0; i < dim; i++)
		{
			tmpstr = wordgrid.substring(startidx,endidx);
			grid[i] = tmpstr.toCharArray();

			// center grid
			for(int j = 0; j < spaces; j++)
				gridfield.append(" ");

			gridfield.append(tmpstr);
			results.append(tmpstr + "\n");

			startidx += dim;
			endidx = startidx + dim;

			// to keep grid within the boundaries without an
			// extra line at the end
			if(i!=dim-1) { gridfield.append("\n"); }
		}

		results.append("\n");
		results.setCaretPosition(results.getText().length());

		flag = new boolean[dim][dim];
		for(int i = 0; i < dim; i++)
			for(int j = 0; j < dim; j++)
				flag[i][j] = false;
	}


	private void analyzeGrid()
	{
		Vector paths = new Vector();
		int[] info = null;
		int ch1 = 0;

		for(int i = 0; i < dim; i++)
		{
			for(int j = 0; j < dim; j++)
			{
				ch1 = (int)grid[i][j] - 65;

				if(i != 0)
				{
					if(j!=0)
					{
					info = new int[5];
					info[0] = i;
					info[1] = j;
					info[2] = i-1;
					info[3] = j-1;
					info[4] = twostep.step2[ch1][grid[i-1][j-1]-65];
					paths.addElement(info);;
					}

					if(j<dim-1)
					{
					info = new int[5];
					info[0] = i;
					info[1] = j;
					info[2] = i-1;
					info[3] = j+1;
					info[4] = twostep.step2[ch1][grid[i-1][j+1]-65];
					paths.addElement(info);;
					}

					info = new int[5];
					info[0] = i;
					info[1] = j;
					info[2] = i-1;
					info[3] = j;
					info[4] = twostep.step2[ch1][grid[i-1][j]-65];
					paths.addElement(info);;

				}

				if(i < dim-1)
				{
					if(j!=0)
					{
					info = new int[5];
					info[0] = i;
					info[1] = j;
					info[2] = i+1;
					info[3] = j-1;
					info[4] = twostep.step2[ch1][grid[i+1][j-1]-65];
					paths.addElement(info);;
					}

					if(j<dim-1)
					{
					info = new int[5];
					info[0] = i;
					info[1] = j;
					info[2] = i+1;
					info[3] = j+1;
					info[4] = twostep.step2[ch1][grid[i+1][j+1]-65];
					paths.addElement(info);;
					}

					info = new int[5];
					info[0] = i;
					info[1] = j;
					info[2] = i+1;
					info[3] = j;
					info[4] = twostep.step2[ch1][grid[i+1][j]-65];
					paths.addElement(info);;

				}

				if(j!=0)
				{
				info = new int[5];
				info[0] = i;
				info[1] = j;
				info[2] = i;
				info[3] = j-1;
				info[4] = twostep.step2[ch1][grid[i][j-1]-65];
				paths.addElement(info);;
				}

				if(j<dim-1)
				{
				info = new int[5];
				info[0] = i;
				info[1] = j;
				info[2] = i;
				info[3] = j+1;
				info[4] = twostep.step2[ch1][grid[i][j+1]-65];
				paths.addElement(info);;
				}
			}
		} // end of evaluation

		// Now sort evaluations
		int[] indices = new int[paths.size()];
		int[] evals = new int[indices.length];

		for(int i = 0; i < indices.length; i++)
		{
			indices[i] = i;
			evals[i] = ((int[])paths.elementAt(i))[4];
		}

		quickSort(evals,indices);

		finalpaths = new int[indices.length][];

		for(int i = 0; i < indices.length; i++)
		{
			finalpaths[i] = (int[])paths.elementAt(indices[i]);
		}
	}


	private void searchGrid()
	{
		starttime = System.currentTimeMillis();
		currenttime = starttime;

		int[] info = null;

		for(int i = finalpaths.length-1; i >=0 ; i--)
		{
			info = (int[])finalpaths[i];

			int len = 1;

			String ch = "" + grid[info[0]][info[1]];
			if(ch.equals("Q"))
			{
				ch = "QU";
				len++;
			}

			flag[info[0]][info[1]] = true;

			ch += "" + grid[info[2]][info[3]];
			len++;
			if(ch.endsWith("Q"))
			{
				ch += "U";
				len++;
			}


			flag[info[2]][info[3]] = true;

			searchRecurse(ch, info[2], info[3], len);

			flag[info[0]][info[1]] = false;
			flag[info[2]][info[3]] = false;

			currenttime = System.currentTimeMillis();
			setTime();
			if((currenttime-starttime) > this.limit)
			{
				results.append("\nTimes up!\n");
				results.setCaretPosition(results.getText().length());
				break;
			}
			else if(i==0)
			{
				results.append("\nSearch completed.");
				results.setCaretPosition(results.getText().length());
			}
		}


	}



	private void setTime()
	{
		if(starttime == 0) timelabel.setText("00:00");
		else
		{
			long timediff = currenttime - starttime;
			timediff = this.limit - timediff;

			timediff /= 1000;
			if(timediff < 0) timediff = 0;

			String tmpmin = "" + timediff/60;
			String tmpsec = "" + timediff%60;

			if(tmpmin.length() < 2) tmpmin = "0" + tmpmin;
			if(tmpsec.length() < 2) tmpsec = "0" + tmpsec;

			timelabel.setText("" + tmpmin + ":" + tmpsec);
		}
	}



	private void searchRecurse(String str, int r, int c, int len)
	{
		// check if current word is in word bank and is
		// in the length range
		if(len >= min)
		{

			if(wordbank.exists(str) && !wordvec.contains(str))
			{
				int strlen = str.length() + 1;

				if( (strlen + resultlen) > 39 )
				{
					results.append("\n");
					results.setCaretPosition(results.getText().length());
					resultlen = 0;
				}

				results.append(str + "  ");
				resultlen += strlen;

				wordvec.addElement(str);
				wordcount++;
			}
		}

		String ch = null;
		int inclen;		// length increment


		// traverse all eight possible directions
		if(len < 6)
		{
			if(r > 0)
			{
				// upper left
				if(c > 0 && !flag[r-1][c-1])
				{
					inclen = 1;
					ch = "" + grid[r-1][c-1];
					if(ch.equals("Q"))
					{
						ch = "QU";
						inclen = 2;
					}

					flag[r-1][c-1] = true;
					searchRecurse(str + ch, r-1, c-1,
							len + inclen);
					flag[r-1][c-1] = false;
				}

				// upper mid
				if(!flag[r-1][c])
				{
					inclen = 1;
					ch = "" + grid[r-1][c];
					if(ch.equals("Q"))
					{
						ch = "QU";
						inclen = 2;
					}

					flag[r-1][c] = true;
					searchRecurse(str + ch, r-1, c,
							len + inclen);
					flag[r-1][c] = false;
				}
				// upper right
				if(c < (dim-1) && !flag[r-1][c+1])
				{
					inclen = 1;
					ch = "" + grid[r-1][c+1];
					if(ch.equals("Q"))
					{
						ch = "QU";
						inclen = 2;
					}

					flag[r-1][c+1] = true;
					searchRecurse(str + ch, r-1, c+1,
							len + inclen);
					flag[r-1][c+1] = false;
				}
			}


			if(r < (dim-1))
			{
				// lower left
				if(c > 0 && !flag[r+1][c-1])
				{
					inclen = 1;
					ch = "" + grid[r+1][c-1];
					if(ch.equals("Q"))
					{
						ch = "QU";
						inclen = 2;
					}

					flag[r+1][c-1] = true;
					searchRecurse(str + ch, r+1, c-1,
							len + inclen);
					flag[r+1][c-1] = false;
				}

				// lower mid
				if(!flag[r+1][c])
				{
					inclen = 1;
					ch = "" + grid[r+1][c];
					if(ch.equals("Q"))
					{
						ch = "QU";
						inclen = 2;
					}

					flag[r+1][c] = true;
					searchRecurse(str + ch, r+1, c,
							len + inclen);
					flag[r+1][c] = false;
				}
				// lower right
				if(c < (dim-1) && !flag[r+1][c+1])
				{
					inclen = 1;
					ch = "" + grid[r+1][c+1];
					if(ch.equals("Q"))
					{
						ch = "QU";
						inclen = 2;
					}

					flag[r+1][c+1] = true;
					searchRecurse(str + ch, r+1, c+1,
							len + inclen);
					flag[r+1][c+1] = false;
				}
			}

			if(c > 0)
			{
				// mid left
				if(!flag[r][c-1])
				{
					inclen = 1;
					ch = "" + grid[r][c-1];
					if(ch.equals("Q"))
					{
						ch = "QU";
						inclen = 2;
					}

					flag[r][c-1] = true;
					searchRecurse(str + ch, r, c-1,
							len + inclen);
					flag[r][c-1] = false;
				}
			}


			if(c < (dim-1))
			{
				// mid right
				if(!flag[r][c+1])
				{
					inclen = 1;
					ch = "" + grid[r][c+1];
					if(ch.equals("Q"))
					{
						ch = "QU";
						inclen = 2;
					}

					flag[r][c+1] = true;
					searchRecurse(str + ch, r, c+1,
							len + inclen);
					flag[r][c+1] = false;
				}
			}


		}
	}

        /** quicksort algorithm (with indices),
          * orders the int array as well as the contents of
          * index array indices. With this, the caller can order
          * other fields that must maintain adjacency to the int array.
        */
        public final static void quickSort(int[] evals, int[] indices)
        {
                quickSort(evals, indices, 0, evals.length-1);
        }

        /** quicksort algorithm (with indices and range)
          * can specify a partial sort of evals and indices using
          * lowest and highest */
        public final static void quickSort(int[] evals, int[] indices,
                                                int lowest, int highest)
        {
                int mid_evals;
                int high = highest;
                int low = lowest;

                if(highest > lowest)
                {
                   mid_evals = evals[(highest + lowest) / 2];
                   while(low <= high)
                   {
                        while(low < highest && evals[low] < mid_evals)
                                ++low;
                        while(high > lowest && evals[high] > mid_evals)
                                --high;
                        if(low <= high)
                        {
                                int temp_evals = evals[low];
                                int temp_int = indices[low];

                                evals[low] = evals[high];
                                indices[low] = indices[high];

                                evals[high] = temp_evals;
                                indices[high] = temp_int;
                                high--;
                                low++;
                        }
                   }
                   if(lowest < high)
                        quickSort(evals, indices, lowest, high);
                   if(highest > low)
                        quickSort(evals, indices, low, highest);
                }
        }


}