Knights Tour

Nicholas Duchon: Mar 31, 2017

Key Concepts:

  • Basic scrolling drawing applet


Image:



Code:

import javax.swing.JFrame;
import javax.swing.JApplet;
import javax.swing.JScrollPane;
import javax.swing.JPanel;
import javax.swing.JComponent;

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;

import java.util.ArrayList;

public class BasicScrollingDrawingApplet extends JApplet {
  final static int FRAME_SIZE = 350;
  final static int DRAW_SIZE  = 500;
  JPanel jd = new JPanel ();
 
  public BasicScrollingDrawingApplet () {}

  public BasicScrollingDrawingApplet (String title) {
    JFrame jf = new JFrame (title);
    jf.add(this); // add applet to JFrame
    jf.setDefaultCloseOperation (JFrame.EXIT_ON_CLOSE);
    jf.setLocationRelativeTo (null);
    jf.setSize (FRAME_SIZE, FRAME_SIZE);
    jf.setVisible (true);
  } // end string constructor
 
  public void init () {
    jd.setBounds (0, 0, DRAW_SIZE, DRAW_SIZE);
    jd.setPreferredSize (new Dimension (DRAW_SIZE, DRAW_SIZE));
    jd.setBackground (Color.yellow);
    jd.setLayout (null);
    JScrollPane jsp = new JScrollPane (jd);
    add (jsp, BorderLayout.CENTER);
 
} // end applet method init
 
  public void start () {
    jd.add (new ChessBoard ());
    repaint ();
 
} // end start
 
  public static void main (String args []) {
    BasicScrollingDrawingApplet kt = new BasicScrollingDrawingApplet ("My Tour");
    kt.init ();
    kt.start ();
 
} // end main
} // end class KnightsTour

class ChessBoard extends JComponent {
  int size = 30, offset = 10;
  Cell [][] board = new Cell [8][8];
  ArrayList < Cell > path = new ArrayList < Cell > ();
  static int countP = 0, countE = 0, countC = 0;
 
  public ChessBoard () {
    setBounds (0, 0, 500, 500);
    for (int i = 0; i < board.length; i++)
      for (int j = 0; j < board [i].length; j++) {
        board [i][j] = new Cell (i, j);
      } // end init each cell
    path.clear ();
    findPath (0, 0, 64); // start coordinates - 0,0 through 7,7
    for (Cell c: path) System.out.println (c);
    System.out.printf ("Count Entries  : %6d\n", countE);
    System.out.printf ("Count Conflicts: %6d\n", countC);
    System.out.printf ("Count Paths    : %6d\n", countP);
 
} // end class ChessBoard
 
  public boolean findPath (int i, int j, int len) {
    countE++;
    if (i < 0 || i > 7 || j < 0 || j > 7) return false;
    countC ++;
    if (path.contains (board[i][j])) return false;

    path.add (board[i][j]);
    countP++;

//    if (countP % 10_000_000 == 0) System.out.printf ("CountP: %,d - i, j: %d, %d\n", countP, i, j);
//    if (countP % 10 == 0) System.out.printf ("CountP: %,d - i, j: %d, %d\n", countP, i, j);

    // max is 64 = all the cells visited
    if (path.size() == len) return true;
   
    // without the following heuristic, the program
    // will run over 900M countP
    // I just quit waiting at that point.
    if (i == 0) {if (findPath (i+1, j+2, len)) return true;}
    if (i == 7) {if (findPath (i-1, j-2, len)) return true;}
    if (j == 0) {if (findPath (i-2, j+1, len)) return true;}
    if (j == 7) {if (findPath (i+2, j-1, len)) return true;}
    if (i == 1) {if (findPath (i-1, j+2, len)) return true;}
    if (i == 6) {if (findPath (i+1, j-2, len)) return true;}
    if (j == 1) {if (findPath (i-2, j-1, len)) return true;}
    if (j == 6) {if (findPath (i+2, j+1, len)) return true;}

    if (findPath (i+1, j-2, len)) return true;
    if (findPath (i-1, j-2, len)) return true;
    if (findPath (i+2, j-1, len)) return true;
    if (findPath (i+2, j+1, len)) return true;
    if (findPath (i+1, j+2, len)) return true;
    if (findPath (i-1, j+2, len)) return true;
    if (findPath (i-2, j+1, len)) return true;
    if (findPath (i-2, j-1, len)) return true;

    path.remove (board[i][j]);
    return false;
 
} // end findPath
 
  public void paintComponent (Graphics g) {
    super.paintComponent (g);
    for (int i = 0; i < 8; i++) {
      for (int j = 0; j < 8; j++) {
        g.setColor ( ((i+j)%2==0)? Color.white : Color.blue);
        g.fillRect (offset + j*size, offset + i*size, size, size);
        g.setColor (Color.black);
        g.drawRect (offset + j*size, offset + i*size, size, size);
      } // end for each box j
    } // end for i
    g.setColor (Color.red);
    for (int i = 1; i < path.size(); i++)
      g.drawLine (path.get(i-1).cx, path.get(i-1).cy, path.get(i).cx, path.get(i).cy);
//     for (int i = 0; i < 8; i++)
//       for (int j = 1; j < 8; j++)
//         g.drawLine (board[i][j-1].cx, board[i][j-1].cy, board[i][j].cx, board[i][j].cy);

 
} // end paintComponent

  class Cell {
    int value, cx, cy, row, col;
    Cell (int i, int j) {
      row = i; col = j;
      cx = offset + (2*j+1) * size / 2;
      cy = offset + (2*i+1) * size / 2;
   
} // int, int constructor
    public String toString () {return row + ", " + col;
}
 
} // end class Cell

} // end class ChessBoard



End.