Проблема N-ферзей и Backtracking ~ как представить узел?

Question

Я пытаюсь создать библиотеку для решения различных ограниченных задач. Сначала я попытался решить проблему с 4 ферзями, и я не могу понять, как я могу представить узел. Я имею в виду, что могу сделать это без каких-либо классов дерева (по размерным массивам), но я хочу представить это как проблему древовидной структуры.

глубина дерева всегда <= 4 </p>

вот мой код:

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;
  }</p>

<p>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();</p>

<pre><code>}
</code>

void start () { stack.push (корень); подсчитывать ++; поиск (stack.pop (), 0); }

логическое согласие (ток узла) { логический флаг = true; 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]. Вы можете так же пометить диагонали так же, как вы это сделали со строками.

Таким образом, проблема теперь состоит в том, чтобы просто найти перестановки [1..N], которые можно присвоить q[1..N], которые удовлетворяют всем 3 ограничениям. Я оставлю все остальное на ваше усмотрение.

Answer 2

Состояние проблемы в любой момент времени - это положение каждой королевы в каждом столбце на доске. Как сказал @poly, две королевы не могут быть в одном столбце. @poly проделал большую работу, объяснив параметры проблемы.

Если вы выбираете путь возврата, тогда вам нужно выбрать место для первой королевы и продолжить, чтобы посмотреть, работает ли он. Далее вы выбираете местоположение 2-й королевы, затем 3-го и, наконец, 4-го. Если четвертое не работает, вы вернетесь к третьему, если третье не сработает, вернетесь ко второму и т. Д.

Я просто расскажу о кейсе 4 на доске 4х4. Я бы сказал, что корень дерева - это то, где вы сделали ноль выбора. Первый уровень ниже корня будет четыре дочерних ... один дочерний для каждого возможного местоположения первой королевы в первом столбце (1,2,3 и 4). На высоте два в дереве вы выбираете местоположение 2-й королевы во втором столбце и так далее вниз по дереву.

Вот частично заполненное дерево:

                          ""
                            |
              -----------------------------------------------
              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

Таким образом, все листья дерева являются кортежами формы (A, B, C, D), где A - это позиция первой ферзя, B - это позиция 2-го, C - это позиция 3-го и D - позиция четвертого.

Так что я бы сказал, что «ценность» каждого узла - это набор вариантов, которые вы сделали до сих пор. Я не думаю, что видел бы это как int. Вы можете просто сохранить его как string, если хотите, или что-то вроде ArrayList, может немного упростить вашу рекурсию. Надеюсь, это поможет.

Answer 3

Вы перевернули его - вы должны хранить родительский узел, а не дочерний.