DEVELOPING EFFICIENT ALGORITHMS - Introduction to Java Programming: Comprehensive Version - page 848

56 queens[k] = j; place a queen

search the next row 57 k++;

58 }
59 }
60
61 if (k == -1 )

62 return false ; // No solution

63 else

64 return true ; // A solution is found

65 }
66
67

public int findPosition( int k) {

68 int start = queens[k] + 1 ; // Search for a new placement

69
70 for ( int j = start; j < SIZE; j++) {

71 if (isValid(k, j))

72 return j; // (k, j) is the place to put the queen now

73 }
74
75 return -1 ;

76 }
77
78 /** Return true if a queen can be placed at (row, column) */
79 public boolean isValid( int row, int column) {
80 for ( int i = 1 ; i <= row; i++)
81 if (queens[row - i] == column // Check column
82 || queens[row - i] == column - i // Check upleft diagonal
83 || queens[row - i] == column + i) // Check upright diagonal
84 return false ; // There is a conflict

85 return true ; // No conflict

86 }
87 }

The program invokes search() (line 19) to search for a solution. Initially, no queens are
placed in any rows (line 15). The search now starts from the first row with k = 0 (line 48) and
finds a place for the queen (line 51). If successful, place it in the row (line 56) and consider the
next row (line 57). If not successful, backtrack to the previous row (lines 53-54).
The findPosition(k) method searches for a possible position to place a queen in row
k starting from queen[k] + 1 (line 68). It checks whether a queen can be placed at start ,
start + 1 , . . . , and 7 , in this order (lines 70-73). If possible, return the column index
(line 72); otherwise, return -1 (line 75).
The isValid(row, column) method is called to check whether placing a queen at the
specified position causes a conflict with the queens placed earlier (line 71). It ensures that no
queen is placed in the same column (line 81), in the upper-left diagonal (line 82), or in the
upper-right diagonal (line 83), as shown in Figure 22.7.

01234567

0
1
2
3
4
5
6
7

check
column

upright diagonal

upleft

(row, column)

F IGURE 22.7

Invoking isValid(row, column) checks whether a queen can be placed at
(row, column).