As usual I know I'm probably doing something stupid. I'm trying to write the program below but I seem to have handled my queue incorrectly. The problem could be in one of three places; the way i handle moving on to the next node, my addboard function or my printsol function. Sadly it may be all three. I've been working on it and changing as much as I can over and over again all to no avail. Any suggestions would be much appreciated. I've attached the question and my code.
Thanks
Conway’s Soldiers
The one player game, Conway’s Soldiers (sometimes known as Solitaire Army), is similar to peg
solitaire. For this exercise, Conway’s board is a 7 (width) × 8 (height) board with tiles on it. The
lower half of the board is entirely filled with tiles (pegs), and the upper half is completely empty.
A tile can move by jumping another tile, either horizontally or vertically (but never diagonally)
onto an empty square. The jumped tile is then removed from the board.
The user enters the location of an empty square they’d like to get a tile into, and the program
demonstrates the moves that enables the tile to reach there (or warns them it’s impossible). To do
this you will use a list of boards. The initial board is put into this list. Each board in the list is, in
turn, read from the list and all possible moves from that board added into the list. The next board
is taken, and all its resulting boards are added, and so on. However, one problem with is that
repeated boards may be put into the queue and cycles occur. This soon creates an explosively
large number of boards (several million). You can solve this by only adding a board into the list
if an identical one has never been put into the list before. A linear search is acceptable for this
task. Each structure in the list will contain (amongst other things) a board and a record of its
parent board, i.e. the board that it was created from.
Write a program that:
• Inputs a target location for a tile to reach (x in argv[1], y in argv[2]).
• Demonstrates the correct solution (reverse order is fine) using SDL graphics which we
used as part of the unit.
Note that it is perfectly acceptable to use a (very large) array for this list - it doesn’t have to be a
linked list.
Use the algorithm described above and not anything else.
The assessment includes checking for
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BCOL (8)
#define BROW (9)
typedef struct node{
char board[BCOL][BROW]; //Board
int boardnum;
struct node *parent; //Board's parent
struct node *next; //Node that follows
}Node;
/*Queue Structure*/
typedef struct qu{
Node *headQ; //First node in the queue
Node *tailQ; //Last node in the queue
}Qu;
void printboard(Node *activeB);
void addboard(Node *tmpN, Qu *queue);
void printsol(Node *lastBoard);
void playboard(Node *boardN, int x, int y);
int main(int argc, char *argv[])
{
Node *boardN;
int x, y, col, row;
boardN = (Node *)malloc(sizeof(Node));
if(boardN==NULL) {
printf("\nThe malloc failed\n");
exit(0);
}
/*Retrieve target location*/
if(argc > 2) {
x = atoi(argv[1]);
y = atoi(argv[2]);
if(x>6||y>3||x<0||y<0) {
printf( "Your target location is not within the confines of the unoccupied board\n" );
exit(0);
}
}
else {
printf( "You have entered an incorrect target location\n" );
exit(0);
}
/*Intializing board*/
for(row=0; row<4; row++) {
for(col=0; col<7; col++) {
boardN->board[col][row]='.';
}
}
for(row=4; row<8; row++) {
for(col=0; col<7; col++) {
boardN->board[col][row]='O';
}
}
boardN->parent=NULL;
boardN->next=NULL;
playboard(boardN, x, y);
return 0;
}
void printboard(Node *activeB)
{
int row=0, col=0;
for(row=0; row<8; row++) {
for(col=0; col<7; col++) {
printf("%c ", activeB->board[col][row]);
}printf("\n");
}printf("\n");
}
void addboard(Node *tmpN, Qu *queue)
{
tmpN->parent = queue->headQ;
tmpN->next = NULL;
queue->tailQ->next = tmpN;
queue->tailQ = tmpN;
//printboard(tmpN);
}
void printsol(Node *lastBoard)
{
int row=0, col=0;
//printf("Solution\n");
if(lastBoard != NULL) {
for(row=0; row<8; row++) {
for(col=0; col<7; col++) {
printf("%c ", lastBoard->board[col][row]);
}printf("\n");
}printf("\n");
}
else exit(0);
printsol(lastBoard->parent);
}
void playboard(Node *boardN, int x, int y)
{
int col, row, headN = 0;//, bn=0;
Node *tmpN;
Qu *queue;
tmpN = (Node *)malloc(sizeof(Node));
queue = (Qu *)malloc(sizeof(Qu));
queue->headQ = queue->tailQ = boardN;
while(queue->headQ->board[x][y] != 'O') { //Used to stop playing the game
//printboard(queue->headQ);
for(row=0; row<8; row++) {
for(col=0; col<7; col++) {
if(queue->headQ->board[col][row] == 'O') {
//printf("\nRow: %d, Col: %d = %c", row, col, queue->headQ->board[row][col]);
/*Top search*/
if(row>1){
if(queue->headQ->board[col][row-1]=='O' && queue->headQ->board[col][row-2]=='.') {
printf("\nTop move made");
printf("\nRow: %d, Col: %d\n", row, col);
tmpN = queue->headQ;
tmpN->board[col][row] = '.';
tmpN->board[col][row-1]= '.';
tmpN->board[col][row-2]= 'O';
addboard(tmpN, queue);
if(queue->headQ->next == NULL && headN == 0) { //To put the second node into the queue
queue->headQ->next = tmpN;
headN=1;
}
}
}
/*Right search*/
if(col<5){
if(queue->headQ->board[col+1][row]=='O' && queue->headQ->board[col+2][row]=='.') {
printf("\nRight move made");
printf("\nRow: %d, Col: %d\n", row, col);
tmpN = queue->headQ;
tmpN->board[col][row] = '.';
tmpN->board[col+1][row]= '.';
tmpN->board[col+2][row]= 'O';
addboard(tmpN, queue);
if(queue->headQ->next == NULL && headN == 0) { //To put the second node into the queue
queue->headQ->next = queue->tailQ;
headN=1;
}
}
}
/*Bottom search*/
if(row<6){
if(queue->headQ->board[col][row+1]=='O' && queue->headQ->board[col][row+2]=='.') {
printf("\nBottom move made");
printf("\nRow: %d, Col: %d\n", row, col);
tmpN = queue->headQ;
tmpN->board[col][row] = '.';
tmpN->board[col][row+1]= '.';
tmpN->board[col][row+2]= 'O';
addboard(tmpN, queue);
if(queue->headQ->next == NULL && headN == 0) { //To put the second node into the queue
queue->headQ->next = queue->tailQ;
headN=1;
}
}
}
/*Left search*/
if(col>1){
if(queue->headQ->board[col-1][row]=='O' && queue->headQ->board[col-2][row]=='.') {
printf("\nLeft move made");
printf("\nRow: %d, Col: %d\n", row, col);
tmpN = queue->headQ;
tmpN->board[col][row] = '.';
tmpN->board[col-1][row]= '.';
tmpN->board[col-2][row]= 'O';
addboard(tmpN, queue);
if(queue->headQ->next == NULL && headN == 0) { //To put the second node into the queue
queue->headQ->next = queue->tailQ;
headN=1;
}
}
}
}
}
} row=col=0;
queue->headQ = queue->headQ->next; //Move to the next board
if(queue->headQ->board[x][y] == 'O') {
printsol(queue->headQ);
exit(0);
}
else {
printf("\nNo solution can be found\n");
exit(0);
}
}
}