/*

This is a program that can generate NxN bords for the (NxN-1)-puzzle for Oblig2,
question 2, INF-4130, 2013.  The program should have 4 parameters when run:

1.There are two ways to generate a board;

  If "0" is given here, you get a random board, which will usually be quite
  difficult to solve.

  If a positive number is given you get a board generated by starting at the
  final correct board, and do a number of random draws.  If you give someting
  around "10 you get very easy boards, while e.g. "100" will give more
  difficult ones.

2.Gives the size of the board (along one edge).

3.Gives the name of the output file (use <name>.txt)

4.Givs a "seed" for the random generator.  As long as you use the same seed
  (e.g. "123") with everything else the same, you will get the same bord.

NB: If you find errors, write a mail to "steinkr@ifi.uio.no"

*/


import java.util.*;
import java.io.*;

class GenBoard{

    int N;        // Size of the board

    int[][] A;    // A board

    Random rand;  // Random is a class for generating random numbers (needs a "seed")
    //=========================== Main ==============================

    public static void main(String[]args) {
        new GenBoard().run(args);
    }

    //=============== Parameter-innlesning og utskrift ===============

    void run(String []args ) {
      try{
		int typeGen = Integer.parseInt(args[0]);  // TypeGen=0: Gen.random
		                                          // TypeGen>0: Gen.backwards

        N = Integer.parseInt(args[1]);

        String outfileName = args[2];

        long seed = Long.parseLong(args[3]);
        rand = new Random(seed);

        //------ Generate boards: -------

        if (typeGen>0) {System.out.println("Backwards gen.(Easy)\n"); A = generateBoardSteps(N, typeGen);}
        else           {System.out.println("Random gen. (Difficult)\n"); A = generateBoardRandom(N);}

        //------ Output resulting board: -----

        BufferedWriter outFile = new BufferedWriter(new FileWriter(outfileName));

        outFile.write(""+ N + "\n");
        for (int ii =1; ii<= N; ii++){
          for (int jj = 1; jj <= N; jj++) {outFile.write("" + A[ii-1][jj-1] + "  ");}

          outFile.write("\n");
	    }
        outFile.close();


        System.out.print("Generated Board: \n\n");
        System.out.println(""+ N);
		for (int ii =1; ii<= N; ii++){
		   for (int jj = 1; jj <= N; jj++) { System.out.print(""+A[ii-1][jj-1] + "   ");}
           System.out.print("\n");
	    }

      }
      catch (java.io.IOException iox){ System.out.println("Run"+iox.getMessage());}
    } // end of method run

    //====================  GenerateBoardRandom =================

    int [][] generateBoardRandom(int N){
    int NN=N*N;
	int []   perm     = new int[N*N];
	int [][] genBoard = new int[N][N];

	// Generer en random permutasjon i perm[0:NN-2]
	for (int i = 0; i < NN-1; i++) {  //// Riktig rettet av dere
	    perm[i]= i+1;
	}

	for (int i = 0; i < NN-2; i++) {  //// Rettet fra N-3
	    int j   = i + rand.nextInt(NN-1-i);  //// Rettet fra (NN-2-i)
	    int k   = perm[i];
	    perm[i] = perm[j];
	    perm[j] = k; // Swap i, j
	}

	// Tell inversjoner
	int inv = 0;
	for (int i = 0; i < NN-2; i++) {
	    for (int j = i+1; j <= NN-2; j++) {
		   if (perm[i] > perm[j]) {
		       inv++;
		   }
	    }
	}

        //// Ny og forh?pentligvis riktig test:
	if (inv % 2 != (N/2) % 2){   // Om den er ul?selig, gj?r en swap
	    int k     = perm[0];     //// Like greit bare ? swappe 0 og 1
	    perm[0]   = perm[1];
	    perm[1] = k;
	}

	// Putt inn den tomme p? et tilfeldig sted
	int open = rand.nextInt(NN);    //// Rettet fra NN-1
	for (int j = NN-1; j > open; j--) {
	    perm[j] = perm[j-1];
	}
	perm[open] = 0;

	int k   = 0;
	int odd = 0; // false

	if (N % 2 == 1) { // Sett inn f?rste linje om N er odde
	    odd = 1; // true
	    for (int j = 0; j <= N-1; j++) {  // Forlengs
		genBoard[0][j] = perm[k];
		k++;
	    }
	}

	for (int i = odd; i <= N-2; i = i+2) {

	    for (int j = N-1; j >=0; j--) {  // Baklengs
		genBoard[i][j] = perm[k];
		k++;
	    }

	    for (int j=0; j<=N-1; j++) {  // Forlengs
		genBoard[i+1][j]=perm[k]; k++;
	    }
	}

	return genBoard;
    }

  //==========================  GenerateBoardSteps =========================

  int[][] generateBoardSteps(int N, int steps){ // Steps angir vanskelighetsgrad
    int i, j, k;  // generelle tellere
    int stno;  // Teller p? stegene
    int[][] A = new int[N][N];

    // Fyll opp sluttilstand

    System.out.print("\n" + steps +"\n");

    k = 1;
    for (i=0; i<N; i++) {
	  for (j=0; j<N; j++) {
	      A[i][j]= k; k++;
	  }
    }
    A[N-1][N-1]=0; i=N-1; j=N-1; // i og j brukes heretter til angi tomt felt

    // Gj?r steps tilfeldige trekk
    for (stno=0; stno < steps; stno++) {
	k= rand.nextInt(4);

	   switch (k) {
	   case 0: // left
	           if (j>0) {A[i][j] = A[i][j-1]; A[i][j-1] = 0; j--;}
		       break;
	   case 1: // right
	           if (j<N-1) {A[i][j] = A[i][j+1]; A[i][j+1] = 0; j++;}
		       break;
	   case 2: // up
	           if (i>0) {A[i][j] = A[i-1][j]; A[i-1][j] = 0; i--;}
		       break;
	   case 3: // down
	           if (i<N-1) {A[i][j] = A[i+1][j]; A[i+1][j] = 0; i++;}
		       break;
	   }
    }
    return A;
  } // End of method generateBoardSteps

}   // end of class driver