Another Java post for beginner

Having checked my previous blog’s traffic, it seems that there are incomings from keyword nQueen problem algorithm. So, I decided to copy and paste my previous project posted in there to here. Yes, it’s about an example problem of backtracking algorithm. I got this task back there when I was in 3rd semester. Ok, lets just read the post.

This post is copied from here with a little modification. So, the time relativity in this post based on that post.

Ok, one of my big pressure, or maybe just my obligation as a student, is already solved. Yeah, as you can see in the title of this post, it’s about the task of subject “Algorithm and Programming 2″ in my study. Yes, I have to create an algorithm to solve N-Queen problem, and then make a presentation to get highest score in my big quiz.

What is N-Queen problem? As you can see in another search result in search engine, in general, N-Queen problem is how can you get a sollution to set n number of Queen on n x n size of chessboard, where no one can attack each other. In my task, I have to use backtracking algorithm, in order to get the closest sollution, rather than all sollution. It means the output is, there is any sollution or not.

We need 2 arrays to use this algorithm. First is the location of the Queens. We can use 1 dimension array with Integer type to save their coordinates. Why just 1 dimension array? Because we know that just one Queen for one row, so we can save the coordinate like this: queen[y]=x; It means that queen at row y is settled at column x. It will save with less capacity rather than 2 dimension array. The second array has to be 2 dimension array with Boolean type. We use it to save the location where Queens cannot take place based on the coordinate. After one Queen is settled, we change the value of second array, where is the row, column, and all diagonals of the position of the Queen, to be “cannot take place”. So in the program’s loop, it will be checked and no queens will try that place. So easy, isn’t it?

I will give explanation about the variables and methods before the pseudocode. Variable queens means the position of the Queens, variable place means the status of free place (it is initialized with true value), variable y means row, variable x means column, and variable size means board size and the number of Queens. Method isAllSolved() will return whether the problem is already solved or not (true if already solved, false is not solved yet), method createCopyOf(array) will create new array with the same value as the parameter, method setCannotTakePlace(x, y) means set the row, column, and diagonals of [x, y] to be ‘false’, so no queens can take that place. And method isRowSolved(place, y) return whether the row y is already solved or not (return true if there is any queen, and false if no queen at that row).

Here is the pseudocode:

void setQueen(int[] queens, boolean[][] place, int y) {
  //Loop for each column in row y
  for(int x = 0; x < size;x++) {
    //If the tile can be taken place and there is no sollution yet
    //So if there is already a sollution, it will do nothing
    if(place[x][y] && !isAllSolved()) {
      //Create new array
      queensCopy = createCopyOf(queens);
      placeCopy = createCopyOf(place);

      //Set the queen at possible place
      queensCopy[y] = x;
      setCannotTakePlace(x, y);

      //The sentinel to stop the program or not
      if(isAllSolved()) {
        print(queensCopy);
      }
      else {
        //The sentinel to continue the recursion or not
        if(isRowSolved(placeCopy, y)) {
          setQueen(queensCopy, placeCopy, y+1);
        }
      }
    }
  }
}

I will give the demo of my program as executable jar file. I use GUI to display the sollution. Once you run the program, an input dialog box will be displayed. You have to type the board size at any size but negative (because the program won’t run anything). After that, a window is opened and you will see the first sollution. You can see another sollution by press right/left arrow on your keyboard. I tell you again, it is ‘another sollution’, not the next sollution.

You can download this jar executable file and the source code here

You can analyze how it works by reading the source code. Please don’t laugh at my source code, because this is my capability back when I was in 3rd semester. So it seems that has many mistakes.

blog comments powered by Disqus