8 Queens Chessboard Placement | 2006-01-21

Portfolio » Application Programming

8 Queens Chessboard placement in C++ label and goto

// 8queens.cpp : Defines the entry point for the console application.
//Written by [email protected]

#include "stdafx.h"
#include <iostream>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    int b[8][8] = { 0 };
    int r, count = 0;

    b[0][0]=1;
    int c = 0;

next_col:
    ****************************
    ****************************


next_row:
    r++;
    if (r == 8)
        goto backtrack;
    if (c == 8)
        goto print;

    // check for clash in present row
    for (int i = 0; i < c; i++)
        if(b[r][i]==1)
            goto next_row;
   
    // check for clash in diagonal
    for (*** *** *** *** *** *** *** )
        if(b[r-i][c-i]==1)
            goto next_row;

    for (int i = 1; r + i < 8 && c - 1 >= 0; i++)
        if(b[r+i][c-i]==1)
            goto next_row;

    if (c <= 8)
    {
        b[r][c] = 1;
        goto next_col;
    }

backtrack:
    c--;
    if (c==-1)
        cout << "there are" << count << " solutions" << endl;

    r = 0;
    while (b[r][c] != 1)
        r++;
    b[r][c] = 0;
    goto next_row;

print:
    cout << count + 1 << endl;

    for (int i = 0; i < 8; i++, cout << endl)
        for (int j = 0; j < 8; j++)
            cout << b[i][j];
    count++;
    goto backtrack;

    return 0;
}
 

*** indicated that some partial codes has been removed

 

 

 

Log(n) implimention to solve this problem

 

//Written by [email protected]

#include <iostream>
using namespace std;

int main(){
    int q[8],c;
    int i;
    int x=1;
    q[0]=0;
    c=0;
Next_col:c++;
    if(c==8) goto print;
    q[c]=-1;
Next_row:q[c]++;
    if(q[c]==8) goto backtrack;
    //row_test
    for(i=0;i<c;i++)
            ****************************
    //up diag
    for(i=0;i<c;i++)
        if(q[c]==q[i]||c-i==abs(q[c]-q[i]))
            goto Next_row;
    goto Next_col;
backtrack:c--;
    if(c==-1)
        return 0;
    goto Next_row;
print:
    int board[8][8]={0};
    int r,col;
    for(i=0;i<8;i++)
        board[q[i]][i]=1;
    for(col=0;col<8;col++){
    for(r=0;r<8;r++){
        cout<<board[r][col];
    }
    cout<<endl;
       }
       cout<<"********The "<<x<<" Solution"<<endl;
       x++;
    goto backtrack;
    return 0;
}

  *** indicated that some partial codes has been removed

 

Using while loops to solve this problem

 

// Written by [email protected]

#include <iostream>
#include <math.h>
using namespace std;

bool ok(int q[], int c)
{
    for(int i = 0; i < c; i++ )
        if(q[i] == q[c] || c-i == abs(q[c] - q[i]))
            return false;
    return true;

}

void print(int q[], int size, int cntr )
{
    cout << "This is the No. " << cntr <<" solution." <<endl;
    for(int i = 0; i < size; i++ )
        cout << q[i];
    cout << endl;
}

int main(){
    int q[8],c=0;
    q[0] = 0;
    int cntr = 0;
    bool nr = false, nc = false, bt=false;
    while( c != -1 )
    {
        if( bt == false )
        {
            c++;
        }
        if ( *** )
        {
            if( bt == false )
            {
                ***
            }
            while ( q[c] != 8 )
            {
                q[c]++;
                if(q[c] == 8)
                {
                    c--;
                    if(c == -1)
                        return 0;
                    continue;
                } //if(q[c]
                if( ok(q,c))
                {
                    nc = true;
                    break;
                }//if(ok(q,c
            }//while(q[c] != 8
        }//if(c != 8
        if( nc == true )
        {
            nc = false;
            bt = false;
            continue;
        }
        print(q,8,++cntr);
        c--;
        bt = true;
    }//while(c != -1
    return 0;
}

  *** indicated that some partial codes has been removed

 

 

 

Using for Loops

 

 


//Written by [email protected]
#include <iostream>
using namespace std;
int main(){
   eightQueens();
   return 0;
}

bool ok(int q[],int size){
    for(int i=1;i<size;i++){
        for(int j=0;j<i;j++){
            if(q[i]==q[j]||i-j==abs(q[i]-q[j]))
               *** *** *** ***
        }
    }
    return true;
}

void eightQueens(){
  int q[8];
  int a,b,c,d,e,f,g,h;
  int cntr = 0;

  for (a=0; a <8; a++)
    for (b = 0; b < 8; b++ )
      for( c = 0; c < 8; c++ )
        for ( d = 0; d < 8; d++ )
          for ( e = 0; e < 8; e++ )
            for ( f = 0; f < 8; f++ )
              for ( g = 0; g < 8; g++ )
                for ( h = 0; h < 8; h++ )
                {
                  q[0] = a;
                  q[1] = b;
                  q[2] = c;
                  q[3] = d;
                  q[4] = e;
                  q[5] = f;
                  q[6] = g;
                  q[7] = h;
                  if(*** *** *** *** *** *** ){
                      cout << a << b << c << d << e << f << g << h << endl ;
                      cout << "This is the No. " << ++cntr <<" solution." <<endl;
                  }
                }
}
 

*** indicated that some partial codes has been removed