//============================================================================
// http://www.apl.jhu.edu/~hall/java/NQueens.java
//
// Finds a solution to the NQueens problem for any N 4 or greater.
// Requires no search, and solutions are found in constant time per
// queen. So printing the board is the rate-limiting step.
// Taken from algorithm in ACM SIGART Bulletin, Vol 2, Number 2,
// page 7.
//
// 3/96 Marty Hall. marty_hall@jhuapl.edu
//============================================================================

import java.applet.Applet;
import java.awt.*;

public class NQueens extends Applet {
  private int Top=45, Left=20, Board_Width=500, Width,
              Height, N=8; 
  private Label N_Label;
  private Scrollbar N_Slider;
  private TextField N_Value;
  private Button Draw;
  
  //-------------------------------------------------------------------
  
  private boolean Is_Even(int X) {
    return(X == 2*(X/2));
  }

  //-------------------------------------------------------------------
  // First square is red. After that, they alternate red/black.
  
  private Color Pos_Color(int Row, int Col) {
    if ( (Is_Even(Row) && Is_Even(Col)) ||
	 (!Is_Even(Row) && !Is_Even(Col)))
      return(Color.black);
    else
      return(Color.red);
  }

  //-------------------------------------------------------------------
  // I probably need to understand how to use GridBagLayout. But
  // I wasn't too good at controlling the widget layout using the
  // existing layout managers, so I used absolute positioning.
  
  private void Add_Widgets() {
    int L = Board_Width + 2*Left + 5,
        W = Width - L,
        C = L+W/2,
        H = Height,
        T = 10,
        N_Label_Top=T,
        N_Label_Height=20,
        Draw_Button_Top = H-100,
        Draw_Button_Height=80,
	N_Value_Height=30,
	N_Value_Top=Draw_Button_Top-N_Value_Height-20,
        N_Slider_Top=N_Label_Top+N_Label_Height,
        N_Slider_Height=N_Value_Top-N_Slider_Top;

    setLayout(null);  // Turn off layout managers
    
    N_Label = new Label("N (4-60)", Label.CENTER);
    N_Label.reshape(L, N_Label_Top, W, N_Label_Height);
    add(N_Label);

    N_Slider = new Scrollbar(Scrollbar.VERTICAL, 8, 10, 4, 60);
    N_Slider.reshape(L+W/2-10, N_Slider_Top, 20, N_Slider_Height);
    add(N_Slider);

    N_Value = new TextField("8", 2);
    N_Value.setEditable(false);
    N_Value.reshape(C-20, N_Value_Top, 40, N_Value_Height);
    add(N_Value);

    Draw = new Button("Draw");
    Draw.setFont(new Font("Helvetica", Font.BOLD, 20));
    Draw.reshape(L+10, Draw_Button_Top, W-20, Draw_Button_Height);
    add(Draw);
  }

  //-------------------------------------------------------------------

  private void Draw_Title(Graphics G) {
    int Big_Size = Top-5;
    G.setColor(Color.yellow);
    G.setFont(new Font("TimesRoman", Font.BOLD, Big_Size));
    G.drawString("N Queens", Left, Top-10);
    G.setColor(Color.black);
    G.setFont(new Font("TimesRoman", Font.ITALIC, 12));
    G.drawString("http://www.apl.jhu.edu/~hall/java/NQueens.html",
		 Left+Board_Width/2, Big_Size/2+2);
    G.drawString("marty_hall@jhuapl.edu",
		 Left+Board_Width/2, Big_Size-5);
  }
    
  //-------------------------------------------------------------------

  private void Draw_Separator(Graphics G) {
    G.setColor(Color.black);
    G.drawLine(Board_Width+2*Left, 0, Board_Width+2*Left, Height);
  }
  
  //-------------------------------------------------------------------

  private void Draw_Queens(int[] Positions, Graphics G) {
    int Square_Width = Board_Width/N,         // Rounds down
        Char_Width = (Board_Width*4)/(N*5),
        Offset = (Square_Width-Char_Width),   // Rounds down
        Col;
    String Q = "Q";

    G.setFont(new Font("Helvetica", Font.BOLD, Char_Width));
    for (int Row=0; Row<N; Row++) {
      Col = Positions[Row]-1;
      G.setColor(Pos_Color(Row, Col+1));    // Reverse color
      G.drawString(Q, Left + Col*Square_Width + Offset,
		   Top + (Row+1)*Square_Width - Offset);
      }
  }
    
  //-------------------------------------------------------------------
  // Uses the 0-based array indices, not the 1-based board indices.
  
  private void Draw_Board(Graphics G) {
    int Square_Width = Board_Width/N;   // Rounds down

    for(int Row=0; Row<N; Row++)
      for(int Col=0; Col<N; Col++) {
	G.setColor(Pos_Color(Row, Col));
	G.fillRect(Left+Col*Square_Width, Top+Row*Square_Width,
		   Square_Width, Square_Width);
      }
  }

