// Project: Recursion
// Module: knightstour
// Source code file Main.java

// Show solution of the Knights Tour Problem:
// visit every square on an n x n chessboard once.
// A knight makes an L-shaped move.

import javax.swing.*;
import java.awt.*;

public class MyPanel extends JPanel
{
    private int[][] array;
    private int size;
    private boolean done;

    public MyPanel(int s)
    {
        size = s;
        done = false;
        array = new int[size][size];
        initialize();
        search(0, 0, 1);
        repaint();
    }

    public void initialize()
    {
        int x, y;
        for(x = 0; x <= size-1; x++)
            for(y = 0; y <= size-1; y++)
                array[x][y] = -1;
    }

    public void search(int x, int y, int depth)
    {
        if (done)
            return;
        else if (depth == size*size+1)
        {
            done = true;
            return;
        }
        else if (0 <= x && 0 <= y &&
                x < size && y < size &&
                array[x][y] == -1)
        {
            array[x][y] = depth;
            search(x + 2, y + 1, depth + 1);
            search(x + 1, y + 2, depth + 1);
            search(x - 1, y + 2, depth + 1);
            search(x - 2, y + 1, depth + 1);
            search(x - 2, y - 1, depth + 1);
            search(x - 1, y - 2, depth + 1);
            search(x + 1, y - 2, depth + 1);
            search(x + 2, y - 1, depth + 1);
            if (!done)
                array[x][y] = -1;
        }
        return;
    }

    public void paintComponent(Graphics g)
    {
        super.paintComponent(g);

        int x, y, value;
        setBackground(Color.white);
        g.setColor(Color.black);
        Font f = new Font("Courier", Font.BOLD, 16);
        g.setFont(f);
        for(x = 0; x <= 30*size; x += 30) {
            g.drawLine(x, 0, x, 30*size);
        }
        for(y = 0; y <= 30*size; y += 30) {
            g.drawLine(0, y, 30*size, y);
        }
        for(x = 0; x <= size - 1; x++) {
            for(y = 0; y <= size - 1; y++)
            {
                value = array[x][y];
                if (value > 0)
                {
                    if (value < 10)
                        g.drawString(String.valueOf(value),
                                10+30*x, 20+30*y);
                    else
                        g.drawString(String.valueOf(value),
                                5+30*x, 20+30*y);
                }
            }
        }
    }
}