CSCI 211 Midterm

ok function for 8 queens 1D

bool ok(int q[], int c)

{

  for (int i = 0; i < c; i++)

  {

     if (q[i] q[c] || abs(q[i] - q[c]) c - i)

         {

             return false; 

         }

  }

  return true; 

}

ok function for eight numbers in a cross

for (int i = 0; i < c; ++i)

     if (q[i] == q[c])

        return false;

  for (int i = 0; adj[c][i] != -1; ++i)

     if (abs(q[c] - q[adj[c][i]]) == 1)

        return false;

  return true;

ok function for stable marriage

for (int i = 0; i < col; ++i) {                                   

     if (q[i] == q[col] || mp[i][q[col]] < mp[i][q[i]] && wp[q[col]][i] < wp[q[col]][col] || mp[col][q[i]] < mp[col][q[col]] && wp[q[i]][col] < wp[q[i]][i])

        return false;                                             

  }

  return true;

}

why the “dumb” eight-queens solution is not optimal

Dumb Eight Queens is not an optional solution because it factors in an exhaustive search approach where we go through every possible index to find a working solution. This hinders time complexity which deteriorates the efficiency of our program.

8 Queens 2D - Row Test

for(int i=0;i<c;i++)

{

if(q[r][c]==q[r][i]) goto nextRow;

}

8 Queens 2D - Up Diagonal Test

for(int i=1;(r-i)>=0 && (c-i)>=0;i++)

{

if(q[r-i][c-i]==1) goto nextRow;

}

8 Queens 2D - Down Diagonal Test

for(int i=1;(r+i)<8 && (c-i)>=0; i++)

{

if(q[r+i][c-i]==1) goto nextRow;

}

Backtrack for 8 Queens 2D

c--;

if(c==-1) return 0;

r=0;

while(r<8&&b[r][c]==0) r++;

if(r==8) goto backtrack;

b[r][c]=0;

goto nextRow;

All in one test for 8 Queens 1D w goto

for(int i=0; i<c; i++)

{

if(q[c]==q[i] || (c-i) == abs(q[c]-q[i])) goto nextRow;

}

Backtrack for 8 Queens 1D w goto

c--;

if(c==-1) return 0;

goto nextRow;

ok function for 8 Queens 1D w/o goto

bool(int q[],int c)

{

for(int i=0; i<c; i++){

if(q[c]==q[i] || (c-i) == abs(q[c]-q[i])) return false;

}

return true;

}