logo CodeStepByStep logo

Main Page → Exercises → C++ → Solve an Exercise

solveQueens

Language/Type: C++ recursion backtracking

Write a recursive function named solveQueens that tries to find all ways to place N queens on an NxN chess board such that no queen can attack another queen. For example, the following is a solution for the 8 queens problem:

queens

Your function will be passed a reference parameter of type Board representing a chess board. Your goal is to place queens on that board until all N of them are in safe locations, then print the board to the console. You must and print all possible solutions where N queens are placed safely. You can print the solutions in any order. If there are no valid solutions, print no output.

The Board class has the following public members. (All members that accept row or column indexes are 0-based.)

Public Member Description
Board b(size); construct an empty board
b.isSafe(row, column) true if a queen could be safely placed here
b.isValid() true if all currently placed queens are placed in safe locations
b.place(row, column); places a queen here
b.remove(row, column); removes a queen from here
out << b prints a text display of the board
b.toString() returns a text display of the board

Constraints: You may use loops in solving this problem if you like, but your overall solution must use recursive backtracking. You may define helper functions if you like.

Function: Write a C++ function as described, not a complete program.

You must log in before you can solve this problem.

Log In

Need help?

Stuck on an exercise? Contact your TA or instructor.

If something seems wrong with our site, please

Is there a problem? Contact us.