import java.util.Scanner;
import java.util.Random;
import java.io.*;

public class GridThread
{
   static int     nTrials = 0;
   static boolean DEBUG   = false;

/**
 * Main program allows for either command-line arguments or user dialog
 * to determine the number of queens and the number of parallel threads
 * to work on the problem.
 */
   public static void main ( String[] args ) throws Exception
   {
      Scanner console = new Scanner(System.in);
      int[]  solution;
      long   start;
      double elapsed;
      int    nQueens;
      int    thread, nThreads;
      PrintWriter outFile = null;
      ComputeEngine[] worker;

      System.out.print ("Number of queens:   ");
      if ( args.length < 1 )
         nQueens = console.nextInt();
      else
      {  nQueens = Integer.parseInt(args[0]);
         System.out.println(nQueens);
      }

      System.out.print ("Number of threads:  ");
      if ( args.length < 2 )
         nThreads = console.nextInt();
      else
      {  nThreads = Integer.parseInt(args[1]);
         System.out.println(nThreads);
      }

      // Timed computation of ONE solution:

      start = System.currentTimeMillis();

      ComputeEngine.nQueens = nQueens;
      worker = new ComputeEngine[nThreads];
      for (thread = 0; thread < nThreads; thread++)
         worker[thread] = new ComputeEngine();
      for (thread = 0; thread < nThreads; thread++)
         worker[thread].start();
      worker[0].join(); // ALL threads terminate when a solution is found

      for (thread = 0; thread < nThreads; thread++ )
         nTrials += worker[thread].nTrials;
      solution = ComputeEngine.solution;

      elapsed = System.currentTimeMillis() - start;

      if ( valid(solution, nQueens) )
         System.out.println("Valid solution found in " +
            elapsed + " msec.");
      else
         System.out.println("ERROR --- invalid solution took " +
            (System.currentTimeMillis() - start) + " msec.");
      System.out.println (nTrials + " passes required.");
   }

// Verify (or reject) the validity of the board of indicated size.
   static public boolean valid( int[] board, int size )
   {
      int row, nxt, k;
      // Take advantage of initialization to false
      boolean[] diagChk = new boolean[2*size-1],
                antiChk = new boolean[2*size-1];

//    mark (0, board[0], true);
      diagChk[0-board[0]+size-1] = true;
      antiChk[0+board[0]] = true;

      for ( row = 1; row < size; row++ )
         if ( (diagChk[row-board[row]+size-1]||antiChk[row+board[row]]) )
            return false;
         else
//          mark (row, board[row], true);
            diagChk[row-board[row]+size-1] =
               antiChk[row+board[row]] = true;
      return true;
   }

   /**
    * The class of compute engines to find a solution.
    */
   private static class ComputeEngine extends Thread
   {
      static int[] solution = null;
      static int   nQueens;       // This is set by the main
      static boolean DEBUG = false;
      Random generator = new Random
         ( this.hashCode() * System.currentTimeMillis() );
      int nTrials = 0;

   // The big kahuna --- all the work is done here
      public void run()
      {
         if ( DEBUG )
            System.out.println ("Started thread " + this.hashCode());
         gridSearch(nQueens);
      }

      void gridSearch(int n)
      {
         int[] solution = new int[n];
         boolean fail = true;

         while ( fail )
         {
            boolean[][]blocked = new boolean[n][n];   // Initially all false
            int row, col, k, d;

            nTrials++;

            for ( row = 0; row < n; row++ )
            {
               col = generator.nextInt(n);
               for ( k = 0; blocked[row][col] && k < n ; k++ )
                  col = (col+1) % n;
               if ( blocked[row][col] )
                  break;
               solution[row] = col;
               for ( k = row; k < n; k++ )
               {
                  blocked[k][col] = true;
                  // row - col
                  d = k - (row - col);
                  if ( d >= 0 && d < n )
                     blocked[k][d] = true;
                  // row + col
                  d = (row + col) - k;
                  if ( d >= 0 && d < n )
                     blocked[k][d] = true;
               } // end for k
            } // end for row
            fail = row < n;
            // Break out as soon as SOMEONE has found a solution
            if ( ComputeEngine.solution != null )
            {
               if ( DEBUG )
                  System.out.println("Thread terminating; solution found elsewhere.");
               break;
            }
         } // end while fail
         if ( ComputeEngine.solution == null )
            ComputeEngine.solution = solution;
      }
   } // end class ComputeEngine
}