Backtracking: Back tracking is a form of recursion. In this method it is possible to backtrack if traversal reaches a node which has no other way from that to find solution. It can be used to solve problems like eight queens puzzle and maze problem. Trace of “putQueen()”: putQueen(0) col = 0; putQueen(1) col = 0; col = 1; col = 2; putQueen(2) col = 0; col = 1; col = 2; col = 3; col = 3; putQueen(2) col = 0; col = 1; putQueen(3) col = 0; col = 1; col = 2; col = 3; col = 2; col = 3; col = 1; putQueen(1) col = 0; col = 1; col = 2; col = 3; putQueen(2) col = 0; putQueen(3) col = 0; col = 1; col = 2; .Q.. ...Q Q... ..Q. col = 3; col = 1; col = 2; col = 3; col = 2; putQueen(1) col = 0; putQueen(2) col = 0; col = 1; col = 2; col = 3; putQueen(3) col = 0; col = 1; ..Q. Q... ...Q .Q.. col = 2; col = 3; col = 1; col = 2; col = 3; col = 3; putQueen(1) col = 0; putQueen(2) col = 0; col = 1; col = 2; putQueen(3) col = 0; col = 1; col = 2; col = 3; col = 3; col = 1; putQueen(2) col = 0; col = 1; col = 2; col = 3; col = 2; col = 3; 2 solutions found

Question

Want to see the full answer?

Answer 1

Question

Chapter 5, Problem 24E

Program Plan Intro

Backtracking:

Back tracking is a form of recursion.

In this method it is possible to backtrack if traversal reaches a node which has no other way from that to find solution.

It can be used to solve problems like eight queens puzzle and maze problem.

Trace of “putQueen()”:

putQueen(0)

col = 0;

putQueen(1)

col = 0;

col = 1;

col = 2;

putQueen(2)

col = 0;

col = 1;

col = 2;

col = 3;

col = 3;

putQueen(2)

col = 0;

col = 1;

putQueen(3)

col = 0;

col = 1;

col = 2;

col = 3;

col = 2;

col = 3;

col = 1;

putQueen(1)

col = 0;

col = 1;

col = 2;

col = 3;

putQueen(2)

col = 0;

putQueen(3)

col = 0;

col = 1;

col = 2;

.Q..

...Q

Q...

..Q.

col = 3;

col = 1;

col = 2;

col = 3;

col = 2;

putQueen(1)

col = 0;

putQueen(2)

col = 0;

col = 1;

col = 2;

col = 3;

putQueen(3)

col = 0;

col = 1;

..Q.

Q...

...Q

.Q..

col = 2;

col = 3;

col = 1;

col = 2;

col = 3;

col = 3;

putQueen(1)

col = 0;

putQueen(2)

col = 0;

col = 1;

col = 2;

putQueen(3)

col = 0;

col = 1;

col = 2;

col = 3;

col = 3;

col = 1;

putQueen(2)

col = 0;

col = 1;

col = 2;

col = 3;

col = 2;

col = 3;

2 solutions found

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Students have asked these similar questions

Describe three (3) Multiplexing techniques common for fiber optic links

Could you help me to know features of the following concepts: - commercial CA - memory integrity - WMI filter

Briefly describe the issues involved in using ATM technology in Local Area Networks

Answer 2

Question

Chapter 5, Problem 24E

Program Plan Intro

Backtracking:

Back tracking is a form of recursion.

In this method it is possible to backtrack if traversal reaches a node which has no other way from that to find solution.

It can be used to solve problems like eight queens puzzle and maze problem.

Trace of “putQueen()”:

putQueen(0)

col = 0;

putQueen(1)

col = 0;

col = 1;

col = 2;

putQueen(2)

col = 0;

col = 1;

col = 2;

col = 3;

col = 3;

putQueen(2)

col = 0;

col = 1;

putQueen(3)

col = 0;

col = 1;

col = 2;

col = 3;

col = 2;

col = 3;

col = 1;

putQueen(1)

col = 0;

col = 1;

col = 2;

col = 3;

putQueen(2)

col = 0;

putQueen(3)

col = 0;

col = 1;

col = 2;

.Q..

...Q

Q...

..Q.

col = 3;

col = 1;

col = 2;

col = 3;

col = 2;

putQueen(1)

col = 0;

putQueen(2)

col = 0;

col = 1;

col = 2;

col = 3;

putQueen(3)

col = 0;

col = 1;

..Q.

Q...

...Q

.Q..

col = 2;

col = 3;

col = 1;

col = 2;

col = 3;

col = 3;

putQueen(1)

col = 0;

putQueen(2)

