backtracking - Explanation of 8-Queen solution Java code. -

i found 8-queen solution able compile , run in eclipse. believe solution follows backtracking approach , meat of work done in solution , unsafe functions, having hard time understanding code paths in there. can please me understand code doing.

my source - http://rosettacode.org/wiki/n-queens_problem#java verified output against 92 solutions published on other sources. looks good. know code works.

i have tried format , add basic notes clear things -

private static int[] b = new int[8]; private static int s = 0;  public static void main(string[] args) {     // solution - 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) {         {             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 other queens public static boolean unsafe(int y) {     int x = b[y];     (int = 1; <= y; i++) {         int t = b[y - i];         if (t == x || t == x - || t == x + i) {             return true;         }     }     return false; }  // printing solution public static void putboard() {     system.out.println("\n\nsolution " + (++s));     (int y = 0; y < 8; y++) {         (int x = 0; x < 8; x++) {             if (b[y] == x)                 system.out.print("|q");             else                 system.out.print("|_");         }         system.out.println("|");     } } 

end.

let's try understand code step step. first of all, call function solution(), leads execution of puzzle answer.

solution funcion:

public void solution() {     int y = 0;     b[0] = -1;     while (y >= 0) {         {             b[y]++; //if last cell unsafe or reached end of board, go next row.         } while ((b[y] < 8) && unsafe(y)); //checks whether it's last cell , if it's unsafe cell (clashing)          if (b[y] < 8) { //we found safe cell. hooray!              if (y < 7) { //did place last queen?                 b[++y] = -1; //nope, let's allocate next one.             } else {                 putboard(); //yup, let's print result!             }          } else { //if not single safe cell found, reallocate last queen.             y--;         }     } } 

on first while, you're going iterate through each cell in row (or column, prefer it. it's rotation matter). on each cell make unsafe(y) check, return true in case cell you're placing queen in clashing other queen-occupied cells (as you've found out in comment).

next step, once we've found safe cell in place actual queen (y), make security check: if have not found single safe cell queen, have reallocate last queen.

in case cell found , correct, check whether last queen (y < 7). if so, proceed print result. otherwise, re-start while loop placing b[++y] = -1.

unsafe function:

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

this function checks whether queen we're using clashes of allocated queens before one. clashes might happen diagonally, vertically or horizontally: why there triple or check before "return true" statement.

putboard function:

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

i'm not gonna explain 1 deep, because line printing function can find out how works when executing solution!

hope helps.

cheers!