1000 queens using Java under 30s

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class NQEEN {
    static final int N=1000;
    static Random rand = new Random();
   
    // i=col, get(i) = row
    //h - so cap doi gay nguy hien cho nhau
    //cung dong: get(i) = get(j)
    //duong cheo song song duong cheo chinh: get(i)-i = get(j)-j
    //song song duong cheo phu: get(i)+i = get(j)+j
    static int get_h_cost(ArrayList <Integer>board){
        int h = 0;
        for(int i=0; i<board.size(); i++){
            for(int j=i+1; j<board.size(); j++){
                if((board.get(i) - i == board.get(j) - j) || (board.get(i) + i == board.get(j) + j))
                    h ++;
            }
        }
        return h;
    }
   
   
    //luu lai cac vi tri de doa nhau
    static ArrayList threatened_queens(ArrayList <Integer>board){
        ArrayList <Integer> threatened = new ArrayList();
        for(int i=0; i<board.size(); i++){
            for(int j=i+1; j<board.size(); j++){
                if((board.get(i) - i == board.get(j) - j) || (board.get(i) + i == board.get(j) + j)){
                    threatened.add(i);
                    break;
                }
            }
        }
        return threatened;
    }
   
    //tìm nước đi mới
    //tim trang thai moi den khi nao het kien nhan
    //tai 1 vi tri bi de doa bat ki ta doi vi tri voi lan luot cac con con lai
    //neu so cap de doa nhau nho hon h_cost luc truoc thi cap nhat trang thai cho trang thai hien tai
    static ArrayList new_neighbor(ArrayList <Integer> curr_board, int curr_cost){
        ArrayList <Integer>threatened= threatened_queens(curr_board);
        for(int itr=0; itr<1500; itr++){           
            int i= threatened.get(rand.nextInt(threatened.size()));
            for(int j= 0; j<N; j++){
                ArrayList <Integer> neighbor = new ArrayList(curr_board);
                int tem= neighbor.get(i);
                neighbor.set(i, neighbor.get(j));
                neighbor.set(j, tem);

                if(get_h_cost(neighbor) < curr_cost){
                    return neighbor;
                }
            }
        }
        return null;
    }
   
    public static void main(String[] args) {
       
        //init board
        ArrayList <Integer> curr_board= new ArrayList<>();
        for(int i=0; i<N; i++)
            curr_board.add(i);
        Collections.shuffle(curr_board);
       
       
        //trạng thái gần đây nhất
        ArrayList <Integer> last_board= new ArrayList<>(curr_board);       
        int curr_h= get_h_cost(curr_board);
       
        try{
             while(curr_h != 0){
                curr_board= new_neighbor(curr_board, curr_h);
                last_board= new ArrayList<>(curr_board);         
                curr_h= get_h_cost(curr_board);
            }
           
            for(int i=0; i<N; i++){
                System.out.print(last_board.get(i)+" ");
            }
            System.out.println("");
            System.out.println("number threatened queens: "+get_h_cost(last_board));
        }catch(NullPointerException e){
            System.out.println("Local optimal");
        }   
    }
}