1.6 queens: (N + 1)-queens ------ IN C

Write a program queens that implements part of the search process for solving the N-queens problem. queens has one required argument and two optional arguments. The required argument will always occur last: it is the name of a file containing a chessboard.

The two optional arguments may occur individually or together in any order. They are +2, which indicates that queens should report whether two queens may be placed on the board (Part 2), and

-w, which allows for the presence of warrior queens (Part 3). This portion of the assignment has three parts, two of which are required. The third part will be

counted as extra credit.

Background A chessboard is an 8 8 grid of squares, each of which may contain up to one chess piece.

The queen is the most powerful piece in chess, capable of moving any number of squares vertically, horizontally, or diagonally, provided that it does not change direction during the move.

The N-queens problem asks how many ways N queens can be arranged on a board such that no queen can take another. That is, no queen can be moved to a square occupied by another queen in a single move.

Part 1 Your program will be given a chessboard with some number of queens already placed. Your program must first determine whether any queen can take any other queen. If so, it will printInvalid. If not, it will determine, for each empty square, whether a queen placed there could be taken by any other queen. It will print a new chessboard with these available squares marked with q.

Part 2 When +2 is given, your program will further determine if there is any way to place twoadditional queens on the board such that no queen can take any other queen. If this is possible,queens will print Two or more. If only one queen may be placed, queens will print One. If no queens may be placed, queens will print Zero.

Part 3 (Extra credit) A warrior queen is a queen that fights on horseback, and thus may move like a queen or like a knight. The knight moves in an L-shape: two squares horizontally and one square vertically, or two squares vertically and one square horizontally. Thus, a warrior queen may reach up to eight squares that a regular queen in the same position could not.

When -w is given, queens will consider boards that may contain warrior queens and distinguish between squares where a warrior queen may be placed (marked w) and squares where only a regular queen may be placed (marked q). Additionally, queens will accept chessboards containing warrior queens.

Input format The input will contain a chessboard, specified as eight lines containing eight characters. A . indicates an empty space, and a Q indicates a queen.

A W indicates a warrior queen. Behavior is unspecified if the chessboard contains a warrior queen, but the -w option has not been given.

Your program will not be tested with incorrectly formatted chessboards. 9

Output format If any queens on the board may take another, queens will print Invalid and terminate. Otherwise, queens will print a chessboard similar to the input, but with additional symbols q and w to indicate squares where a queen or warrior queen may be placed. The mark wwill only be used if the -w option is given.

Next, if the +2 option is given, queens will print Zero, One, or Two or more, depending on how many additional queens may be safely placed on the board.

Usage Assume the file board.txt contains the following chessboard:

........ ........ ....Q... ......Q. ........ ..Q..... ........ ........ 

Then,

$ ./queens board.txt qq...q.. qq.....q ....Q... 

......Q. q....... ..Q..... .....q.q .q.q.q.q $ ./queens +2 -w board.txt ww...q.. 

ww.....q ....Q... ......Q. q....... ..Q..... .....w.w .q.q.w.w Two or more