Объяснение кода Java-решения для 8-Queen.

Question

Я нашел решение с 8 королями, которое я смог скомпилировать и запустить в Eclipse. Я считаю, что это решение следует подходу backtracking, а мясо работы выполняется в функциях solution и unsafe, но мне трудно понять пути кода там. Может кто-то, пожалуйста, помогите мне понять, что делает этот код.

My Source - http://rosettacode.org/wiki/N-queens_problem#Java Я проверил выход по 92 решениям, опубликованным в других источниках. Выглядит неплохо. Поэтому я знаю, что код работает.

Я попытался отформатировать его и добавить некоторые базовые ноты, чтобы очистить вещи -

private static int[] b = new int[8]; 
private static int s = 0; 

public static void main(String[] args) { 
    // solution from - http://rosettacode.org/wiki/N-queens_problem#Java 
    new QueenN(); 
} 

public QueenN() { 
    solution(); 
} 

public void solution() { 
    int y = 0; 
    b[0] = -1; 
    while (y >= 0) { 
     do { 
      b[y]++; 
     } while ((b[y] < 8) && unsafe(y)); 

     if (b[y] < 8) { 

      if (y < 7) { 
       b[++y] = -1; 
      } else { 
       putboard(); 
      } 

     } else { 
      y--; 
     } 
    } 
} 

// check if queen placement clashes with other queens 
public static boolean unsafe(int y) { 
    int x = b[y]; 
    for (int i = 1; i <= y; i++) { 
     int t = b[y - i]; 
     if (t == x || t == x - i || t == x + i) { 
      return true; 
     } 
    } 
    return false; 
} 

// printing solution 
public static void putboard() { 
    System.out.println("\n\nSolution " + (++s)); 
    for (int y = 0; y < 8; y++) { 
     for (int x = 0; x < 8; x++) { 
      if (b[y] == x) 
       System.out.print("|Q"); 
      else 
       System.out.print("|_"); 
     } 
     System.out.println("|"); 
    } 
} 

End.

Answer 1

Постараемся понять код шаг за шагом. Прежде всего, мы называем решение функции(), что и приводит к выполнению головоломки.

Решение несильно:

public void solution() { 
    int y = 0; 
    b[0] = -1; 
    while (y >= 0) { 
     do { 
      b[y]++; //if last cell was unsafe or we reached the end of the board, we go for the next row. 
     } while ((b[y] < 8) && unsafe(y)); //Checks whether it's the last cell and if it's an unsafe cell (clashing) 

     if (b[y] < 8) { //We found a safe cell. Hooray! 

      if (y < 7) { //Did we place the last queen? 
       b[++y] = -1; //Nope, let's allocate the next one. 
      } else { 
       putboard(); //Yup, let's print the result! 
      } 

     } else { //If not a single safe cell was found, we reallocate the last queen. 
      y--; 
     } 
    } 
} 

На первом некоторое время, вы будете перебирать каждую ячейку в строке (или столбце, однако вы предпочитаете Это просто поворот дело.). В каждой ячейке вы делаете небезопасную (y) проверку, которая вернет true, если ячейка, в которую вы помещаете королеву, сталкивается с другими ячейками, занятыми королевой (как вы уже узнали в комментарии).

Следующий шаг, после того как мы нашли безопасную ячейку для размещения фактической королевы (y), мы делаем проверку безопасности: если мы не нашли ни одной безопасной ячейки для этой королевы, мы должны перераспределить последнюю Королева.

Если ячейка была найдена и была правильной, мы проверяем, была ли она последней королевой (y < 7). Если это так, мы переходим к печати результата. В противном случае мы просто запустим цикл while, поставив b [++ y] = -1.

Опасная функция:

public static boolean unsafe(int y) { 
    int x = b[y]; //Let's call the actual cell "x" 
    for (int i = 1; i <= y; i++) { //For each queen before placed BEFORE the actual one, we gotta check if it's in the same row, column or diagonal. 
     int t = b[y - i]; 
     if (t == x || t == x - i || t == x + i) { 
      return true; //Uh oh, clash! 
     } 
    } 
    return false; //Yay, no clashes! 
} 

Эта функция проверяет, является ли матка мы используем столкновения с какой-либо из выделенных маток до этого. Столкновения могут происходить по диагонали, по вертикали или по горизонтали: именно поэтому перед операцией «return true» существует тройная проверка OR.

функция

Putboard:

public static void putboard() { 
    System.out.println("\n\nSolution " + (++s)); 
    for (int y = 0; y < 8; y++) { 
     for (int x = 0; x < 8; x++) { 
      if (b[y] == x) 
       System.out.print("|Q"); 
      else 
       System.out.print("|_"); 
     } 
     System.out.println("|"); 
    } 
} 

Я не собираюсь объяснить это тот, который глубоко, потому что это просто достаточно просто линия функция печати, которые вы можете узнать, как она работает самостоятельно, выполняя решение!

Надеюсь, это поможет.

Cheers!