8 queen problem with a twist

  • (2 Pages)
  • +
  • 1
  • 2

16 Replies - 871 Views - Last Post: 04 August 2014 - 05:28 AM Rate Topic: **--- 3 Votes

#1 Darraptor  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 63
  • Joined: 11-May 14

8 queen problem with a twist

Posted 30 July 2014 - 03:44 PM

The problem I have to deal with is let the user give the starting position of q queens where q represents the number of queen(from 1-8) and I need to check to see whether or not this is valid. If its valid then the program must compute the rest of the queen. I;m having trouble coming up with the algorithm to determine if the placement of the queen(s) on the board is legal and coming up with a algorithm that will help put the other queens on the board. Here is what I have so far in my code with comments that will make it easier to follow along with what I did. Much help is appreciated

//---------------------------------------------------------------------------------------------------------------------------
//---------------------------------------------------------------------------------------------------------------------------

                                            //PROJECT ASSINGMENT

//The purpose of this program is to let the user give the initial position of m(greater than 0 and less than 9) Queens. The program first checks if these m Queens violate the eight Queen's rule(meaning among these m Queens, there is at least one pair of Queens that they can attack each other).If the input violates the rule, tell the user the input is illegal.If the input does not violate the rule, fixing these m Queens, computing the positions of the rest 8-m Queens. Note there could be no solution or multiple solutions

//---------------------------------------------------------------------------------------------------------------------------
//---------------------------------------------------------------------------------------------------------------------------

                                    //THINGS THAT THE PROGRAM CAN CURRENTLY DO

//The only the program does so far is ask user to input m queens's intital positon on the board. The program will check to see if the user puts in a valid amount of queens. If it isn't valid the program will exit telling the user that the input was invalid. The program will also check to see if the user puts in a legal initial position on the board.If the user tries to enter an initial positon that isnt within the range of 0 and 7 or puts in a coordinate point for one queen that would overlap with another queen on the chessboard then the program will exit. If everything is okay then the program will go to the function int compute_positon_of_remaining_queens() to add in the remaining queens in the correct position

//---------------------------------------------------------------------------------------------------------------------------
//---------------------------------------------------------------------------------------------------------------------------

                                            //MY TO DO LIST

// 1.Make the program check to see if the m Queens violate the 8 queen rule with the function int check_violation(); which should probably be implimented after the program checks to see if the queens don't overlap

// 2.Thinking of an algorithm to correctly put the remaining m queens in the function int compute_positon_of_remaining_queens();

//---------------------------------------------------------------------------------------------------------------------------
//---------------------------------------------------------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>

int board [8][8];//The chessboard
int m;//queens

int position_x1;//Position of queen 1 in x coordinate
int position_y1;//Position of queen 1 in y coordiante
int position_x2;//Position of queen 2 in x coordinate
int position_y2;//Position of queen 2 in y coordinate
int position_x3;//Position of queen 3 in x coorindate
int position_y3;//Position of queen 3 in y coordinate
int position_x4;//Position of queen 4 in x coordinate
int position_y4;//Position of queen 4 in y coordinate
int position_x5;//Position of queen 5 in x coordinate
int position_y5;//Position of queen 5 in y coorindate
int position_x6;//Position of queen 6 in x coordinate
int position_y6;//Position of queen 6 in y coordinate
int position_x7;//Position of queen 7 in x coordinate
int position_y7;//Position of queen 7 in y coordinate
int position_x8;//Position of queen 8 in x coorindate
int position_y8;//Position of queen 8 in y coordinate

int check_violation();//Checks to see if the queens don't attack each other
int compute_positon_of_remaining_queens();//Puts the other m queens in the correct position on the board so that the 8 queens wont attack each other