col = 0;

col = 1;

col = 2;

putQueen(3)

col = 0;

col = 1;

col = 2;

col = 3;

col = 3;

col = 1;

putQueen(2)

col = 0;

col = 1;

col = 2;

col = 3;

col = 2;

col = 3;

2 solutions found

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Answer 3

Question

Chapter 5, Problem 24E

Program Plan Intro

Backtracking:

Back tracking is a form of recursion.

In this method it is possible to backtrack if traversal reaches a node which has no other way from that to find solution.

It can be used to solve problems like eight queens puzzle and maze problem.

Trace of “putQueen()”:

putQueen(0)

col = 0;

putQueen(1)

col = 0;

col = 1;

col = 2;

putQueen(2)

col = 0;

col = 1;

col = 2;

col = 3;

col = 3;

putQueen(2)

col = 0;

col = 1;

putQueen(3)

col = 0;

col = 1;

col = 2;

col = 3;

col = 2;

col = 3;

col = 1;

putQueen(1)

col = 0;

col = 1;

col = 2;

col = 3;

putQueen(2)

col = 0;

putQueen(3)

col = 0;

col = 1;

col = 2;

.Q..

...Q

Q...

..Q.

col = 3;

col = 1;

col = 2;

col = 3;

col = 2;

putQueen(1)

col = 0;

putQueen(2)

col = 0;

col = 1;

col = 2;

col = 3;

putQueen(3)

col = 0;

col = 1;

..Q.

Q...

...Q

.Q..

col = 2;

col = 3;

col = 1;

col = 2;

col = 3;

col = 3;

putQueen(1)

col = 0;

putQueen(2)

col = 0;

col = 1;

col = 2;

putQueen(3)

col = 0;

col = 1;

col = 2;

col = 3;

col = 3;

col = 1;

putQueen(2)

col = 0;

col = 1;

col = 2;

col = 3;

col = 2;

col = 3;

2 solutions found

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Answer 4

Question

Chapter 5, Problem 24E

Program Plan Intro

Backtracking:

Back tracking is a form of recursion.

In this method it is possible to backtrack if traversal reaches a node which has no other way from that to find solution.

It can be used to solve problems like eight queens puzzle and maze problem.

Trace of “putQueen()”:

putQueen(0)

col = 0;

putQueen(1)

col = 0;

col = 1;

col = 2;

putQueen(2)

col = 0;

col = 1;

col = 2;

col = 3;

col = 3;

putQueen(2)

col = 0;

col = 1;

putQueen(3)

col = 0;

col = 1;

col = 2;

col = 3;

col = 2;

col = 3;

col = 1;

putQueen(1)

col = 0;

col = 1;

col = 2;

col = 3;

putQueen(2)

col = 0;

putQueen(3)

col = 0;

col = 1;

col = 2;

.Q..

...Q

Q...

..Q.

col = 3;

col = 1;

col = 2;

col = 3;

col = 2;

putQueen(1)

col = 0;

putQueen(2)

col = 0;

col = 1;

col = 2;

col = 3;

putQueen(3)

col = 0;

col = 1;

..Q.

Q...

...Q

.Q..

col = 2;

col = 3;

col = 1;

col = 2;

col = 3;

col = 3;

putQueen(1)

col = 0;

putQueen(2)

col = 0;

col = 1;

col = 2;

putQueen(3)

col = 0;

col = 1;

col = 2;

col = 3;

col = 3;

col = 1;

putQueen(2)

col = 0;

col = 1;

col = 2;

col = 3;

col = 2;

col = 3;

2 solutions found

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Answer 5

Chapter 5, Problem 24E

Program Plan Intro

Backtracking:

Back tracking is a form of recursion.

In this method it is possible to backtrack if traversal reaches a node which has no other way from that to find solution.

It can be used to solve problems like eight queens puzzle and maze problem.

Trace of “putQueen()”:

putQueen(0)

col = 0;

putQueen(1)

col = 0;

col = 1;

col = 2;

putQueen(2)

col = 0;

col = 1;

col = 2;

col = 3;

col = 3;

putQueen(2)

col = 0;

col = 1;

putQueen(3)

col = 0;

col = 1;

col = 2;

col = 3;

col = 2;

col = 3;

col = 1;

putQueen(1)

col = 0;

col = 1;

col = 2;

col = 3;

putQueen(2)

col = 0;

putQueen(3)

col = 0;

col = 1;

col = 2;

.Q..

...Q

Q...

..Q.

col = 3;

col = 1;

col = 2;

col = 3;

col = 2;

putQueen(1)

col = 0;

putQueen(2)

col = 0;

