lab7.tar

nqueens.cpp0000600006513700162730000000403614326127766013026 0ustar  lsmit248lsmit248// Lab 7:  N-queens using backtracking 
/*Laura Smith 11:58 PM Lab 7 Part 1
This lab was to learn about recursion. We used a recursive statement to solve the nqueens problem, which is a problem
where on an nxn board how can you arrange chess queens so they all aren't in the line of fire of another. We used recursion
to go throuh all the possible boards and check if they were valid, printing only the valid boards.
*/

#include <iostream>

using namespace std;

//checks if a board is valid and returns as either true or false
bool valid (int board[], int size){

//double nested for loops that iterate through each possible combination of two spots on the board
//returns false if the two spots are in the same row, or if they are on the same slope, otherwise returns true
  for (int i=0; i < size; i++){
    for (int j= i + 1; j < size; j++){
      int board_first = board[i];
      int board_second = board[j];

      if (board_first == board_second){
        return false;
      }
      else if ((abs(board_first - board_second) == abs(i-j))){
        return false;
      } 
    }
  }

  return true;
}

//recursive function that takes an array, column number, and size of the board
void nqueens (int board[], int col, int size){

//if statement to check if a board is valid before continuing
  if (valid (board, col-1)){

//prints out the board when the board is full
    if (col == size){

        if (valid (board, size)){
          cout << board[0];
          for (int i = 1; i < size; i++){
            cout << ", " << board[i]; 
          }
          cout << endl;
        }
      }

//until the board is full runs the recursive statement to fill it
    else {
        for (int i = 0; i < size; i++){
          board[col] = i;

          nqueens (board, col+1, size);
        }
      
    }

  }

}

int main(int argc, char *argv[]) {

  int size = atoi (argv[1]);  //reads in from the command line to get the size
  int board[size];            //creates the board of the specified size

  nqueens (board, 0, size);   //begins the recursive function

  return 0;

}
nqueens2.cpp0000600006513700162730000000446214326127757013113 0ustar  lsmit248lsmit248// Lab 7:  N-queens using backtracking 
/* Laura Smith 11:58 PM Lab 7 Part 2
In this part I added in another validity check to check the validity of the board as it is being made to decrease the time
it takes to calculate the valid boards. I also added a counter that counts the number of boards that are checked to be valid.
*/

#include <iostream>

using namespace std;

int count {}; //Global variable to keep counts of how many boards are checked

//checks if a board is valid and returns as either true or false
bool valid (int board[], int size){

//double nested for loops that iterate through each possible combination of two spots on the board
//returns false if the two spots are in the same row, or if they are on the same slope, otherwise returns true
  for (int i=0; i < size; i++){
    for (int j= i + 1; j < size; j++){
      int board_first = board[i];
      int board_second = board[j];

      if (board_first == board_second){
        return false;
      }
      else if ((abs(board_first - board_second) == abs(i-j))){
        return false;
      } 
    }
  }

  return true;
}

//recursive function that takes an array, column number, and size of the board
void nqueens (int board[], int col, int size){

//if statement to check if a board is valid before continuing
  if (valid (board, col-1)){

//prints out the board when the board is full
    if (col == size){

//counts the amount of boards considered with constraints
      count++;

        if (valid (board, size)){
          cout << board[0];
          for (int i = 1; i < size; i++){
            cout << ", " << board[i]; 
          }
          cout << endl;
        }
      }

//until the board is full runs the recursive statement to fill it
    else {
        for (int i = 0; i < size; i++){
          board[col] = i;

          nqueens (board, col+1, size);
        }
      
    }

  }

}

int main(int argc, char *argv[]) {

  int size = atoi (argv[1]);  //reads in from the command line to get the size
  int board[size];            //creates the board of the specified size
  count = 0;                  //starts count at 0 for each time

  nqueens (board, 0, size);   //begins the recursive function

  cerr << endl << "# of boards considered with constraint for n = " << size << " is " << count << endl << endl; //error statement to print out count

  return 0;

}
report.txt0000600006513700162730000000307114326130054012676 0ustar  lsmit248lsmit248Laura Smith 11:58 PM Lab 7 Part 3 

boards considered for n = 8 - 2496
boards considered for n = 10 - 40400

- In your own words, what is the benefit of a recursive solution to enumerate all of the nqueens potential solutions: 

The benefit is to save time and resources, it is also an easy way to reduce the amount of code you need to write to complete a task. Recursion
helps especially when you need something done multiple times, and when each time you call it the previous values are needed. Examples of when
they're helpful are games like the towers of hanoi and sudoku, each time you look to do the same algorithm, but each time the board changes which
changes what the algorithm spits out. For nqueens, each time you need to check different boards to see if they're valid after making a board, and 
how the board gets checked doesn't change, but the board changes each time. It also makes the code simpler and have the code do the calculating 
by itself. For nqueens one could calculate by hand the solutions then print them but a recursive statement does it for us.

- Also in your own words, what are the theoretical and/or practical advantages of constraining the search space to only still valid solutions?:

The benefit is to save a lot of time, the time before and after the constraints are very different and the amount of boards considered went 
down considerably. Testing if they're valid first helps the program run faster, as there are less boards that the program needs to go through. Doing
this speeds up the recursion and makes the code more efficient.