The backtracking algorithm of n queen problem can be improved by space and time trade-off further. The consideration of positions occupancy is attained by duplicate_array and two integrals. Note that these utilities can’t tell all illegal moves because it is performing its job on the basis of chess_board definition. That is, power of utilities contained by chess_board are not enough to telling all illegal moves. It needs a data structure to record positions occupied by chesses. Naturally, it needs three arrays to recording row, column, diagonal1 (upper left to lower right) and diagonal2 (upper right to lower left). Column is already represented by duplicate_array. So it needs two other array to represent diagonal1,2. Consequently, the job is how to express the meaning of one diagonal is occupied. That is, for a move: (cur_i, j), how to assign value to the corresponding element in diagonal1,2. Assuming the one of occupied diagonal1 is diagonal1[x] and diagonal2 is diagonal2[y], then assign diagonal1[x] and diagonal2[y] to 1 to denoting these diagonals are occupied. An n queen problem has 2n-1 diagonal1s and 2n-1 diagonal2s. The rules are:
|
本类阅读TOP10