col = 1;

col = 2;

col = 3;

putQueen(3)

col = 0;

col = 1;

..Q.

Q...

...Q

.Q..

col = 2;

col = 3;

col = 1;

col = 2;

col = 3;

col = 3;

putQueen(1)

col = 0;

putQueen(2)

col = 0;

col = 1;

col = 2;

putQueen(3)

col = 0;

col = 1;

col = 2;

col = 3;

col = 3;

col = 1;

putQueen(2)

col = 0;

col = 1;

col = 2;

col = 3;

col = 2;

col = 3;

2 solutions found

Answer 6

Chapter 5, Problem 24E

Program Plan Intro

Backtracking:

Back tracking is a form of recursion.

In this method it is possible to backtrack if traversal reaches a node which has no other way from that to find solution.

It can be used to solve problems like eight queens puzzle and maze problem.

Trace of “putQueen()”:

putQueen(0)

col = 0;

putQueen(1)

col = 0;

col = 1;

col = 2;

putQueen(2)

col = 0;

col = 1;

col = 2;

col = 3;

col = 3;

putQueen(2)

col = 0;

col = 1;

putQueen(3)

col = 0;

col = 1;

col = 2;

col = 3;

col = 2;

col = 3;

col = 1;

putQueen(1)

col = 0;

col = 1;

col = 2;

col = 3;

putQueen(2)

col = 0;

putQueen(3)

col = 0;

col = 1;

col = 2;

.Q..

...Q

Q...

..Q.

col = 3;

col = 1;

col = 2;

col = 3;

col = 2;

putQueen(1)

col = 0;

putQueen(2)

col = 0;

col = 1;

col = 2;

col = 3;

putQueen(3)

col = 0;

col = 1;

..Q.

Q...

...Q

.Q..

col = 2;

col = 3;

col = 1;

col = 2;

col = 3;

col = 3;

putQueen(1)

col = 0;

putQueen(2)

col = 0;

col = 1;

col = 2;

putQueen(3)

col = 0;

col = 1;

col = 2;

col = 3;

col = 3;

col = 1;

putQueen(2)

col = 0;

col = 1;

col = 2;

col = 3;

col = 2;

col = 3;

2 solutions found

Answer 7

Chapter 5, Problem 24E

Program Plan Intro

Backtracking:

Back tracking is a form of recursion.

In this method it is possible to backtrack if traversal reaches a node which has no other way from that to find solution.

It can be used to solve problems like eight queens puzzle and maze problem.

Trace of “putQueen()”:

putQueen(0)

col = 0;

putQueen(1)

col = 0;

col = 1;

col = 2;

putQueen(2)

col = 0;

col = 1;

col = 2;

col = 3;

col = 3;

putQueen(2)

col = 0;

col = 1;

putQueen(3)

col = 0;

col = 1;

col = 2;

col = 3;

col = 2;

col = 3;

col = 1;

putQueen(1)

col = 0;

col = 1;

col = 2;

col = 3;

putQueen(2)

col = 0;

putQueen(3)

col = 0;

col = 1;

col = 2;

.Q..

...Q

Q...

..Q.

col = 3;

col = 1;

col = 2;

col = 3;

col = 2;

putQueen(1)

col = 0;

putQueen(2)

col = 0;

col = 1;

col = 2;

col = 3;

putQueen(3)

col = 0;

col = 1;

..Q.

Q...

...Q

.Q..

col = 2;

col = 3;

col = 1;

col = 2;

col = 3;

col = 3;

putQueen(1)

col = 0;

putQueen(2)

col = 0;

col = 1;

col = 2;

putQueen(3)

col = 0;

col = 1;

col = 2;

col = 3;

col = 3;

col = 1;

putQueen(2)

col = 0;

col = 1;

col = 2;

col = 3;

col = 2;

col = 3;

2 solutions found

Answer 8

Expert Solution & Answer

Answer 9

Expert Solution & Answer

Answer 10

Want to see the full answer?

Check out a sample textbook solution

See solution

Answer 11

Ch. 5 - Prob. 1E Ch. 5 - Prob. 2E Ch. 5 - Prob. 3E Ch. 5 - Prob. 4E Ch. 5 - Prob. 5E Ch. 5 - Prob. 6E Ch. 5 - Prob. 7E Ch. 5 - Prob. 8E Ch. 5 - Prob. 9E Ch. 5 - Prob. 10E

Solution Summary: The author explains how backtracking is used to solve puzzles like the eight queens and mazes. The “putQueen()” function assigns a queen in each row without any conflicts.

Concept explainers

Want to see the full answer?

Chapter 5 Solutions