  //-------------------------------------------------------------------
  // Works for any even N except when N is of form 6K+2 (eg N=8,14,20)
  // Since this is simpler than Even_Queens_2, it will be used in
  // the cases when both apply (N even but neither of form 6K+2 nor 6K).
  // Note that the positions are 1-based, but stored in a 0-based array.

  private int[] Even_Queens_1(int N) {
    int[] Positions = new int[N];
    
    // Row 1 to N/2:   Queen on 2*Row
    for(int Row=1; Row<=N/2; Row++) {
      Positions[Row-1] = 2*Row;
    }
    // Row N/2+1 to N: Queen on 2*Row-N-1
    for(int Row=N/2+1; Row<=N; Row++) {
      Positions[Row-1] = 2 * Row - N - 1;
    }
    return(Positions);
  }
  
  //-------------------------------------------------------------------
  // Works for any even N except when N a multiple of 6. Since
  // this is more complicated than Even_Queens_1, it will not be used in
  // the cases when both apply (N even but neither of form 6K+2 nor 6K).
  // Note that the positions are 1-based, but stored in a 0-based array.
  
  private int[] Even_Queens_2(int N) {
    int[] Positions = new int[N];
    
    // Row 1 to N/2:   Queen on Queen_Mod(Row,N) +1
    for(int Row=1; Row<=N/2; Row++) {
      Positions[Row-1] = Queen_Mod(Row,N) + 1;
    }
    // Row N/2+1 to N: Queen on N - Queen_Mod(N-Row+1,N)
    for(int Row=N/2+1; Row<=N; Row++) {
      Positions[Row-1] = N - Queen_Mod(N - Row +1, N);
    }
    return(Positions);
  }

  //-------------------------------------------------------------------
  // Neither of the even N cases place a queen on position (1,1).
  // So this just places the first N-1 queens as on an N-1 sized board,
  // then places the last queen on the bottom right position (N,N).
  
  private int[] Odd_Queens(int N) {
    int[] Even_Positions = Queen_Positions(N-1);
    int[] Positions = new int[N];
    for(int I=0; I<N-1; I++)
      Positions[I] = Even_Positions[I];
    Positions[N-1]=N;
    return(Positions);
  }

  //-------------------------------------------------------------------
  // Given N, returns an array of the positions for each queen.
  
  private int[] Queen_Positions(int N) {
    if (Is_Even(N) && (Mod(N, 6) != 2))
      return(Even_Queens_1(N));
    else if(Is_Even(N))
      return(Even_Queens_2(N));
    else
      return(Odd_Queens(N));
  }
  
  //-------------------------------------------------------------------
  // Given R, returns (2R + N/2 - 3)mod N

  private int Queen_Mod(int R, int N) {
    return(Mod((2*R + N/2 -3), N));
  }

  //-------------------------------------------------------------------
  // Takes NmodM for the case where N is non-negative.

  private int Mod(int N, int M) {
    while (N >= M) {
      N -= M;
    }
    return(N);
  }
  
  //-------------------------------------------------------------------
  // For debugging only.
  
  private void Print_Positions(int[] Positions) {
    System.out.println("N=" + Positions.length);
    for(int I=0; I<Positions.length; I++)
      System.out.println("  " + Positions[I]);
  }
  
  //-------------------------------------------------------------------
  // Update string if slider moves. Redraw if button clicked.
  
  public boolean handleEvent(Event E) {
    if (E.target == N_Slider) {
      N = N_Slider.getValue();
      N_Value.setText(Integer.toString(N));
      return(true);
    }
    else if (E.target == Draw) {
      repaint();
      return(true);
    }
    else
      return(super.handleEvent(E));
  }


  //-------------------------------------------------------------------

  public String[][] getParameterInfo() {
    String[][] ParameterInfo =
      {{"WIDTH", "int", "(650 or more)"},
       {"HEIGHT", "int", "(550 or more)"}};
    return(ParameterInfo);
  }

  //-------------------------------------------------------------------

  public String getAppletInfo() {
    return("NQueens version of 4/96. Latest is at " +
	   "http://www.apl.jhu.edu/~hall/java/NQueens.html " +
	   "(and .java for source)");
  }
  
  //-------------------------------------------------------------------
  // Reads Width and Height from HTML tags. Netscape ignores
  // calls to resize(), to these values need to be correct in the HTML.
  
  public void init() {
    Width=Integer.parseInt(getParameter("WIDTH"));   // 650 optimal
    Height=Integer.parseInt(getParameter("HEIGHT")); // 550 optimal
    Add_Widgets();
  }

  //-------------------------------------------------------------------
  
  public void paint(Graphics G) {
    Draw_Title(G);
    Draw_Board(G);
    Draw_Separator(G);
    Draw_Queens(Queen_Positions(N), G);
  }

  //-------------------------------------------------------------------
}