java - N皇后问题和回溯~如何表示节点？

Question

我正在尝试构建一个库来解决不同的约束问题。我首先尝试了 4-queens 问题，但我无法弄清楚如何表示 node 。我的意思是我可以在没有任何树类(通过维数组)的情况下做到这一点，但我想将其表示为树结构问题。

树的深度总是<=4

这是我的代码:

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();
}
无效开始(){       堆栈。推(根)；       计数++；       搜索(堆栈。弹出()，0)；   
 boolean 一致(节点当前){     boolean 标志=真；    int n=current.getDepth();       //需要更多       返回标志；   
 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> 
 

Answer 1

有很多方法可以解决 N 皇后区问题。您提到了回溯，所以我将解释使用该技术解决它的最佳方法之一。

首先，注意同一列上不能有两个皇后:每一列必须恰好有一个皇后，不能多也不能少。因此，不用将皇后位置表示为二维 (r, c)，只需将一个皇后恰好分配给恰好一列即可； q[c] == r 表示分配给 c 列的皇后在 r 行。

您的问题现在变得简单多了:现在可以保证不会有两个皇后在同一列上。您现在只需要强制执行其他 2 个约束:同一行上没有两个皇后，同一对角线上没有两个皇后。

检查两个皇后是否在同一行很简单:q[c1] == q[c2] 表示两个皇后在同一行。但是请注意，您实际上不需要比较每对皇后的 q 值:您可以简单地为每一行分配一个标签，当您在该行放置一个皇后时，您将该行标记为“已使用”。没有其他皇后可以放置在已使用的行上。

检查两个皇后是否在同一条对角线上并没有那么困难:根据 q[c1] 和 q[c2] 找到方程。您可以像标记行一样标记对角线。

所以现在的问题是简单地找到可分配给 q[1..N] 的 [1..N] 满足所有 3 个约束的排列。剩下的就交给你了。