package Search;

import java.util.*;
import java.util.Random;
import java.lang.Math;

public class NKPuzzle implements SearchState {

  protected NKPuzzle () {
  }

  public NKPuzzle(int x, int y) {
    Xdim = x; Ydim = y; ex = x-1; ey = y-1;
    nrOfTiles = (Xdim*Ydim)-1;
    thePuzzle = new int[Xdim][Ydim];
    int tn = 1;
    for (int yp=0; yp<Ydim; yp++)
      for (int xp=0; xp<Xdim; xp++)
	thePuzzle[xp][yp] = tn++;
    thePuzzle[Xdim-1][Ydim-1] = 0;
  }

  public NKPuzzle clone(int exDiff, int eyDiff) {
    NKPuzzle res = new NKPuzzle();
    res.Xdim = Xdim; res.Ydim = Ydim; 
    res.ex = ex+exDiff; res.ey = ey+eyDiff;
    res.nrOfTiles = nrOfTiles;
    res.thePuzzle = new int[Xdim][Ydim];
    for (int yp=0; yp<Ydim; yp++)
      for (int xp=0; xp<Xdim; xp++)
	res.thePuzzle[xp][yp] = thePuzzle[xp][yp];
    res.thePuzzle[ex][ey] = thePuzzle[res.ex][res.ey];
    res.thePuzzle[res.ex][res.ey] = 0;
    return res;
  }

  public void randomInit() {
    for (int yp=0; yp<Ydim; yp++)
      for (int xp=0; xp<Xdim; xp++)
	thePuzzle[xp][yp] = -1;
    Random r = new Random();

    for (int tn=nrOfTiles; tn>=0; tn--) {
      boolean tAssigned = false;
      while (! tAssigned) {
	ex = java.lang.Math.abs(r.nextInt()%Xdim);
	ey = java.lang.Math.abs(r.nextInt()%Ydim);
	if (thePuzzle[ex][ey] == -1) {
	  thePuzzle[ex][ey] = tn;
	  tAssigned = true;
	}
      }
    }
  }

  public boolean isGoalState() {
    int tn = 1;
    for (int yp=0; yp<Ydim; yp++)
      for (int xp=0; xp<Xdim; xp++)
	if ((tn <= nrOfTiles) && (thePuzzle[xp][yp] != tn++))
	  return false;
    return true;
  }

  public Vector getSuccessors() {
    Vector res = new Vector();
    // move the empty tile up:
    if (ey > 0)
      res.addElement(clone(0,-1));
    // move the empty tile right:
    if (ex < Xdim-1)
      res.addElement(clone(1,0));
    // move the empty tile down:
    if (ey < Ydim-1)
      res.addElement(clone(0,1));
    // move the empty tile left:
    if (ex > 0)
      res.addElement(clone(-1,0));
    return res;
  }

  public boolean equals(Object otherState) {
    int[][] otherPuzzle = ((NKPuzzle)otherState).thePuzzle;
    for (int yp=0; yp<Ydim; yp++)
      for (int xp=0; xp<Xdim; xp++)
	if (thePuzzle[xp][yp] != otherPuzzle[xp][yp])
	  return false;
    return true;
  }

  public String toString() {
    String res = "";
    for (int yp=0; yp<Ydim; yp++) {
      for (int xp=0; xp<Xdim; xp++)
	res += tileName(thePuzzle[xp][yp]) + " ";
      res += '\n';
    }
    return res;
  }

  static private String tileName(int n) {
    if (n == 0)
      return "__";
    return "T" + n;
  }

  static public void main(String[] args) {
    if (args.length != 2) {
      System.out.println("Error: Two integer arguments expected!");
      return;
    }
    try {
      int xdim = (new Integer(args[0])).intValue();
      int ydim = (new Integer(args[1])).intValue();
      if ((xdim < 1) || (ydim < 1))
	throw new NumberFormatException();
      // create a ramdom puzzle and try to solve it:
      NKPuzzle aPuzzle = new NKPuzzle(xdim, ydim);
      aPuzzle.randomInit();
      USearcher nkps = new USearcher(aPuzzle);
      //nkps.setTraceStream(System.out);
      nkps.setSearchLimit(10000);
      //nkps.searchDepthFirst();
      nkps.setRepeatTestLevel(1);
      if (nkps.search())
	System.out.println("Puzzle solved!");
      else
	System.out.println("Puzzle not solved!");
    } catch (NumberFormatException nfe) {
      System.out.println("Error: Arguments must be positive integers!");
    }
  }

  private int Xdim, Ydim, ex, ey, nrOfTiles;
  private int[][] thePuzzle;
}
