My program needs to execute in 3 seconds, and currently has a run time of 30+ se

Question

My program needs to execute in 3 seconds, and currently has a run time of 30+ seconds for inputs such as:

"8 9"

"8 10"

"8 15"

I've tried altering the while loops to for loops, but it doesn't seem like it's reducing the runtime much. Any ideas, information, or variations on implementation regarding this? The problem is described below.

===================================================

#include <cstdlib>
#include <new>
#include <iostream>
#include<stdio.h>
#include <time.h>
#include <unistd.h>
using namespace std;

/*
A bishop is a piece used in the game of chess which can only
move diagonally from its current position. Two bishops attack
each other if one is on the path of the other. Given two numbers n and k, determine the number of
ways one can put k bishops on an n × n chessboard so that
no two of them are in attacking positions.

The input file may contain multiple test cases. Each test
case occupies a single line in the input file and contains two
integers n (1 n 8) and k (0 k (n*n)).
A test case containing two zeros terminates the input.
*/

//chessboard is an array of squares, where piece is a bishop and chessboard[piece] is the square the bishop occupies
bool validMove(int chessboard[], int piece, int n){
//identify the row and col the bishop is in
int row = chessboard[piece]/n;
   int col = chessboard[piece]%n;
   int curRow, curCol;

for(int i=0; i<piece; i++)
   { //for every bishop
curRow = chessboard[i]/n;
curCol = chessboard[i]%n;

//diagonal test
if(abs(row-curRow)==abs(col-curCol))
       {
           return false;
       }
}

return true;
};

bool solutionFound(int &bishop, int count, int n, int k){
bishop--;
  
   if(n == 0 && k == 0)
   {
       return false;
   }
  
  
if(bishop==-1)
   {
cout << count << endl;
return false;
   }
   else
   {
       return true;
   }
};

int bishopBacktrack(int n, int k, int chessboard[])
{
int solutions = 0, piece = 0;
       int temp;
chessboard[piece] = 0;

while(true)
       { //until all soln found
           bool breakFlag = false;

while(piece<k)
           { //for each bishop
while(chessboard[piece]<n*n)
               { //for each square
if(validMove(chessboard,piece,n)) break;
else chessboard[piece]++;
}

if(chessboard[piece]==n*n)
               {
                  
                   breakFlag = !solutionFound(piece, solutions, n, k);
                   if(breakFlag)   break;

chessboard[piece]++;
continue;
}

else
               {
temp = chessboard[piece];
piece++;
chessboard[piece] = temp;
}
}
           if(breakFlag)   break;
solutions++;
          
           breakFlag = !solutionFound(piece, solutions, n, k);
           if(breakFlag)   break;
chessboard[piece]++;
       }
};

//using backtracking
int main()
{
   int n,k;
while(n != 0)
   {
       clock_t tStart = clock();
//User input, where n is the board size and k is the number of bishops
cin >> n >> k;
int chessboard[k]; //a square on grid
       bishopBacktrack(n,k,chessboard);
       printf("Time taken: %.2fs ", (double)(clock() - tStart)/CLOCKS_PER_SEC);
}
return 0;
}

Explanation / Answer

the best ways to reduce runtimes are:

1. to minimize comparisions

2. to replace statements like a++ by a=a+1 (example chessboard[piece]++ by chessboard[piece]= chessboard[piece]+ 1 as it saves memory occupied.

3.while loops is fine but the statements inside should be minimized exactly to the point what is required by the program.

4.do not use too many continue statements as this will increase more memory.

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.