grid.java

（1）、深度优先搜索。 （2）、可以点击面板上的按钮设置七种默认的初始状态。 （3）、点击“自定义”按钮可以自行设定初始状态。 （4）、设定初始状态后点击“搜索”按钮

package org.hites.pegjump;

import java.util.Stack;

import javax.swing.JOptionPane;

@SuppressWarnings("unchecked")
public class Grid {

	StringBuilder a;
	Stack hasChildState;
	Stack usedState;
	
	
	public Grid(String command) 
	{
		if("cross".equals(command))
		{
			a =  new StringBuilder("*********" +
								   "***000***" +
								   "***000***" +
								   "*000#000*" +
								   "*00###00*" +
								   "*000#000*" +
								   "***0#0***" +
								   "***000***" +
								   "*********");
		}
		else if("plus".equals(command))
		{
			a =  new StringBuilder("*********" +
					   "***000***" +
					   "***0#0***" +
					   "*000#000*" +
					   "*0#####0*" +
					   "*000#000*" +
					   "***0#0***" +
					   "***000***" +
					   "*********");
		}
		else if("fireplace".equals(command))
		{
			a =  new StringBuilder("*********" +
					   "***###***" +
					   "***###***" +
					   "*00###00*" +
					   "*00#0#00*" +
					   "*0000000*" +
					   "***000***" +
					   "***000***" +
					   "*********");
		}
		else if("uparrow".equals(command))
		{
			a =  new StringBuilder("*********" +
					   "***0#0***" +
					   "***###***" +
					   "*0#####0*" +
					   "*000#000*" +
					   "*000#000*" +
					   "***###***" +
					   "***###***" +
					   "*********");
		}
		else if("pyramid".equals(command))
		{
			a =  new StringBuilder("*********" +
					   "***000***" +
					   "***0#0***" +
					   "*00###00*" +
					   "*0#####0*" +
					   "*#######*" +
					   "***000***" +
					   "***000***" +
					   "*********");
		}
		else if("diamond".equals(command))
		{
			a =  new StringBuilder("*********" +
					   "***0#0***" +
					   "***###***" +
					   "*0#####0*" +
					   "*###0###*" +
					   "*0#####0*" +
					   "***###***" +
					   "***0#0***" +
					   "*********");
		}
		else if("solitaire".equals(command))
		{
			a =  new StringBuilder("*********" +
					   "***###***" +
					   "***###***" +
					   "*#######*" +
					   "*###0###*" +
					   "*#######*" +
					   "***###***" +
					   "***###***" +
					   "*********");
		}
	}
	
	@SuppressWarnings("unchecked")
	public boolean search()
	{
		StringBuilder b =  null;
		StringBuilder c =  null;
		StringBuilder d =  null;
		StringBuilder e =  null;
		Stack s = new Stack();
		hasChildState = new Stack();
		int count = 0; //统计钉子数
		boolean hasSollution = false;
		
		s.push(a);
		while(!s.empty())
		{
			a = new StringBuilder ((StringBuilder)s.pop());
			
			for(int j=0;j<a.length();j++)
				if(a.charAt(j) == '#')
					count++;
	
			System.out.println(count);	
			
			b = new StringBuilder(a);
			c = new StringBuilder(a);
			d = new StringBuilder(a);
			e = new StringBuilder(a);
			
			for(int i=0;i<a.length();i++)
			{
				//up
				if(b.charAt(i) == '#' && b.charAt(i-9) == '#' && b.charAt(i-18) == '0')
				{
					System.out.println(i+" ---up");
					b.setCharAt(i, '0');
					b.setCharAt(i-9, '0');
					b.setCharAt(i-18, '#');
					s.push(b);
					if(!(hasChildState.contains(a)))
						hasChildState.push(a);
				}
				
				//down
				if(c.charAt(i) == '#' && c.charAt(i+9) == '#' && c.charAt(i+18) == '0')
				{
					System.out.println(i+" ---down");
					c.setCharAt(i, '0');
					c.setCharAt(i+9, '0');
					c.setCharAt(i+18, '#');
					s.push(c);
					if(!(hasChildState.contains(a)))
						hasChildState.push(a);
				}
				
				
				//right
				if(e.charAt(i) == '#' && e.charAt(i+1) == '#' && e.charAt(i+2) == '0')
				{
					System.out.println(i+" ---right");
					e.setCharAt(i, '0');
					e.setCharAt(i+1, '0');
					e.setCharAt(i+2, '#');
					s.push(e);
					if(!(hasChildState.contains(a)))
						hasChildState.push(a);
				}
				
				//left
				if(d.charAt(i) == '#' && d.charAt(i-1) == '#' && d.charAt(i-2) == '0')
				{
					System.out.println(i+" ---left");
					d.setCharAt(i, '0');
					d.setCharAt(i-1, '0');
					d.setCharAt(i-2, '#');
					s.push(d);
					if(!(hasChildState.contains(a)))
						hasChildState.push(a);
				}
				
				
				b = new StringBuilder(a);
				c = new StringBuilder(a);
				d = new StringBuilder(a);
				e = new StringBuilder(a);
			}
			
			if(count == 1) 
			{
				s.removeAllElements();
				hasSollution=true;
			}
			count = 0;
		}
		
		if(hasSollution)
		{
			System.out.println("-------------------得到解，停止搜索---------------------");
			JOptionPane.showMessageDialog(null, "找到解!");
			backFind();
		}
		else{System.out.println("未找到解");JOptionPane.showMessageDialog(null, "未找到解!");}
		return hasSollution;		
		
	}

	
	public void backFind()
	{
		usedState = new Stack();
		//printState(a);
		usedState.push(a);
		
		int flag = 2;
		for(int i=hasChildState.size()-1;i>=0;i--)
		{
			StringBuilder s1 = (StringBuilder)hasChildState.get(i);
				if(count(s1) == flag)
			{
				//printState(s1);
				usedState.push(s1);
				flag++;
			}
		}
		
		/*while(!(usedState.empty()))
		{
			printState((StringBuilder)usedState.pop());
		}*/
		
		reShowGrid();
	}
	
	public static int count(StringBuilder s)
	{
		int count = 0;
		for(int j=0;j<s.length();j++)
			if(s.charAt(j) == '#')
				count++;
		return count;
	}
	
	public void printState(StringBuilder state)
	{
		System.out.println("  "+state.substring(12, 15)+"  ");
		System.out.println("  "+state.substring(21, 24)+"  ");
		System.out.println(state.substring(28, 35));
		System.out.println(state.substring(37, 44));
		System.out.println(state.substring(46, 53));
		System.out.println("  "+state.substring(57, 60)+"  ");
		System.out.println("  "+state.substring(66, 69)+"  ");
		System.out.println(" ============================ ");
	}
	
	public StringBuilder reShowGrid()
	{
		StringBuilder grid = (StringBuilder)usedState.pop();
		printState(grid);
		return grid;
		
	}
}