int main()
{
    for(int i=0;i<8;i++) //Creates an 8 by 8 chessboard with every spot being free
    {
        for (int j=0;j<8;j++)
        {
            board[i][j]=0;
        }
    }
    
    printf("Enter intitial positions of m queens\n");
    scanf("%d",&m);
    
    //After the user enters an m amount of queens,the user must give the x and y coordinates of each queen from 0-7 inclusive
    
    if(m==1)//input is 1 queen
    {
        scanf("%d",&position_x1); //Stores x&y coordinates(location on chessboard) of queen 1
        scanf("%d",&position_y1);
        
        if((position_x1>=0 && position_x1<8)&&(position_y1>=0 && position_y1<8))//If the coordinate points of the queen is legal then the program will compute the remaining positions of the 7 queens
        {
            check_violation();
            compute_positon_of_remaining_queens();
        }
        
        else//If user inputs illegal coordinates
        {
            printf("You did not enter a valid coordinate point(s) for the queen(s)\n");
            return 0;
        }
    }
    
    else if(m==2)//input is 2 queens
    {
        scanf("%d",&position_x1);  //Stores x&y coordinates(location on chessboard) of queen 1,2
        scanf("%d",&position_y1);
        scanf("%d",&position_x2);
        scanf("%d",&position_y2);
        
        if((position_x1>=0 && position_x1<8)&&(position_y1>=0 && position_y1<8)&&(position_x2>=0 && position_x2<8)&&(position_y2>=0 && position_y2<8))//Makes sure the user doesn't enter a coordinate point that isnt 0-7 i.e a character like a etc
        {
            if(position_x1==position_x2 && position_y1==position_y2)//This makes sure queen 1 and 2 don't overlap
            {
                printf("Cannot put two queens in the same spot\n");
                return 0;
            }
            
           else if((position_x1>=0 && position_x1<8)&&(position_y1>=0 && position_y1<8))//If the position of queen 1 and 2 don't overlap then the program will compute the remaining positions of the 5 queens after checking to see if they don't violate the 8 queen rule
           {
               check_violation();
               compute_positon_of_remaining_queens();
           }
        }
        
        else//If the coordinates are not legal then the function ends
        {
            printf("You did not enter a valid coordinate point(s) for the queen(s)\n");
            return 0;
        }
    }
    
    else if(m==3)//input is 3 queens
    {
        scanf("%d",&position_x1); //Stores x&y coordinates(location on chessboard) of queen 1,2,3
        scanf("%d",&position_y1);
        scanf("%d",&position_x2);
        scanf("%d",&position_y2);
        scanf("%d",&position_x3);
        scanf("%d",&position_y3);
    
        if((position_x1>=0 && position_x1<8)&&(position_y1>=0 && position_y1<8)&&(position_x2>=0 && position_x2<8)&&(position_y2>=0 && position_y1<8)&&(position_x3>=0 && position_x3<8) && (position_y3>=0 && position_y3<8))//Makes sure the user doesn't enter a coordinate point that isnt 0-7 i.e a character like a etc
        {
            if(position_x1==position_x2 && position_y1==position_y2)//This makes sure queen 1 and 2 don't overlap
            {
                printf("Some queens overlap\n");
                return 0;
            }
            
            else if(position_x1==position_x3 && position_y1==position_y3)//This makes sure queen 1 and 3 don't overlap
            {
                printf("Some queens overlap\n");
                return 0;
            }
            
            else if(position_x2==position_x3 && position_y2==position_y3)//This makes sure queen 2 and 3 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            else
            {
                check_violation();
                compute_positon_of_remaining_queens();
            }
            
        }
        
        else//If user enters a coordinate that is is illegal like a or b
        {
            printf("You did not enter a valid coordinate point(s) for the queen(s)\n");
            return 0;
        }
    }
    
    else if(m==4)
    {
        scanf("%d",&position_x1); ////Stores x&y coordinates(location on chessboard) of queen 1,2,3,4
        scanf("%d",&position_y1);
        scanf("%d",&position_x2);
        scanf("%d",&position_y2);
        scanf("%d",&position_x3);
        scanf("%d",&position_y3);
        scanf("%d",&position_x4);
        scanf("%d",&position_y4);
    
        if((position_x1>=0 && position_x1<8)&&(position_y1>=0 && position_y1<8)&&(position_x2>=0 && position_x2<8)&&(position_y2>=0 && position_y1<8)&&(position_x3>=0 && position_x3<8) && (position_y3>=0 && position_y3<8) && (position_y4>=0 && position_y4<8) && (position_x4>=0 && position_x4<8))//Makes sure the user doesn't enter a coordinate point that isnt 0-7 i.e a character like a etc
        {
            if(position_x1==position_x2 && position_y1==position_y2)//This makes sure queen 1 and 2 don't overlap
            {
                printf("Some queens overlap\n");
                return 0;
            }
            
            else if(position_x1==position_x3 && position_y1==position_y3)//This makes sure queen 1 and 3 don't overlap
            {
                printf("Some queens overlap\n");
                return 0;
            }
            
            else if(position_x2==position_x3 && position_y2==position_y3)//This makes sure queen 2 and 3 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x1==position_x4 && position_y1==position_y4)//This makes sure queen 1 and 4 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x2==position_x4 && position_y2==position_y4)//This makes sure queen 2 and 4 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x3==position_x4 && position_y3==position_y4)//This makes sure queen 3 and 4 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            else//If no queens overlap and coordinates are legal
            {
                check_violation();
                compute_positon_of_remaining_queens();
            }
                
        }
        
        else//If user inputs illegal coordinates
        {
            printf("You did not enter a valid coordinate point(s) for the queen(s)\n");
            return 0;
        }
    }
    
    else if(m==5)
    {
        scanf("%d",&position_x1);     ////Stores x&y coordinates(location on chessboard) of queen 1,2,3,4,5
        scanf("%d",&position_y1);
        scanf("%d",&position_x2);
        scanf("%d",&position_y2);
        scanf("%d",&position_x3);
        scanf("%d",&position_y3);
        scanf("%d",&position_x4);
        scanf("%d",&position_y4);
        scanf("%d",&position_x5);
        scanf("%d",&position_y5);
    
        
        if((position_x1>=0 && position_x1<8)&&(position_y1>=0 && position_y1<8)&&(position_x2>=0 && position_x2<8)&&(position_y2>=0 && position_y1<8)&&(position_x3>=0 && position_x3<8) && (position_y3>=0 && position_y3<8) && (position_y4>=0 && position_y4<8) && (position_x4>=0 && position_x4<8)&&(position_x5>=0 && position_x5<8)&&(position_y5>=0&&position_y5<8))//Makes sure the user doesn't enter a coordinate point that isnt 0-7 i.e a character like a etc
        {
            if(position_x1==position_x2 && position_y1==position_y2)//Makes sure queen 1 and 2 don't overlap
            {
                printf("Some queens overlap\n");
                return 0;
            }
            
            else if(position_x1==position_x3 && position_y1==position_y3)//Makes sure queen 1 and 3 don't overlap
            {
                printf("Some queens overlap\n");
                return 0;
            }
            
            else if(position_x1==position_x4 && position_y1==position_y4)//Makes sure queen 1 and 4 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x1==position_x5 && position_y1==position_y5)//Makes sure queen 1 and 5 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x2==position_x3 && position_y2==position_y3)//Makes sure queen 2 and 3 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x2==position_x4 && position_y2==position_y4)//Makes sure queen 2 and 4 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x2==position_x5 && position_y2==position_y5)//Makes sure queen 2 and 5 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x3==position_x4 && position_y3==position_y4)//Makes sure queen 3 and 4 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x3==position_x5 && position_y3==position_y5)//Makes sure queen 3 and 5 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x4==position_x5 && position_y4==position_y5)//Makes sure queen 4 and 5 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else//If no queen's overlap and coordinates are legal
            {
                check_violation();
                compute_positon_of_remaining_queens();
            }
        }
        
        else//If user inputs illegal coordinates
        {
            printf("You did not enter a valid coordinate point(s) for the queen(s)\n");
            return 0;
        }
    }

    else if(m==6)
    {
        scanf("%d",&position_x1);       //Stores x&y coordinates(location on chessboard) of queen 1,2,4,5,6
        scanf("%d",&position_y1);
        scanf("%d",&position_x2);
        scanf("%d",&position_y2);
        scanf("%d",&position_x3);
        scanf("%d",&position_y3);
        scanf("%d",&position_x4);
        scanf("%d",&position_y4);
        scanf("%d",&position_x5);
        scanf("%d",&position_y5);
        scanf("%d",&position_x6);
        scanf("%d",&position_y6);
    
        if((position_x1>=0 && position_x1<8)&&(position_y1>=0 && position_y1<8)&&(position_x2>=0 && position_x2<8)&&(position_y2>=0 && position_y1<8)&&(position_x3>=0 && position_x3<8) && (position_y3>=0 && position_y3<8) && (position_y4>=0 && position_y4<8) && (position_x4>=0 && position_x4<8)&&(position_x5>=0 && position_x5<8)&&(position_y5>=0&&position_y5<8)&&(position_x6>=0 && position_x6<8)&&(position_y6>=0 &&position_y6<8))
        {
            if(position_x1==position_x2 && position_y1==position_y2)//Makes sure queen 1 and 2 don't overlap
            {
                printf("Some queens overlap\n");
                return 0;
            }
            
            else if(position_x1==position_x3 && position_y1==position_y3)//Makes sure queen 2 and 3 don't overlap
            {
                printf("Some queens overlap\n");
                return 0;
            }
            
            else if(position_x1==position_x4 && position_y1==position_y4)//Makes sure queen 1 and 4 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x1==position_x5 && position_y1==position_y5)//Makes sure queen 1 and 5 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x1==position_x6 && position_y1==position_y6)//Makes sure queen 1 and 6 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x2==position_x3 && position_y2==position_y3)//Makes sure queen 2 and 3 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x2==position_x4 && position_y2==position_y4)//Makes sure queen 2 and 4 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x2==position_x5 && position_y2==position_y5)//Makes sure queen 2 and 5 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x2==position_x6 && position_y2==position_y6)//Makes sure queen 2 and 6 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x3==position_x4 && position_y3==position_y4)//Makes sure queen 3 and 4 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x3==position_x5 && position_y3==position_y5)//Makes sure queen 3 and 5 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x3==position_x6 && position_y3==position_y6)//Makes sure queen 3 and 6 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x4==position_x5 && position_y4==position_y5)//Makes sure queen 4 and 5 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x4==position_x6 && position_y4==position_y6)//Makes sure queen 4 and 6 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x5==position_x6 && position_y5==position_y6)//Makes sure queen 5 and 6 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            else//If no queen's overlap and coordinates are legal
            {
                check_violation();
                compute_positon_of_remaining_queens();
            }
        }
        
        else//If user inputs illegal coordinates
        {
            printf("You did not enter a valid coordinate point(s) for the queen(s)\n");
            return 0;
        }
        
    }
    
    else if(m==7)
    {
        scanf("%d",&position_x1);      //Stores x&y coordinates(location on chessboard) of queen 1,2,3,4,5,6,7
        scanf("%d",&position_y1);
        scanf("%d",&position_x2);
        scanf("%d",&position_y2);
        scanf("%d",&position_x3);
        scanf("%d",&position_y3);
        scanf("%d",&position_x4);
        scanf("%d",&position_y4);
        scanf("%d",&position_x5);
        scanf("%d",&position_y5);
        scanf("%d",&position_x6);
        scanf("%d",&position_y6);
        scanf("%d",&position_x7);
        scanf("%d",&position_y7);
        
        if((position_x1>=0 && position_x1<8)&&(position_y1>=0 && position_y1<8)&&(position_x2>=0 && position_x2<8)&&(position_y2>=0 && position_y1<8)&&(position_x3>=0 && position_x3<8) && (position_y3>=0 && position_y3<8) && (position_y4>=0 && position_y4<8) && (position_x4>=0 && position_x4<8)&&(position_x5>=0 && position_x5<8)&&(position_y5>=0&&position_y5<8)&&(position_x6>=0 && position_x6<8)&&(position_y6>=0 &&position_y6<8)&&(position_x7>=0 && position_x7<8) &&(position_y7<=0 && position_y7>8))
        {
            if(position_x1==position_x2 && position_y1==position_y2)//Makes sure queen 1 and 2 don't overlap
            {
                printf("Some queens overlap\n");
                return 0;
            }
            
            else if(position_x1==position_x3 && position_y1==position_y3)//Makes sure queen 1 and 3 don't overlap
            {
                printf("Some queens overlap\n");
                return 0;
            }
            
            else if(position_x1==position_x4 && position_y1==position_y4)//Makes sure queen 1 and 4 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x1==position_x5 && position_y1==position_y5)//Makes sure queen 1 and 5 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x1==position_x6 && position_y1==position_y6)//Makes sure queen 1 and 6 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x1==position_x7 && position_y1==position_y7)//Makes sure queen 1 and 7 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x2==position_x3 && position_y2==position_y3)//Makes sure queen 2 and 3 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x2==position_x4 && position_y2==position_y4)//Makes sure queen 2 and 4 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x2==position_x5 && position_y2==position_y5)//Makes sure queen 2 and 5 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x2==position_x6 && position_y1==position_y6)//Makes sure queen 2 and 6 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x2==position_x7 && position_y2==position_y7)//Makes sure queen 2 and 7 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x3==position_x4 && position_y3==position_y4)//Makes sure queen 3 and 4 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x3==position_x5 && position_y3==position_y5)//Makes sure queen 3 and 5 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x3==position_x6 && position_y3==position_y6)//Makes sure queen 3 and 6 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x3==position_x7 && position_y3==position_y7)//Makes sure queen 3 and 7 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x4==position_x5 && position_y4==position_y5)//Makes sure queen 4 and 5 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x4==position_x6 && position_y4==position_y6)//Makes sure queen 4 and 6 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x4==position_x7 && position_y4==position_y7)//Makes sure queen 4 and 7 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x5==position_x6 && position_y5==position_y6)//Makes sure queen 5 and 6 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x5==position_x7 && position_y5==position_y7)//Makes sure queen 5 and 7 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x6==position_x7 && position_y6==position_y7)//Makes sure queen 6 and 7 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            else//If no queen's overlap and coordinates are legal
            {
                check_violation();
                compute_positon_of_remaining_queens();
            }
        }
        
        else//If user inputs illegal coordinates
        {
            printf("You did not enter a valid coordinate point(s) for the queen(s)\n");
            return 0;
        }
    }

    else if (m==8)
    {
        scanf("%d",&position_x1);     //Stores x&y coordinates(location on chessboard) of queen 1,2,3,4,5,6,7,8
        scanf("%d",&position_y1);
        scanf("%d",&position_x2);
        scanf("%d",&position_y2);
        scanf("%d",&position_x3);
        scanf("%d",&position_y3);
        scanf("%d",&position_x4);
        scanf("%d",&position_y4);
        scanf("%d",&position_x5);
        scanf("%d",&position_y5);
        scanf("%d",&position_x6);
        scanf("%d",&position_y6);
        scanf("%d",&position_x7);
        scanf("%d",&position_y7);
        scanf("%d",&position_x8);
        scanf("%d",&position_y8);
        
        if((position_x1>=0 && position_x1<8)&&(position_y1>=0 && position_y1<8)&&(position_x2>=0 && position_x2<8)&&(position_y2>=0 && position_y1<8)&&(position_x3>=0 && position_x3<8) && (position_y3>=0 && position_y3<8) && (position_y4>=0 && position_y4<8) && (position_x4>=0 && position_x4<8)&&(position_x5>=0 && position_x5<8)&&(position_y5>=0&&position_y5<8)&&(position_x6>=0 && position_x6<8)&&(position_y6>=0 &&position_y6<8)&&(position_x7>=0 && position_x7<8) &&(position_y7<=0 && position_y7>8)&&(position_x8>=0 && position_x8<8)&&(position_y8<=0&&position_y8<8))
        {
            if(position_x1==position_x2 && position_y1==position_y2)//Makes sure queen 1 and 2 don't overlap
            {
                printf("Some queens overlap\n");
                return 0;
            }
            
            else if(position_x1==position_x3 && position_y1==position_y3)//Makes sure queen 1 and 3 don't overlap
            {
                printf("Some queens overlap\n");
                return 0;
            }
            
            else if(position_x1==position_x4 && position_y1==position_y4)//Makes sure queen 1 and 4 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x1==position_x5 && position_y1==position_y5)//Makes sure queen 1 and 5 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x1==position_x6 && position_y1==position_y6)//Makes sure queen 1 and 6 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x1==position_x7 && position_y1==position_y7)//Makes sure queen 1 and 7 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x1==position_x8 && position_y1==position_y8)//Makes sure queen 1 and 8 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x2==position_x3 && position_y2==position_y3)//Makes sure queen 2 and 3 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x2==position_x4 && position_y2==position_y4)//Makes sure queen 2 and 4 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x2==position_x5 && position_y2==position_y5)//Makes sure queen 2 and 5 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x2==position_x6 && position_y1==position_y6)//Makes sure queen 2 and 6 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x2==position_x7 && position_y2==position_y7)//Makes sure queen 2 and 7 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x2==position_x8 && position_y2==position_y8)//Makes sure queen 2 and 8 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x3==position_x4 && position_y3==position_y4)//Makes sure queen 3 and 4 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x3==position_x5 && position_y3==position_y5)//Makes sure queen 3 and 5 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x3==position_x6 && position_y3==position_y6)//Makes sure queen 3 and 6 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x3==position_x7 && position_y3==position_y7)//Makes sure queen 3 and 7 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x3==position_x8 && position_y3==position_y8)//Makes sure queen 3 and 8 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x4==position_x5 && position_y4==position_y5)//Makes sure queen 4 and 5 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x4==position_x6 && position_y4==position_y6)//Makes sure queen 4 and 6 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x4==position_x7 && position_y4==position_y7)//Makes sure queen 4 and 7 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x4==position_x8 && position_y4==position_y8)//Makes sure queen 4 and 8 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x5==position_x6 && position_y5==position_y6)//Makes sure queen 5 and 6 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x5==position_x7 && position_y5==position_y7)//Makes sure queen 5 and 7 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x5==position_x8 && position_y5==position_y8)//Makes sure queen 5 and 8 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x6==position_x7 && position_y6==position_y7)//Makes sure queen 6 and 7 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x6==position_x8 && position_y6==position_y8)//Makes sure queen 6 and 8 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            
            else if(position_x7==position_x8 && position_y7==position_y8)//Makes sure queen 7 and 8 don't overlap
            {
                printf("some queens overlap\n");
                return 0;
            }
            else//If no queen's overlap and coordinates are legal
            {
                check_violation();
                compute_positon_of_remaining_queens();
            }
        }
        
        else
        {
            printf("You did not enter a valid coordinate point(s) for the queen(s)\n");
            return 0;
        }
    }
    
    else
    {
        printf("\nInput is illegal\n");
        return 0;
    }
}

