A new Solution for n-queens Problem using Blind Approaches: dfs and bfs algorithms

Table6.DFS and BFS algorithms for 8-queens (number of 
runs are 10) 
AlgorithmDFS
 
AlgorithmBFS
 
Period execute 
 
Time 
 
Time 
 
1 
0.4524
11.4036
2
0.468
12.0432
3
0.4212
11.5908
4
0.4212
12.5736
5
0.4212
11.8404
6
0.4212
12.0276
7
0.468
12.2772
8
0.4992
12.0588
9
0.4992
12.3552
10
0.4368
11.8404
Average time
 
4.49280 / 10 = 
0.44928
120.0108 / 10 = 
12.00108 
maximum 
length Un 
 
57
16777216 
Number of 
extracted node
 
9458841 
3696597 
In Table 7, we compare to BFS and DFS time for deferent 
queens: 
Table7.BFS and DFS time comparison for different 
queens 
DFS
 
BFS
 
Nu
mbe
r 
que
en’s 
 
 
time
 
Number of 
extracted 
node
 
Time
 
Number of 
extracted 
node
 
4 
0 
988 
0 
000 
8 
0 
489 
0 
9940 
6 
0009 
98396 
0003 
00010 
7 
0003 
80194 
00570 
950601 
5 
00480 
9458841 
960940 
3616817 
1 
30554 
94006655 
0760800
~
63305341
~
90 
500048 
056601046 
79410078
~
9637406100
~
99 
954101
81 
6076669557 
988794070
6
~
3866318550
6
~
90 
470500
038
~ 
9604000695
83
~ 
471471301
00
~
9015970701
617
~
96 
457105
577000
500
~
9688477030
08815840
~
679971304
88990635
~
9837005670
501901309
~
According to up results, we can see the average run time to 
reach the first answer in DFS algorithm 0.44928 second while 
this time for BFS algorithm 12.00108 second. Therefore, the 
DFS algorithm is quicker than BFS algorithm. Number of 
extended node in DFS algorithm is less than BFS algorithm 
therefore the needed memory for BFS is more than DFS. 
Fig 2:View of DFS algorithm’s performance in solving N-
queens problem

---

International Journal of Computer Applications (0975 – 8887) 
Volume 53– No.1, September 2012
48 
Fig 3:View of BFS algorithm’s performance in solving N-
queens problem 
5. CONCLUSION AND FUTURE WORK 
In this paper, we proposed new blind algorithm for solving n-
queens using combination of DFS and BFS methods. The 
proposed algorithm act based on placing queens on chess 
board directly. The results show that performance and run 
time in this approach better then back tracking methods and 
hill climbing modes. As a result, the DFS algorithm is quicker 
than BFS algorithm and Number of extended node in DFS 
algorithm is less than BFS algorithm as well as the required 
memory for BFS is larger than DFS. Using this method, time 
and cost of solving n-queens problem is minimized in 
comparison of old methods. As future work, we can also find 
more efficient algorithms to solving n-queen problem based 
on other AI techniques.