CS211 k bishops on an nXn chessboard We have previously solved the N Queens Prob
ID: 3556808 • Letter: C
Question
CS211 k bishops on an nXn chessboard We have previously solved the N Queens Problem, where, for a given n, we calculated the number of ways to place n queens on an nXn board. This problem concerns bishops on the chessboard. What is a bishop? A bishop is a chess piece that controls all the squares on the two diagonals that it can reach. Note that a bishop may be either on a white square or a black square. The problem Write a program that inputs two integers n and k, where n>=k. Your program should calculate the number of different ways that k bishops could be placed on an nXn chessboard. Structure your program using the backtracking scheme that we have used for the eight queens problem. What needs to be modified is the OK function. Input Your main program should loop asking the user for values of n and k. Output Each time through the loop, output n, k and the number of configurations. Program Termination The program will terminate if the user enters a value of -1 for n.
Explanation / Answer
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include<ctype.h>
using namespace std;
enum Direction {
FwdRight,
RightFwd,
RightBack,
BackRight,
BackLeft,
LeftBack,
LeftFwd,
FwdLeft
};
void printBoard(char * marks, int turn);
int initialize(char *board);
int convertIndexToRowCol(int index, int *row, int *col);
int convertRowColToIndex(int row, int col, int *index);
int convertNameToIndex(char *name, int *index);
char * convertIndexToName(int index);
int findAvailMoves(int position, char *board, int *moves);
int bestWarnsdorff(int position, char *board, int * movesAvail);
int promptAndReply(char * message, char * response, int responseLen);
void stringToUpper (char *buffer);
void getCommandLineArgs(int argc, char **argv);
int ARG_Debug = 0; // if command line arg "ARG_Debug" is given, each step
// of the move selection process will be displayed
main(int argc, char **argv)
{
char boardState[64], tmp[3];
int movesAvail[8], turns, validMoves, curPos, newPos, trace=0;
int a, openWin=0, closedWin=0, lost=0;
srand ((unsigned)time(NULL)); // seed pseudo-random generator
getCommandLineArgs(argc,argv); // check command line
do {
// clear board position index, get initial (start) pos from user
curPos = newPos = 0; turns = 1;
memset(boardState, 0, 64);
curPos = initialize(boardState);
while (curPos != -1) // continue unless error
{
// from current position, find number of valid moves available
validMoves = findAvailMoves(curPos,boardState,movesAvail);
if (validMoves == 0) // tour is done, no moves available
break; // break from while() loop
if (++turns > 64) // can only occur on a "closed win"
break;
// of the valid moves available, find which is "best"
newPos = bestWarnsdorff(curPos,boardState,movesAvail);
boardState[newPos] = turns; // move to that best position
printBoard(boardState, turns); // redraw new board state
curPos = newPos; // new best postion -> current
// if all squares have been toured, clear initial position
// if it can be attacked, is "closed win", otherwise "open"
if (turns==64)
for (a=0; a<64; a++)
if (boardState[a]==1) // found the initial position
{
boardState[a]=0; // clear it
break; // done here, break from FOR
}
}
printf(" Final Pos: %s Result : ",
convertIndexToName(curPos));
if (turns==65) // if inital pos a valid move after the 64th turn
{
printf("CLOSED WIN !!! ");
closedWin++;
}
else if (turns==64)
{
printf("Open Win ");
openWin++;
}
else if (curPos != -1) // "quit to exit" is not a failure
{
printf("well, crap... ");
lost++;
}
else
printf("User Quit ");
printf(" Totals : Closed %d, Open %d, Lost %d ",
closedWin, openWin, lost);
promptAndReply("hit <enter> to continue ",tmp, sizeof(tmp));
}
while (curPos != -1);
printf("Bye. ");
}
int bestWarnsdorff(int position, char *board, int * movesAvail)
// uses the Warnsdorff Algorithm to determine "best" of all available
// moves with goal of completing the Knight's Tour. If there two or
// more equally "best" moves, one will be chosen randomly. This
// allows "open solutions" to occur more often than "closed solutions"
// Choosing among equally "best" moves to prefer a closed solution is
// beyond scope of Warnsdorff's Algorithm
//
// input: position (1D index value) of the Knight's current location
// board array indicating state of all spaces on board
// movesAvail array showing which directions valid/available
//
// return: 1D index value of the "best" board position for next move
{
int newPos, bestMove, score, bestScore, numBest,
direction, locations[8];
double pct, rval;
char tmp[3];
bestScore = 9; // start high possible, better scores will be lower
numBest = 1; // number of equally-lowest (best) scores found
//check each of the 8 ordinal directions Knight is able to move
for (direction=0; direction<8; direction++)
{
// if direction is valid/available, it will be the index number
// of the position (0-63) of the resulting move
newPos = movesAvail[direction];
if (newPos >= 0)
{
// grade the new position to how many "entrances" it has
score = findAvailMoves(newPos,board,locations);
if (ARG_Debug)
printf("move to %s score %d ",
convertIndexToName(newPos),score);
if (score < bestScore) // new position with lowest score
{
numBest=1; // reset count of equally low scores
bestScore = score; // new score becomes the best score
bestMove = newPos; // new position becomes the new best
}
else if (score == bestScore)// if new best equals current
{ // choose between the two bests
pct = 1.0/++numBest; // based on number of ties
rval = (double)rand() / (double)RAND_MAX;
if (rval < pct) // if random # is within % chance
bestMove = newPos; // replace current best w/ new
}
}
}
if (ARG_Debug)
{
printf(" ... selected %s",convertIndexToName(bestMove));
promptAndReply("",tmp, sizeof(tmp));
}
return bestMove;
}
int findAvailMoves(int position, char *board, int *moves)
// using current position, check each of the 8 ordinal directions that a
// knight can move, whether the direction lands on a valid and available
// space. invalid moves land off board. unavailable moves land on
// spaces that have already been "toured"
//
// input: "position" of knight described as 1D board array index (0-63)
// "board" array describing current state of all board positions
//
// output: "moves" array describing each of 8 ordinal directions the
// knight could conceivably move. if the move is invalid or
// unavailable, the element is flagged -1 or -2
// if the move is valid and available element written with 1D
// board array index value (0-63) of resulting space
//
// return: numeric value between 0 and 8 of the total number of valid and
// available moves from the current position.
// if an error occurs, the return value will be 0.
{
//enum Direction direction;
int direction;
int row,col,index, numAvailable;
numAvailable=0; // count of valid and available moves
for (direction=0; direction<8; direction++)
{ // convert 1D index to 2D row and column values
convertIndexToRowCol(position, &row,&col);
switch (direction) // based on each direction, calculate where
{ // each move would land
case (FwdRight):
row+=2; col++;
break;
case (RightFwd):
row++; col+=2;
break;
case (RightBack):
row--; col+=2;
break;
case (BackRight):
row-=2; col++;
break;
case (BackLeft):
row-=2; col--;
break;
case (LeftBack):
row--; col-=2;
break;
case (LeftFwd):
row++; col-=2;
break;
case (FwdLeft):
row+=2; col--;
break;
default : // invalid input returns zero, ending program
printf(" *** FindAvailMove: switch statement Error! ");
return 0;
}
// check if the new row and/or column are out of bounds
if (convertRowColToIndex(row, col, &index) == -1)
moves[direction]=-1; // flag direction as invalid
// check if position was marked as "toured" from a previous turn
else if (board[index]>0)
moves[direction]=-2; // flag direction as unavailable
else // move is valid and available
{
moves[direction]=index;
numAvailable++;
}
}
return numAvailable;
}
int convertIndexToRowCol(int index, int *row, int *col)
// convert the 1D board array index to corresponding row and column values
//
// input: index for board array is a value from 0-63
//
// output: row is value from 0-7
// col is value from 0-7
//
// return 0 if success, -1 if invalid input
{
if (index < 0 || index > 63)
return -1;
*row = index / 8;
*col = index % 8;
return 0;
}
int convertRowColToIndex(int row, int col, int *index)
// convert row and column values to corresponding 1D board array index
//
// input : row is value from 0-7
// col is value from 0-7
//
// output: index for board array is a value from 0-63
//
// return: 0 if success, -1 if invalid input
{
if (row<0 || col<0 || row>7 || col>7)
return -1;
*index = row*8 + col;
return 0;
}
int convertNameToIndex(char *name, int *index)
// take the standard (algebraic) space name ("A2", "D4", etc)
// convert to the 1D board array index number
//
// input: pointer to NAME as ascii string, "A2", "D4", etc.
//
// output: 1D board array index value (0-63) or the flag value 999
// to indicate the user "quit" command was given
//
// return: 0 if success (including "quit"), -1 if invalid input
{
char spaceName[3];
//copy only the first two characters, ensure first is capitalized
strncpy(spaceName,name,2);
spaceName[3]=0;
spaceName[0]=toupper(spaceName[0]);
//only columns A-H & rows 1-8 (algebraic chess notation) are valid
if (spaceName[0] >= 'A' &&
spaceName[0] <= 'H' &&
spaceName[1] > '0' &&
spaceName[1] < '9'
)
*index = (spaceName[1]-0x31) * 8 + spaceName[0]-0x41; // 0-63
// exception for the first letter "Q" of user "quit" command
else if (spaceName[0] == 'Q')
*index = 999;
else
{
printf(" *** Error: '%s' is invalid ",spaceName);
*index = -1;
}
return (*index >= 0) ? 0 : -1; // 0 if success, -1 fail
}
char * convertIndexToName(int index)
// take the 1D array index number, convert it to the
// standard (algebraic) space name ("A2", "D4", etc)
//
// input: 1D board array index value (0-63)
//
// return: pointer to NAME as ascii string, "A2", "D4", etc.
// or NULL if invalid input
{
static char name[3];
if (index<0 || index > 63)
return NULL; // invalid index value
name[0] = (index % 8) + 0x41;
name[1] = (index / 8) + 0x31;
name[2] = 0;
return name;
}
void printBoard(char * marks, int turn)
// prints the entire board and marks all postions visited
// use unique marks for the current Knight position.
//
// input: requires board array (marks)
// current turn number
//
// outputs and returns nothing
//
{
int row, col, index;
system("cls");
printf(" Knight's Tour Turn %d ",turn);
printf(" ----------------------- ");
for (row=7; row>=0; row--)
{
printf(" %d |",row+1);
for (col=0; col<8; col++)
{
convertRowColToIndex(row, col, &index);
if (marks[index] == turn) // mark the knight's current space
printf("><");
else if (marks[index]) // mark the turn space was visited
printf("%2d",marks[index]);
else // leave blank, if not
printf(" ");
if (col==7)
printf("| ");
else
printf(" ");
}
if (row)
printf(" | + + + + + + + | ");
}
printf(" ----------------------- ");
printf(" A B C D E F G H ");
}
int initialize(char *board)
// starts the clean board and prompts user to choose start position
//
// output: updates array of board data via pointer
//
// return the 0-63 index value of the chosen start position if success
// -1 if function failed
{
char startPos[32];
int startIndex=-1;
do
{
printBoard(board,1);
promptAndReply(" Choose starting position or "q" to quit : ",
startPos, sizeof(startPos));
}
while(convertNameToIndex(startPos,&startIndex)); // return 0 success
if ( startIndex >= 0 && startIndex < 64)
{
board[startIndex] = 1; // "turn" number 1 is starting position
printBoard(board,1); // prints entire board, turn number = 1
return startIndex;
}
else
return -1;
}
int promptAndReply(char * message, char * response, int responseLen)
// prints prompt message to terminal, waits for input from user
//
// inputs: pointer to message string that prompts the user response
// maximum response string length (sizeof)
//
// outputs: pointer to null-terminated response string
// NOTE: any newline characters will be stripped
//
// returns: 0 if full user response was successfully read and stored
// 1 if any bytes still remain after input was processed.
// -1 if failure caused any other error
//
// notes: if a positive value is returned, the user input more
// characters than the calling routine anticipated.
// the caller is responsible for performing additional
// input processing on any remaining characters
{
char *buffer, *buff_ptr;
int remain=1;
buffer = (char*) malloc (responseLen);
buff_ptr = buffer;
printf("%s",message);
fgets(buffer,responseLen-1,stdin);
//newline read from stdin indicates end of user data
//delete the newline character(s).
//return flag indicates no data remains
while(*buff_ptr)
{
if (*buff_ptr == 0x0D || *buff_ptr == 0x0A)
{
remain = 0;
*buff_ptr = 0;
}
buff_ptr++;
}
strcpy(response,buffer);
free(buffer);
return remain;
}
void stringToUpper (char *buffer)
// converts any lowercase characters in a string to uppercase
// leaves non-lowercase and non-alpha character as they were
//
//
{
char * buffer_ptr = buffer;
size_t buffer_len = strlen(buffer);
while(buffer_len--)
*buffer_ptr=toupper(*buffer_ptr++);
}
void getCommandLineArgs(int argc, char **argv)
// parse all command line arguments each in turn
// matching against expected values and setting
// global variables accordingly.
//
// inputs: argc and argv from main()
//
// notes: currently only "ARG_Debug" is being checked.
// more argumetns can be added as desired
// arguments have a maximum length of 15 chars
// arguments are case insensitive
{
int a, argLen;
char argStr[16];
if (argc>1) // parse command line arguments
{
printf(" parsing command line args: ");
for (a=1; a<argc; a++)
{
argLen = (strlen(argv[a])>15)?15:strlen(argv[a]);
strncpy(argStr,argv[a],argLen);
argStr[argLen]=0;
stringToUpper(argStr);
if (strncmp(argStr,"ARG_Debug",5)==0)
ARG_Debug=1;
//add additional arguments as needed
printf(" arg[%d] = %s ",a,argStr);
}
promptAndReply(" hit <enter> to continue ...",argStr,3);
}
}