/***********************************************************************
  Dackral Phillips
  COMP 7600 - Artificial Intelligence
  Dr. Dozier
  Final Project
  Feb. 27, 2K2

  Description:  This project deals with how to solve
                N-queens problem.  It uses six different
					 methods to solve the problem, O(N),
                modified backtracking algorithm,
					 arc consistent look ahead, next and steepest 
                ascent hill climbing, and genetic sean
rch 
                algorithms.
  Board.java:   This java file defines the board class and is
                also the main file used to solve my 
                implementation of the N-Queens problem.  It
                includes 3 variables: n, which is the dimension
                of the chessboard, the matrix array, which is 
                a 2D array of chess board squares, and the 
                queen array, which is a 1D array containing
                n queens.
***********************************************************************/


   import java.io.*;				// Let me print some stuff!
   import java.util.Random; 	// I need some pseudorandom numbers too
   import ChessSquare; 			// Yank in the stuff I created!
   import Queen;

	// Begin the Board class definition

    public class Board
   {
   
   	// Make me some variables!
   
      private int n;
      private ChessSquare[][] matrix;
      private Queen[] queen;
   
   	// Default Constructor - creates a board of size 4
   
       public Board()
      {
         n = 4;
         matrix = new ChessSquare[n][n];
         queen = new Queen[n];
      
         for (int i = 0; i < n; i++)
         {
            for (int j = 0; j < n; j++)
            {
               matrix[j][i] = new ChessSquare();
            }
            queen[i] = new Queen(n);
         }
      }
   
   	// Constructor - creates a board of size n
   
       public Board(int squares)
      {
         n = squares;
         matrix = new ChessSquare[n][n];
         queen = new Queen[n];
      
         for (int i = 0; i < n; i++)
         {
            for (int j = 0; j < n; j++)
            {
               matrix[j][i] = new ChessSquare();
            }
            queen[i] = new Queen(n);
         }
      }
   
   	// A queen has been placed on this spot, so mark the squares she endangers
   
       public void createLinesOfForce(int x, int y)
      {
         int tempx;
         int tempy;
      
         for (int i = 0; i < n; i++)
         {
            matrix[i][y].checkSquare();
         }
      
         for (int j = 0; j < n; j++)
         {
            matrix[x][j].checkSquare();
         }
      
         tempx = x - 1;
         tempy = y - 1;
      
         while (tempx >= 0 && tempy >= 0)
         {
            matrix[tempx][tempy].checkSquare();
            tempx--;
            tempy--;
         }
      
         tempx = x + 1;
         tempy = y - 1;
      
         while (tempx < n && tempy >= 0)
         {
            matrix[tempx][tempy].checkSquare();
            tempx++;
            tempy--;
         }
      
         tempx = x - 1;
         tempy = y + 1;
      
         while (tempx >= 0 && tempy < n)
         {
            matrix[tempx][tempy].checkSquare();
            tempx--;
            tempy++;
         }
      
         tempx = x + 1;
         tempy = y + 1;
      
         while (tempx < n && tempy < n)
         {
            matrix[tempx][tempy].checkSquare();
            tempx++;
            tempy++;
         }
      }
   
   	// The queen has been removed from (x,y) so undo the danger she caused
   
       public void removeLinesOfForce(int x, int y)
      {
         int tempx;
         int tempy;
      
         for (int i = 0; i < n; i++)
         {
            matrix[i][y].unCheckSquare();
         }
      
         for (int j = 0; j < n; j++)
         {
            matrix[x][j].unCheckSquare();
         }
      
         tempx = x - 1;
         tempy = y - 1;
      
         while (tempx >= 0 && tempy >= 0)
         {
            matrix[tempx][tempy].unCheckSquare();
            tempx--;
            tempy--;
         }
      
         tempx = x + 1;
         tempy = y - 1;
      
         while (tempx < n && tempy >= 0)
         {
            matrix[tempx][tempy].unCheckSquare();
            tempx++;
            tempy--;
         }
      
         tempx = x - 1;
         tempy = y + 1;
      
         while (tempx >= 0 && tempy < n)
         {
            matrix[tempx][tempy].unCheckSquare();
            tempx--;
            tempy++;
         }
      
         tempx = x + 1;
         tempy = y + 1;
      
         while (tempx < n && tempy < n)
         {
            matrix[tempx][tempy].unCheckSquare();
            tempx++;
            tempy++;
         }
      }
   
   	// Place a queen on coordinate (x,y)
   
       public void placeQueen(int x, int y)
      {
         matrix[x][y].placeQueen();
         queen[x].setQueen(x, y);
         createLinesOfForce(x, y);
      }
   
   	// Remove a queen from coordinate (x,y)
   
       public void removeQueen(int x, int y)
      {
         matrix[x][y].removeQueen();
         queen[x].removeQueen(x,y);
         removeLinesOfForce(x, y);
      
         // Removing a queen might have screwed up my lines of force
         // So go through and place all the queens again.
      
         for (int i = 0; i < n; i++)
         {
            if (queen[i].getPlaced())
            {
               placeQueen(queen[i].getX(), queen[i].getY());
            }
         }
      }
   
     // Have we found a solution yet?
   
       public boolean isSolution()
      {
         boolean flag = false;
      
         for (int i = 0; i < n; i++)
         {
            if (queen[i].getPlaced())
            {
               flag = true;
            }
            else 
            {
               flag = false;
               break;
            }
         }
         return flag;
      }
   
   	// Fill the free array with available squares
   
       public void fillFree(int row)
      {
         int index = 1;
         queen[row].resetFree();
         for (int i = 0; i < n; i++)
         {
            if (!(matrix[row][i].getChecked()))
            {
               queen[row].setFree(index, i);
               index++;
            }
         }
      }
   
      // Let's make some whoopie! 
   
       public int[] whoopie(int[] daddy, int[] mommy)
      {
         final double MUTATEFACTOR = 0.1;
         Random Randomizer = new Random();
         int[] child = new int[(n + 1)];
      
         for (int i = 0; i < n; i++)
         {
            if(Randomizer.nextBoolean())
            {
               child[i] = daddy[i];
            }
            else
            {
               child[i] = mommy[i];
            }
         
            // Cause random mutation 10% of the time
         
            if (Randomizer.nextDouble() <= MUTATEFACTOR)
            {
               child[i] = Randomizer.nextInt(n);
            }
         }
         child[n] = fitness(child);
         return child;
      }
   
      // How fit is the chessboard?  Based on how many queen conflicts are produced
   
       public int fitness(int[] board)
      {
         int conflicts = 0;
         int index = 0;
      
         for (int i = 0; i < n; i++)
         {
            index = board[i];
            for (int j = 0; j < n; j++)
            {
               if (i != j)
               {
                  placeQueen(j, board[j]);
                  if(matrix[i][index].getChecked())
                  {
                     conflicts++;
                  }
                  removeQueen(j, board[j]);
               }
            }
         }
         return conflicts;
      }
   
      // Creates a board from a genetically created array
   
       public void createBoardFromArray(int[] array)
      {
         for (int i = 0; i < n; i++)
         {
            placeQueen(i, array[i]);
         }
      }
   
   	// O(N) solution to the problem
   
       public void orderN()
      {
         // This solution is based on an article that appeared in ACM SIGART Bulletin Vol. 2(2) on page 7,
         // which shows that the N-Queens problem can be divided into boards of 3 different types:
         //      - Odd Boards
         //      - Even boards of the type (n % 6 = 2)
         //      - All other even boards
         // The source code has been adapted from a Java applet located on the web at 
         //      - http://www.apl.jhu.edu/~hall/NQueens.html
         // The source code for the applet is available at 
         //      - http://www.apl.jhu.edu/~hall/java/NQueens.java
         // I modified the code by relying on the Java modulus operator rather than computing 
         // the modulus by a function that does repeated division as on the source code listed above.
         // I also adapted it so that it would print out the way I want it to.
      
         int row = 1;
      
         if ((n % 2 == 0) && (n % 6 != 2))
         {
            while(row <= (n/2))
            {
               placeQueen((row - 1), ((row * 2) - 1));
               row++;	
            }
         
            while(row <= n)
            {
               placeQueen((row - 1), (2 * row - n - 2));
               row++;
            }
         }
         else if (n % 2 == 0)
         {
            placeQueen(0, ((2 + n / 2 - 3) % n));
            while(row < (n/2))
            {
               placeQueen(row, ((2* (row + 1) + n / 2 - 3) % n));
               row++;
            }
         
            while(row < n)
            {
               placeQueen(row, (((2 * (n - row +1) + 1) + n / 2 - 3) % n));
               row++;
            }
         }
         else
         {            
            n--;
            if ((n % 2 == 0) && (n % 6 != 2))
            {
               while(row <= (n/2))
               {
                  placeQueen((row - 1), ((row * 2) - 1));
                  row++;	
               }
            
               while(row <= n)
               {
                  placeQueen((row - 1), (2 * row - n - 2));
                  row++;
               }
               n++;
               placeQueen((row - 1), (n-1));
            }
            else if (n % 2 == 0)
            {
               placeQueen(0, ((2 + n / 2 - 3) % n));
               while(row < (n/2))
               {
                  placeQueen(row, ((2* (row + 1) + n / 2 - 3) % n));
                  row++;
               }
            
               while(row < n)
               {
                  placeQueen(row, (((2 * (n - row +1) + 1) + n / 2 - 3) % n));
                  row++;
               }
               n++;
               placeQueen(row, (n-1));
            }
         }
      }
   
   	// Backtracking with some work saved on the first queen placement
   
       public int modifiedBacktrack()
      {
         int Square;
         int backtracks = 0;
         int row = 0;
         int column = 0;
      
      
      	// Test my hypothesis: There is always a solution to an n-queens problem when 
      	// first queen is placed directly in the middle of a given rank on the first
      	// file.  So, find the middle of the file and put a queen there.  Then increment 
         // the row.
      
         if (n % 2 == 0)
            Square = n / 2;
         else
            Square = (n + 1) / 2;
      
         placeQueen(row, Square);
         row++;
      
      	// Now, place the other queens accordingly.  For boards where n < 6
      	// A solution is generated on the first try.
      
         while (! (isSolution()))
         {
            if (column < n)
            {
               if (matrix[row][column].getChecked())
               {
                  column++;
               }
               else
               {
                  placeQueen(row, column);
                  row++; 
                  column = 0;
               }
            }
         
         // No empty square found!  Backtrack time.
         
            if (column >= n)
            {
               row--;
               if (row > -1)
               {
                  column = queen[row].getY();
                  removeQueen(row, column);
                  column++;
                  backtracks++;
               }
            }
         }
         return backtracks;
      }
   
     // Simple Backtracking coupled with steps to place queens on the board faster
     // via arc consistent look ahead
   
       public int lookAhead()
      {
         int Square = 0;
         int backtracks = 0;
         int row = 0;
         int column = 0;
         boolean flag = true;
      
      	// Save some time by placing the first queen correctly
      
         if (n % 2 == 0)
            Square = n / 2;
         else
            Square = (n + 1) / 2;
      
         placeQueen(row, Square);
         row++;
         fillFree(row);
      
      	// Now, place the other queens accordingly.  For boards where n < 6
      	// A solution is generated on the first try.
      
         while (! (isSolution())) // (row < n)
         {
            Square = queen[row].getFree();
         
            if (Square == -1)
            {
               flag = true;
            }
            else
            {
               placeQueen(row, Square);
               flag = false;
            }
         
            if (flag)
            {
               row--;
               removeQueen(row, queen[row].getY());
               backtracks += 1;
            }
            else
            {
               row++;
               if ((row < n) && (row > -1))
               {
                  fillFree(row);
               }
            }
         }
         return backtracks;
      }
   
      // Next Ascent Hill Climbing algorithm to solve the problem
      // An iteration does not occur until a child becomes a new parent
   
       public long nextHillClimb()
      {
         Random Randomizer = new Random();
         long iterations = 0;
         int row = 0;
         int index = 0;
         int unStickIndex = 0;
         int[] parent = new int[(n + 1)];
         int[][] child = new int[(n * 2)][(n + 1)];
         boolean solved = false;
      
         // Initialize the parent
         for (int i = 0; i < n; i++)
         {
            parent[i] = Randomizer.nextInt(n);
         }
         parent[n] = fitness(parent);
      
         while (!(solved))
         {
            // Initialize all the children to be the same as the parent
         
            for (int j = 0; j < (n * 2); j++)
            {
               for (int k = 0; k < n; k++)
               {
                  child[j][k] = parent[k];
               }
               child[j][n] = fitness(child[j]);
            }
         
            for (int l = 0; l < (n * 2); l++)
            {
               if (parent[n] == 0)
               {
                  solved = true;
                  break;
               }
            
               // Find all children that are one addition apart from the parent
               if (l < n)
               {
                  child[l][row] += 1;
                  if (child[l][row] >= n)
                  {
                     child[l][row] = 0;
                  }
               }
               
               // Find all children that are one subtraction apart from the parent
               
               else
               {
                  child[l][row] -= 1;
                  if (child[l][row] <= 0)
                  {
                     child[l][row] = n - 1;
                  }
               }
            
               // Check the fitness of the child
            
               child[l][n] = fitness(child[l]);
            
               // if the child is better, make it the new parent
            
               if (child[l][n] < parent[n])
               {
                  for (int m = 0; m <= n; m++)
                  {
                     parent[m] = child[l][m];
                  }
               
                  // reset the row to start from scratch
               
                  row = 0;
               
                  // Is the child a solution?
               
                  if (child[l][n] == 0)
                  {
                     solved = true;
                     index = l;
                  }
                  break;
               }
            
               // Reset the row if it has reached the end of the board
               // increment otherwise
            
               if (row >= n)
               {
                  row = 0;
               }
               else
               {
                  row++;
               }
            
            // Check to see if we're stuck at a local maximum
            
               if ((l >= ((n * 2) - 1)) && (child[l][n] >= parent[n]))
               {
                  // Attempt #1: Multiply the parent fitness by a random number between 1 and n to break out
               
                  // parent[n] = parent[n] * (Randomizer.nextInt(n) + 1); 
               
                  // Attempt #2: Multiply the parent fitness by two to break out (simpler)
               
                  // parent[n] = parent[n] * 2; 
               
                  // Attempt #3: Choose Random Child
               
                  unStickIndex = Randomizer.nextInt(n);
               
                  for (int m = 0; m <= n; m++)
                  {
                     parent[m] = child[unStickIndex][m];
                  }
               }
            }
            iterations++;
         }
      
         // Print out the solution
      
         if(child[index][n] == 0)
         {
            createBoardFromArray(child[index]);
         }
         else
         {
            createBoardFromArray(parent);
         }
         return iterations;
      }
   
      // Steepest Ascent Hill Climbing algorithm to solve the problem
      // An iteration does not occur until a child becomes a new parent
   
       public long steepHillClimb()
      {
         Random Randomizer = new Random();
         long iterations = 0;
         int row = 0;
         int index = 0;
         int[] parent = new int[(n + 1)];
         int[][] child = new int[(n * 2)][(n + 1)];
         int bestChildIndex = -1;
         int bestChildFitness = 0;
         int unStickIndex = 0;
         boolean solved = false;
      
         // Initialize the parent
         for (int i = 0; i < n; i++)
         {
            parent[i] = Randomizer.nextInt(n);
         }
         parent[n] = fitness(parent);
      
         //System.out.print("DEBUG! Parent: "); printArray(parent);
      
         while (!(solved))
         {
            // Set the fitness of the best Child to the parent initially
         
            bestChildFitness = parent[n];
         
            // Set the index to a bogus value
         
            bestChildIndex = -1;
         
            // Initialize all the children to be the same as the parent
         
            for (int j = 0; j < (n * 2); j++)
            {
               for (int k = 0; k < n; k++)
               {
                  child[j][k] = parent[k];
               }
               child[j][n] = fitness(child[j]);
            }
         
            for (int l = 0; l < (n * 2); l++)
            {
               if (parent[n] == 0)
               {
                  solved = true;
                  break;
               }
            
               // Find all children that are one addition apart from the parent
               if (l < n)
               {
                  child[l][row] += 1;
                  if (child[l][row] >= n)
                  {
                     child[l][row] = 0;
                  }
               }
               
               // Find all children that are one subtraction apart from the parent
               
               else
               {
                  child[l][row] -= 1;
                  if (child[l][row] <= 0)
                  {
                     child[l][row] = n - 1;
                  }
               }
            
            
               // Check the fitness of the child
            
               child[l][n] = fitness(child[l]);
            
               //System.out.print("DEBUG! Child: "); printArray(child[l]);
            
               // Find the best child
            
               if (child[l][n] < bestChildFitness)
               {
                  bestChildFitness = child[l][n];
                  bestChildIndex = l;
                  //System.out.print("DEBUG! Best Child: "); printArray(child[l]);
               }
            
               // Reset the row if it has reached the end of the board
               // increment otherwise
            
               if (row >= n)
               {
                  row = 0;
               }
               else
               {
                  row++;
               }
            }
            if (bestChildIndex != -1)
            {
               for (int m = 0; m <= n; m++)
               {
               
                  parent[m] = child[bestChildIndex][m];
               }
               //System.out.print("DEBUG! New Parent: "); printArray(parent);
            }
            else
            {
               // Attempt #1: Multiply the parent fitness by a random number between 1 and n to break out
            
               // parent[n] = parent[n] * (Randomizer.nextInt(n) + 1); 
            
               // Attempt #2: Multiply the parent fitness by two to break out (simpler)
            
               // parent[n] = parent[n] * 2; 
            
               // Attempt #3: Choose Random Child
            
               unStickIndex = Randomizer.nextInt(n);
            
               for (int m = 0; m <= n; m++)
               {
                  parent[m] = child[unStickIndex][m];
               }
            }
         
            // Is the child a solution?
         
            if (parent[n] == 0)
            {
               solved = true;
               index = bestChildIndex;
            }
         
            // reset the row to start from scratch
         
            row = 0;
         
            // Increment the iterations that have elapsed
         
            iterations++;
         }
      
         // Print out the solution
      
         if(child[index][n] == 0)
         {
            createBoardFromArray(child[index]);
         }
         else
         {
            createBoardFromArray(parent);
         }
         return iterations;
      }
   
      // Solution applying Darwinian survival of the fittest strategy
      // 2n parents are randomly created.  Mating occurs between two
      // random parents.  The worst parent is replaced by a better child.
   
       public long geneticSearch()
      {
         // Make me some variables!
      
         Random Randomizer = new Random();
         int[][] parent = new int[(n * 2)][(n + 1)];
         int[] child = new int[(n + 1)];
         long generations = 0;
         int worstChildIndex = 0;
         int bestChildIndex = 0;
         boolean solved = false;
      
         // Randomly initialize the parents
      
         for (int i = 0; i < (n * 2); i++)
         {
            for (int j = 0; j < n; j++)
            {
               parent[i][j] = Randomizer.nextInt(n);
            }
            parent[i][n] = fitness(parent[i]);
         }
      
         while (!(solved))
         {
         
         // Check for the best, next best, and worst parents
         
            for (int k = 0; k < n; k++)
            {
               if (parent[k][n] > parent[worstChildIndex][n])
               {
                  worstChildIndex = k;
               }
            
               if (parent[k][n] < parent[bestChildIndex][n])
               {
                  bestChildIndex = k;
                  if (parent[bestChildIndex][n] == 0)
                  {
                  // We found a solution!
                     solved = true;
                     createBoardFromArray(parent[bestChildIndex]);
                     break;
                  }
               }
            }
         
            // Let's have a child with two random parents
         
            child = whoopie(parent[Randomizer.nextInt((n * 2))], parent[Randomizer.nextInt((n * 2))]);
         
            // We found a solution!
         
            if (child[n] == 0)
            {
               solved = true;
            }
         
            // If the child is fitter than the worst of the bunch, replace it
         
            if (child[n] < parent[worstChildIndex][n])
            {
               for (int i = 0; i <= n; i++)
               {
                  parent[worstChildIndex][i] = child[i];
               }
            }   
            generations++;
         }
      
         // Print the solution
      
         if (child[n] == 0)
         {
            createBoardFromArray(child);
         }
         else
         {
            createBoardFromArray(parent[bestChildIndex]);
         }
      
         return generations;
      }
   
      // A method for printing a board in array form.  Used for debugging purposes.
   
       public void printArray(int[] myArray)
      {
         System.out.print("DEBUG! ");
         for (int i = 0; i < myArray.length; i++)
         {
            System.out.print(myArray[i] + " ");
         }
         System.out.println();
      }
   
      // Print out the board state
   	// q = Queen
   	// 1 = Square is in danger
   	// 0 = Square is safe
   
       public String toString()
      {
         String print = new String(n + " Queen Problem Board Layout:\n\n");
      
         for (int i = 0; i < n; i++)
         {
            for (int j = 0; j < n; j++)
            {
               if ( matrix[j][i].getQueenOn())
                  print = print + "q ";
               else if ( matrix[j][i].getChecked())
                  print = print + "1 ";
               else 
                  print = print + "0 ";
            }
         
            print = print + "\n";
         }
         return print;
      }
   
   	// N-Queens driving engine
   
       public static void main(String[] args) throws IOException
      {
         int squares;        // board dimensions
         int method;			  // Method used to solve the problem
         char again;
         Board chessboard;
         int backtracks = 0;
         long generations = 0;
         BufferedReader kbd;
      
         // Allow the user to select how many queens to use and provide a menu system
         // giving the user the choice of which method to use to solve the problem.
      
         do
         {
            kbd = new BufferedReader(new InputStreamReader(System.in));
         
            System.out.print("\n\nHow many queens do you want to use? ");
            squares = Integer.valueOf(kbd.readLine()).intValue();
            System.out.println("\n\nN Queens Menu\n");
            System.out.println("1) O(N) Solution");
            System.out.println("2) Modified Bactracking Search");
            System.out.println("3) Arc Consistent Look Ahead Search");
            System.out.println("4) Next Ascent Hill Climbing Search");
            System.out.println("5) Steepest Ascent Hill Climbing Search");
            System.out.println("6) Genetic Search");
            System.out.print("\nHow would you like to solve the problem? ");
            method = Integer.valueOf(kbd.readLine()).intValue();
         
            // Solve the problem already!
         
            // create a new board
         
            chessboard = new Board(squares);	
         
            switch (method)
            {
               case 1:
                  chessboard.orderN();
               
               // Let me see the solution!
               
                  System.out.println("O(N) Runtime Algorithm\n" + chessboard +"\n");
                  break;
            
               case 2:
                  backtracks = chessboard.modifiedBacktrack();
               
               // Let me see the solution!
               
                  System.out.println(chessboard + "\nBacktracks: " + backtracks + "\n");
                  break;
            
               case 3:
                  backtracks = chessboard.lookAhead();
               
               // Let me see the solution!
               
                  System.out.println(chessboard + "\nBacktracks: " + backtracks + "\n");
                  break;
            
               case 4:      
                  generations = chessboard.nextHillClimb();
               
               // Let me see the solution!
               
                  System.out.println(chessboard + "\nIterations: " + generations + "\n");
                  break;
               case 5:      
                  generations = chessboard.steepHillClimb();
               
               // Let me see the solution!
               
                  System.out.println(chessboard + "\nIterations: " + generations + "\n");
                  break;
               case 6:
                  generations = chessboard.geneticSearch();
               
               // Let me see the solution!
               
                  System.out.println(chessboard + "\nGenerations: " + generations + "\n");
                  break;
            
               default:
                  System.out.println("\nInvalid Choice!\n");
            }
            System.out.print("\nWould you like to run the program again (Y,y/N,n)? ");
            again = (char) kbd.read();
         } while (again == 'y' || again == 'Y');
      }
   }	// End of class definition