knighttour.java

本程序是著名的骑士巡游问题,利用了最小度优先和回溯算法,

import java.util.*;
import java.awt.*;
import java.awt.geom.*;
import javax.swing.*;
import java.awt.event.*;
import javax.imageio.*;
import java.io.*;

public class KnightTour
{
    public static void main(String[] args)
    {
        KnightsBoardFrame frame = new KnightsBoardFrame();
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setVisible(true);
    }
}
 
class KnightsBoardFrame extends JFrame
{
    public KnightsBoardFrame()
    {
        Toolkit kit = Toolkit.getDefaultToolkit();
        Dimension screenSize = kit.getScreenSize();

        int screenHeight = screenSize.height;
        int screenWidth = screenSize.width;

        setSize(600,600);
        setLocation(screenWidth / 6,screenHeight / 6);

        setTitle("knight's tour");

        KnightsBoardPanel panel = new KnightsBoardPanel();
        add(panel);
    }

}

class KnightsBoardPanel extends JPanel
{
    public KnightsBoardPanel()
    {
        startButton = new JButton("开始");
		startButton.addActionListener(new startAction());
        exitButton = new JButton("退出");
         
        JPanel buttonPanel = new JPanel();
        buttonPanel.add(startButton);
        buttonPanel.add(exitButton);
        add(buttonPanel,BorderLayout.NORTH);

        exitButton.addActionListener(new 
            ActionListener()
            {
            public void actionPerformed(ActionEvent event)
               {
                System.exit(0);
               }
            });

         try 
         {
               img = ImageIO.read(new File("Horse.gif"));
         }
         catch (IOException e)
         {
               e.printStackTrace();
         }
		knighttour = new ArrayList<Dimension>();
    }
    private JButton startButton;
    private JButton exitButton;
	private Image img;
	private ArrayList<Dimension> knighttour;

    private class startAction implements ActionListener
	{
		public void actionPerformed(ActionEvent event)
		{
			if (knighttour.size() >= 64) return;
			originalSize = knighttour.size();
			while (knighttour.size() < 64)
			{
				if (knighttour.size() == 0)
				{
					int i = (int) (Math.random() * 8);
					int j = (int) (Math.random() * 8);
					knighttour.add(new Dimension(i, j));
				}
				ArrayList<Dimension> nextPossiblePositions = new ArrayList<Dimension>();
				Dimension d = knighttour.get(knighttour.size() - 1);
				nextPossiblePositions = getNextPossiblePositions(d);
				if (nextPossiblePositions.size() == 0 && knighttour.size() >0)
				{
					int size = knighttour.size();
					for (int i = originalSize; i <= size; i++)
						knighttour.remove(knighttour.size() - 1);
					originalSize = knighttour.size();
					continue;
				}
				getNextPosition(nextPossiblePositions);
			}
			Thread t = new Thread(new AnimationPaint());
			t.start();
		}
		private int originalSize;
		private class AnimationPaint implements Runnable
		{
			public void run()
			{
				startButton.setEnabled(false);
				Dimension[] temp = new Dimension[64];
				temp = knighttour.toArray(temp);
				knighttour.removeAll(knighttour);
				for (int i = 0; i < originalSize; i++)
				{
					knighttour.add(temp[i]);
				}
				for (int i = originalSize; i < temp.length; i++)
				{
					try
					{
						Thread.sleep(500);
					}
					catch (InterruptedException e)
					{
						//do nothing
					}
					knighttour.add(temp[i]);
					repaint();
				}
				startButton.setEnabled(true);
			}
		}
		private ArrayList<Dimension> getNextPossiblePositions(Dimension d)
		{
			Dimension[] surrounding = new Dimension[8];
			surrounding[0] = new Dimension(d.width - 2, d.height - 1);
			surrounding[1] = new Dimension(d.width - 2, d.height + 1);
			surrounding[2] = new Dimension(d.width + 2, d.height - 1);
			surrounding[3] = new Dimension(d.width + 2, d.height + 1);
			surrounding[4] = new Dimension(d.width - 1, d.height - 2);
			surrounding[5] = new Dimension(d.width - 1, d.height + 2);
			surrounding[6] = new Dimension(d.width + 1, d.height - 2);
			surrounding[7] = new Dimension(d.width + 1, d.height + 2);
			ArrayList<Dimension> next = new ArrayList<Dimension>();
			for (Dimension temp : surrounding)
			{
				if (temp.width >=0 && temp.width < 8 &&
						temp.height >= 0 && temp.height < 8)
				{
					boolean exist = false;
					for (Dimension di : knighttour)
					{
						if (di.equals(temp)) exist = true;
					}
					if (exist == false) next.add(temp);
				}
			}
			return next;
		}
		private void getNextPosition(ArrayList<Dimension> next)
		{
			Dimension nextPosition = next.get(0);
			int degree = 8;
			for (Dimension d : next)
			{
				ArrayList<Dimension> temp = getNextPossiblePositions(d);
				if (temp.size() < degree && temp.size() > 0)
				{
					nextPosition = d;
					degree = temp.size();
				}
			}
			knighttour.add(nextPosition);
		}
	}
    
    public void paintComponent(Graphics g)
    {
        super.paintComponent(g);
        setBackground(Color.GRAY);
        Graphics2D g2 = (Graphics2D) g;

        for(int i = 1; i <= 8; i++)
            for(int j = 1; j <= 8; j++)
            {
                if((i+j) % 2 == 0)
                    g2.setPaint(Color.RED);
                else
                    g2.setPaint(Color.WHITE);

                Rectangle2D rect = new Rectangle2D.Double(j * WIDTH,i * HEIGHT,WIDTH,HEIGHT);
                g2.fill(rect);
                
            }
        
		g2.setPaint(Color.BLACK);
		Dimension d;
		Font f = new Font("Serif", Font.BOLD, 20);
		g2.setFont(f);
		for (int i = 0; i < knighttour.size(); i++)
		{
			d = knighttour.get(i);
			g2.drawString((i + 1) + "", (d.width + 1) * WIDTH + 35, 
					(d.height + 1) * HEIGHT + 30);
		}
		if (knighttour.size() > 0)
		{
			d = knighttour.get(knighttour.size() - 1);
			g2.drawImage(img, (d.width + 1) * WIDTH,
					(d.height +1) * HEIGHT + 10, null);
		}
    }
    private static final int WIDTH = 60;
    private static final int HEIGHT = 60;
}