int check_violation()//-Haven't completed yet
{
  
    
    
    printf("Struggling here");
    
    
    return 0;
}

int compute_positon_of_remaining_queens()//-Haven't completed yet
{
    printf("Does nothing atm");
    return 0;
} 


Is This A Good Question/Topic? 0
  • +

Replies To: 8 queen problem with a twist

#2 Salem_c  Icon User is offline

  • void main'ers are DOOMED
  • member icon

Reputation: 1780
  • View blog
  • Posts: 3,439
  • Joined: 30-May 10

Re: 8 queen problem with a twist

Posted 30 July 2014 - 10:12 PM

> 799 int check_violation()//-Haven't completed yet
No, the first problem you have to deal with is those global variables, and the fact that your main is 800 lines long!

> 033 int position_x1;//Position of queen 1 in x coordinate
> 034 int position_y1;//Position of queen 1 in y coordiante
> 035 int position_x2;//Position of queen 2 in x coordinate
> 036 int position_y2;//Position of queen 2 in y coordinate
When you start putting numbers on the ends of variables, it should be screaming at you to use an array!

printf("How many");
scanf("%d",&m);
for ( i = 0 ; i < m ; i++ ) {
  printf("Enter pos");
  scanf("%d %d",&posx[i],&posy[i]);
  checkValid(posx,posy,i+1); // check the first n positions  
}


