CODEWITHSUNDEEP
java
seteropere
seteropere

Reputation: 489

N-queens problem and Backtracking ~how to represent the node?

I am trying to build a library for solving different constrained problems . I tried first with 4-queens problem and I can't figure out how I can represent the node . I mean I can do it without any tree classes (by dimensional arrays) but I wanna represent it as tree-structure problem .

the depth of a tree is always <=4

here is my code : 

class Node {
  Node []next ;
  int value;
  int depth;
  String name;
  Node(){
      next=null;
      value=0;
      depth=0;
      name=null;
  }
  Node(int value,int depth,String name){
      this.value=value;
      //this.next=child;
      this.depth=depth;
      this.name=name;
  }



class Tree{
    Node root;
    Stack stack;
    String[] vars={"Q1","Q2","Q3","Q4"};
    int[] domain={1,2,3,4};
    int count=0;
    Tree(){
        root=new Node();
        stack=new Stack();



}




void start(){
       stack.push(root);
       count++;
       search(stack.pop(),0);
   }



boolean consistent(Node current){
    boolean flag=true;
    int n=current.getDepth();
        //need more
       return flag;
   }


private void search(Node current,int num) {

    if(num==3&&consistent(current)){
        System.out.println("solution !");
        num=0;
    }
    else{
        if(consistent(current)){
        Node child[]=new Node[4];
            for(int i=0;i<4;i++)
                child[i]=new Node(domain[i],current.getDepth()+1,vars[num]);

        current.setNext(child);

        for(int i=3;i>=0;i--)
            stack.push(child[i]);

        search(stack.pop(),num+1);

    }
    search(stack.pop(),num);
    }
}<code>

Upvotes: 1

Views: 2061

Answers (3)

J-16 SDiZ
J-16 SDiZ

Reputation: 26910

You have got it inverted -- you should store the parent of the node, not the child.

Upvotes: 0

Brent Writes Code
Brent Writes Code

Reputation: 19613

The state of the problem at any point in time is the position of each of the queens in each column on the board. As @poly said, there's no way two queens can be in the same column. @poly did a great job explaining the parameters of the problem.

If you're taking a backtracking approach then what you want to do is choose a location for the first queen and continue onward to see if it works. Next you choose the location of the 2nd queen, then the 3rd and finally the 4th. If the 4th doesn't work, you'll backtrack to the third, if the third doesn't work, you'll back to the 2nd, etc.

I'll just talk about the 4 queen case on a 4x4 board. The way I would see it is that the root of the tree is where you've made zero choices. The first level below the root would be four children...one child for each possible location of the first queen in the first column (1,2,3 & 4). At height two in the tree, you choose the location of the 2nd queen in the second column and so on down the tree.

Here's a partially completed tree:

                          ""
                            |
              -----------------------------------------------
              1                  2            3             4
              |                  |            |             |        
     ---------------------
     1,1   1,2   1,3   1,4
            |
------------------------------------

1,1,1     1,1,2     1,1,3      1,1,4

                                 |
        -------------------------------------------------
        1,1,4,1      1,1,4,2       1,1,4,3        1,1,4,4

So all the leaves of the tree are tuples of the form (A,B,C,D) where A is the position of the first queen, B is the position of the 2nd, C is the position of the 3rd and D is the position of the fourth.

So I would say the "value" of each Node is the set of choices you've made so far. I don't think I'd see it as an int. You could just keep it as a string if you wanted to or something like an ArrayList might make your recursion a bit easier. Hope that helps.

Upvotes: 1

polygenelubricants
polygenelubricants

Reputation: 383746

There are many ways to tackle the N-queens problem. You mentioned backtracking, so I will explain one of the best way to solve it with that technique.

First, note that no two queens can be on the same column: each column must have exactly one queen, no more, no less. Therefore, instead of representing the queen positions as 2-dimensional (r, c), it suffices to assign exactly one queen to exactly one column; q[c] == r means the queen assigned to column c is on row r.

Your problem has now become much simpler: it's now guaranteed that no two queens will be on the same column. You now only need to enforce the other 2 constraints: no two queens on the same row, and no two queens on the same diagonal.

Checking if two queens are on the same row is trivial: q[c1] == q[c2] means the two queens are on the same row. Note, however, that you don't actually need to compare the q values of each pair of queens: you can simply assign a label to each row, and when you place a queen on that row, you mark that row as "used". No other queen can be placed on an already used row.

Checking if two queens are on the same diagonal is not that much more difficult: find the equations in terms of q[c1] and q[c2]. You can similarly label the diagonals just as you did with the rows.

So the problem is now simply finding permutations of [1..N] that is assignable to q[1..N] that satisfies all 3 constraints. I'll leave the rest up to you.

Upvotes: 6

Related Questions