6.1 N Queens Problem using Backtracking
6.1 N Queens Problem using Backtracking
N-Queens problem
state space tree
PATREON : https://www.patreon.com/bePatron?u=20…
Courses on Udemy
================
Java Programming
https://www.udemy.com/course/java-se-…
Data Structures using C and C++
https://www.udemy.com/course/datastru…
C++ Programming
https://www.udemy.com/course/cpp-deep…
Content
0.255 -> The problem is N-Queens problem.
2.9 -> First, let us understand what does it mean by "N-Queens problem"
5.72 -> Then I'll explain to you how backtracking is used for
8.42 -> solving this problem.
10.595 -> See here
11.675 -> a chess board is given
14.145 -> of 4 cross 4, 16 cells.
17.1 -> A standard chessboard will be of 8X8
20.115 -> But for we are using a size of a problem,we have taken 4X4.
23.015 -> And 4 queens are given.
25.995 -> So,in a game of chess,queen will be there
28.195 -> which will have its move like,horizontal
31.255 -> that is in a row or a column or diagonally it moves.
34.245 -> So,here it also a same queen.
37.445 -> And that queen,we have to place them on this board.
40.325 -> So,all 4 queens we have to place.Such that
43.095 -> No,two queens are under attack
46.365 -> So,when do you say they are under attack
48.065 -> If they are in same row or same column
50.905 -> or they are in same diagonal
55.985 ->
60.205 -> So,we have to avoid these and arrange themselves
63.235 -> that,they are not under attack.
65.425 -> So,is it possible to arrange that?
68.305 -> Yes,it is possible.We get some solutions.
71.325 -> Is there only one solution? No,for this
73.705 -> we will have more than one solution.And we want all those solutions.
78.095 -> So,now
79.205 -> We want to know,what all
80.955 -> their possible arrangements,from
83.705 -> there,which will satisfy these conditions.
86.955 ->
89.925 ->
93.765 ->
95.805 ->
98.935 ->
101.765 ->
105.325 ->
107.745 ->
110.755 ->
113.945 ->
116.475 ->
118.935 ->
121.565 ->
123.835 ->
127.075 ->
131.365 ->
134.515 ->
137.305 ->
140.355 ->
143.345 ->
146.385 ->
149.495 ->
151.155 ->
153.335 ->
154.945 ->
157.435 ->
160.145 ->
163.405 ->
165.935 ->
168.705 ->
172.905 ->
175.925 ->
178.115 ->
181.535 ->
184.215 ->
185.645 ->
187.545 ->
190.525 ->
193.885 ->
196.755 ->
199.785 ->
203.675 ->
206.705 ->
208.385 ->
214.005 ->
217.765 ->
218.775 ->
221.885 ->
224.905 ->
227.925 ->
229.515 ->
232.545 ->
234.525 ->
238.125 ->
239.185 ->
245.855 ->
249.455 ->
252.985 ->
256.985 ->
261.785 ->
264.125 ->
266.475 ->
267.665 ->
270.745 ->
273.175 ->
276.675 ->
278.955 ->
282.025 ->
287.475 ->
289.215 ->
292.125 ->
296.185 ->
300.325 ->
303.355 ->
306.715 ->
309.435 ->
312.475 ->
315.625 ->
318.995 ->
320.815 ->
324.085 ->
326.575 ->
329.915 ->
332.015 ->
335.025 ->
335.975 ->
338.945 ->
340.955 ->
344.985 ->
348.095 ->
351.855 ->
355.945 ->
359.305 ->
362.325 ->
365.205 ->
367.865 ->
371.755 ->
374.695 ->
377.485 ->
379.495 ->
382.315 ->
385.305 ->
388.255 ->
391.775 ->
394.615 ->
396.985 ->
399.975 ->
404.135 ->
407.465 ->
411.085 ->
414.065 ->
416.685 ->
419.845 ->
422.045 ->
424.435 ->
425.795 ->
427.955 ->
430.375 ->
431.755 ->
434.885 ->
437.595 ->
438.955 ->
439.985 ->
441.855 ->
444.915 ->
447.385 ->
453.315 ->
456.955 ->
459.925 ->
463.775 ->
465.255 ->
468.215 ->
469.795 ->
472.225 ->
474.495 ->
477.465 ->
480.015 ->
481.875 ->
484.805 ->
486.865 ->
490.145 ->
493.125 ->
495.235 ->
497.825 ->
500.485 ->
503.485 ->
506.345 ->
509.785 ->
511.185 ->
514.215 ->
517.655 ->
520.745 ->
521.865 ->
524.865 ->
527.415 ->
529.455 ->
532.475 ->
535.585 ->
539.175 ->
543.955 ->
544.975 ->
547.325 ->
549.725 ->
552.245 ->
554.435 ->
555.755 ->
559.575 ->
561.375 ->
564.385 ->
565.645 ->
569.575 ->
572.715 ->
577.445 ->
579.645 ->
582.725 ->
587.265 ->
589.575 ->
593.425 ->
594.555 ->
596.315 ->
601.395 ->
604.425 ->
606.375 ->
609.745 ->
611.885 ->
615.015 ->
619.365 ->
622.065 ->
624.825 ->
628.145 ->
631.875 ->
635.255 ->
637.215 ->
639.925 ->
643.095 ->
646.785 ->
649.805 ->
650.725 ->
653.795 ->
656.395 ->
658.545 ->
661.935 ->
665.595 ->
667.565 ->
668.935 ->
671.665 ->
674.555 ->
675.625 ->
678.415 ->
679.865 ->
682.855 ->
685.655 ->
688.985 ->
692.685 ->
696.295 ->
698.245 ->
700.805 ->
702.305 ->
703.525 ->
711.275 ->
712.995 ->
714.955 ->
718.435 ->
720.305 ->
723.475 ->
725.635 ->
728.645 ->
730.305 ->
733.395 ->
735.865 ->
737.705 ->
739.285 ->
742.375 ->
745.095 ->
748.415 ->
749.645 ->
752.285 ->
754.485 ->
757.435 ->
760.545 ->
763.475 ->
767.005 ->
769.375 ->
771.045 ->
773.835 ->
776.605 ->
779.255 ->
781.555 ->
784.475 ->
787.075 ->
790.055 ->
793.605 ->
796.815 ->
799.685 ->
801.475 ->
804.215 ->
807.215 ->
809.215 ->
812.685 ->
815.685 ->
818.715 ->
Source: https://www.youtube.com/watch?v=xFv_Hl4B83A