Done properly, this should get rid of 100's of lines of your copy/paste.
Was This Post Helpful? 0
  • +
  • -

#3 Darraptor  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 63
  • Joined: 11-May 14

Re: 8 queen problem with a twist

Posted 31 July 2014 - 11:38 AM

View PostSalem_c, on 30 July 2014 - 10:12 PM, said:

> 799 int check_violation()//-Haven't completed yet
No, the first problem you have to deal with is those global variables, and the fact that your main is 800 lines long!

> 033 int position_x1;//Position of queen 1 in x coordinate
> 034 int position_y1;//Position of queen 1 in y coordiante
> 035 int position_x2;//Position of queen 2 in x coordinate
> 036 int position_y2;//Position of queen 2 in y coordinate
When you start putting numbers on the ends of variables, it should be screaming at you to use an array!

printf("How many");
scanf("%d",&m);
for ( i = 0 ; i < m ; i++ ) {
  printf("Enter pos");
  scanf("%d %d",&posx[i],&posy[i]);
  checkValid(posx,posy,i+1); // check the first n positions  
}


Done properly, this should get rid of 100's of lines of your copy/paste.


Just a few questions I have:

1. Why is i+1 in the parameter(I dont see how it will help?
2. If m==1 then would any spot be legal for the queen to be placed in?
3.I;m having trouble coming up with an algorithm that checks the pieces diagonally but I have something in mind that checks the pieces if they are horizontal or vertical. I was thinking along the lines of comparing the x and y positions of the m queens. So my pusedocode that I have thought of so far is if(posx of 1st queen==posx of 2nd queen || posy of 1st queen is equal posy to 2nd queen)
then invalid placing because the queens would attack each other. I mean the psudeocode works for when there's two queens but what if there's like 7 queens then it gets a bit complicated.
Was This Post Helpful? 0
  • +
  • -

#4 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3667
  • View blog
  • Posts: 11,499
  • Joined: 05-May 12

Re: 8 queen problem with a twist

Posted 31 July 2014 - 11:49 AM

View PostDarraptor, on 31 July 2014 - 02:38 PM, said:

1. Why is i+1 in the parameter(I dont see how it will help?


He is following the convention that when you call a function that takes an array (or a set of parallel arrays), that you pass in the number of items in the array. In this case, you have an item at index i, so therefore, you must have i + 1 elements in the array.

View PostDarraptor, on 31 July 2014 - 02:38 PM, said:

2. If m==1 then would any spot be legal for the queen to be placed in?

Yes. There should be nothing for it to collide against.

View PostDarraptor, on 31 July 2014 - 02:38 PM, said:

3.I;m having trouble coming up with an algorithm that checks the pieces diagonally...

When you are checking for horizontal, you just need to check for other queens with the same row number.
When you are checking for vertical, you just need to check for other queens with the same column number.
When you are checking for diagonals, you just need to walk the two diagonal lines emanating from the queen and check for queens.
Was This Post Helpful? 0
  • +
  • -

#5 Darraptor  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 63
  • Joined: 11-May 14

Re: 8 queen problem with a twist

Posted 31 July 2014 - 12:02 PM

View PostSkydiver, on 31 July 2014 - 11:49 AM, said:

View PostDarraptor, on 31 July 2014 - 02:38 PM, said:

1. Why is i+1 in the parameter(I dont see how it will help?


He is following the convention that when you call a function that takes an array (or a set of parallel arrays), that you pass in the number of items in the array. In this case, you have an item at index i, so therefore, you must have i + 1 elements in the array.

View PostDarraptor, on 31 July 2014 - 02:38 PM, said:

2. If m==1 then would any spot be legal for the queen to be placed in?

Yes. There should be nothing for it to collide against.

View PostDarraptor, on 31 July 2014 - 02:38 PM, said:

3.I;m having trouble coming up with an algorithm that checks the pieces diagonally...

When you are checking for horizontal, you just need to check for other queens with the same row number.
When you are checking for vertical, you just need to check for other queens with the same column number.
When you are checking for diagonals, you just need to walk the two diagonal lines emanating from the queen and check for queens.


When I use i+1 I get an error. I declared int Check_if_valid(int m,int posx,int posy,int i+1); and its saying expected ')' Even when I put paratheses around i+1 I still get the same error. Also I'm a little confused on how to walk the two diagonal lines emanating from the queen and check for queens.
Was This Post Helpful? 0
  • +
  • -

#6 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3667
  • View blog
  • Posts: 11,499
  • Joined: 05-May 12

Re: 8 queen problem with a twist

Posted 31 July 2014 - 12:24 PM

View PostDarraptor, on 31 July 2014 - 03:02 PM, said:

When I use i+1 I get an error. I declared int Check_if_valid(int m,int posx,int posy,int i+1); and its saying expected ')' Even when I put paratheses around i+1 I still get the same error. Also I'm a little confused on how to walk the two diagonal lines emanating from the queen and check for queens.


There is a difference between declaring and calling a function. Note that in my reply I said call.

View PostSkydiver, on 31 July 2014 - 11:49 AM, said:

He is following the convention that when you call a function that takes an array (or a set of parallel arrays), that you pass in the number of items in the array. ...

Was This Post Helpful? 0
  • +
  • -

#7 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1432
  • View blog
  • Posts: 4,968
  • Joined: 19-February 09

Re: 8 queen problem with a twist

Posted 31 July 2014 - 12:27 PM

Hi, I take it you have added the position variables. Do you need them all? When you read a queen's position, a symbol/value is placed in the array to represent a queen's position.
Was This Post Helpful? 0
  • +
  • -

#8 Darraptor  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 63
  • Joined: 11-May 14

Re: 8 queen problem with a twist

Posted 31 July 2014 - 12:33 PM

View PostSkydiver, on 31 July 2014 - 12:24 PM, said:

View PostDarraptor, on 31 July 2014 - 03:02 PM, said:

When I use i+1 I get an error. I declared int Check_if_valid(int m,int posx,int posy,int i+1); and its saying expected ')' Even when I put paratheses around i+1 I still get the same error. Also I'm a little confused on how to walk the two diagonal lines emanating from the queen and check for queens.


There is a difference between declaring and calling a function. Note that in my reply I said call.

View PostSkydiver, on 31 July 2014 - 11:49 AM, said:

He is following the convention that when you call a function that takes an array (or a set of parallel arrays), that you pass in the number of items in the array. ...


so when I declare I just put i in the parameter?
Was This Post Helpful? 0
  • +
  • -

#9 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3667
  • View blog
  • Posts: 11,499
  • Joined: 05-May 12

Re: 8 queen problem with a twist

Posted 31 July 2014 - 01:00 PM

Actually, you should name your parameters more descriptively. For example consider this function prototype:
bool FindValueInArray(int value, int arr[], size_t arraySize);


It makes it pretty obvious which parameters are which.

(As an aside: The size_t could have just been an int for simplicity, but for correctness size_t should be use.)
Was This Post Helpful? 0
  • +
  • -

#10 Darraptor  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 63
  • Joined: 11-May 14

Re: 8 queen problem with a twist

Posted 01 August 2014 - 03:27 PM

**UPDATE So I managed to figure almost everything except for the algorithm that helps me place the remaining queens once you give an initial position to the m queens but I'm really having a tough time figuring this out. If I didn't have to give a certain amount of queens initial positions then i wouldnt be having this trouble. Anyways the only thing I;ve noticed is that for the 8 queen problem to work is that none of the queens can share a row or column otherwise it would violate the rule. With that being said I still can't come up with an algorithm so could someone point me in the right direction pleassee??
Was This Post Helpful? 0
  • +
  • -

#11 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3667
  • View blog
  • Posts: 11,499
  • Joined: 05-May 12

Re: 8 queen problem with a twist

Posted 02 August 2014 - 06:25 AM

If you are not being graded on algorithm design and efficiency, you could go for the brute force algorithm. In pseudo code:
for each row
    for each column
        if row,col is occupied
            continue
        place queen at row,col
        check if valid
        if invalid
            undo placing queen at row, col


Was This Post Helpful? 0
  • +
  • -

#12 Darraptor  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 63
  • Joined: 11-May 14

Re: 8 queen problem with a twist

Posted 03 August 2014 - 10:56 AM

View PostSkydiver, on 02 August 2014 - 06:25 AM, said:

If you are not being graded on algorithm design and efficiency, you could go for the brute force algorithm. In pseudo code:
for each row
    for each column
        if row,col is occupied
            continue
        place queen at row,col
        check if valid
        if invalid
            undo placing queen at row, col



Efficiency does matter but this is what I have so far. I already initialized both int posx[8] and int posy[8] with 9's. If you could help me out that would be great.

int Compute_positon_of_remaining_queens(int m,int posx,int posy)//Calculates where the remaining queen goes on the board
{
    //I'm having difficulty coming up with the algorithm that will put the remaining m queens on the board
    
    int i,j,count2,checkifsolutionexist=0;
    count2++;
    
    printf("Solution #%d:\n\n",count2);
    for(i=0;i<8;i++)
    {
        for(j=0;j<8;j++)
        {
            if(posx[i]==9 && posy[j]==9)//I'm trying to get this part to say if there's no queen assigned to this spot
            {
                
               if(posx[i]==posx[j]||posy[i]==posy[j])//If the spot is where another queen can attack it then print 0-doesnt work on diagonals yet which i dont know how to make it work on diagonal
                   printf("0\t");
                else
                {
                    printf("Q\t");//Otherwise if the second if statement is false then printf Q
                    ++checkifsolutionexist;
                }
            }
            
            else if(posx[i]!=9 && posy[i]!=9)//If there's a queen occupying the spot then print the queen
                printf("Q\t");
        }
        printf("\n\n");
    }
    
    if(checkifsolutionexist!=(8-m))//For instance lets say if we had 7 queens placed on the board and we needed to place one more queen. If there was no way to do so then the statement would read 0!=(8-1) which is equivalent to 0!=1 and if thats the case it means there's no solution where it satisfy the 8 queen rule
        printf("No solution possible\n");

    return 0;
    
                                        //PSUDEOCODE
    
                        //If the spot on the board equals zero(no queen is there) then
                        //If the spot is where another queen can attack it then print 0
                        //Otherwise if the second if statement is false then printf Q
    
                        //If the spot on the board is not zero(in other words if there's a queen occupying the spot then
                        //Place a queen there
}


This post has been edited by Darraptor: 03 August 2014 - 10:57 AM

Was This Post Helpful? 0
  • +
  • -

#13 Salem_c  Icon User is offline

  • void main'ers are DOOMED
  • member icon

Reputation: 1780
  • View blog
  • Posts: 3,439
  • Joined: 30-May 10

Re: 8 queen problem with a twist

Posted 03 August 2014 - 11:45 AM

8 queens is a relatively well studied problem, there's plenty of information on the web for you to read.

Seriously, if the imaginary function
solve(board,8);
recurses at most 8 times to place 8 queens on a empty board, then there really is no difference for you to specify the initial positions of say 3 pieces and then call
solve(board,5);

The algorithm doesn't change because you gave some initial state. It just gives it less work to do.

It could be however, that your initial 3 positions result in there being no solution at all.
Was This Post Helpful? 0
  • +
  • -

#14 Darraptor  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 63
  • Joined: 11-May 14

Re: 8 queen problem with a twist

Posted 03 August 2014 - 02:24 PM

View PostSalem_c, on 03 August 2014 - 11:45 AM, said:

8 queens is a relatively well studied problem, there's plenty of information on the web for you to read.

Seriously, if the imaginary function
solve(board,8);
recurses at most 8 times to place 8 queens on a empty board, then there really is no difference for you to specify the initial positions of say 3 pieces and then call
solve(board,5);

The algorithm doesn't change because you gave some initial state. It just gives it less work to do.

It could be however, that your initial 3 positions result in there being no solution at all.


Can you explain a bit more on why it gives less work to do? I would think its harder
Was This Post Helpful? 0
  • +
  • -

#15 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1432
  • View blog
  • Posts: 4,968
  • Joined: 19-February 09

Re: 8 queen problem with a twist

Posted 03 August 2014 - 02:51 PM

Hi, if you are placing a queen on the board, why can you not check the position on the board for a queen?
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2