Basic CS-Data Structures [Redpine Infotech Placement]: Sample Questions 3 - 3 of 4

Glide to success with Doorsteptutor material for competitive exams : get questions, notes, tests, video lectures and more- for all subjects of your exam.

Question 3

Data Structures
Edit

Describe in Detail

Essay▾

8 queen problem can be solved by using which method.

Explanation

• 8 queen problem can solved by using back tracking method.
• Back tracking is used to solving the problems like puzzles.
• Search path is followed and the algorithm backtracks at a particular point in the path.
• The backtracking happens when algorithm realizes path will not lead to a valid solution and then it follows another path starting from a previous decision point.

Ex. Of 8 Queen Problem

• Eight queen puzzle is the problem of placing eight chess queens on an chessboard.
• A solution required that no two queen share the same row, column, or diagonal.
• Strategy: the rows and columns are numbered through 1 to 8.
• Each queen is put on a different row without loss, we assume queen i is to be placed on row i.
• 8 tuple () , where is the column queen i is placed.

Implicit Constraints Are

• No two can be the same that is, all queens must be on different column.
• No two queens can be on the same diagonal.
• Reduce the size of space from 8- tuples.
• First solution is (4, 6 , 8 , 2, 7,6, 3,5) First Solution is (4, 6 , 8 , 2, 7,6, 3,5)
• Second solution is (3, 7, 1, 5, 8,2, 4,6)