Thread: 8 Queens, problem with searching 2D array

  1. #1
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719

    8 Queens, problem with searching 2D array

    Hello, I'm trying to solve the 8 queens problem, but I need some help searching the 2D array. I understand how the algorithm works, but the problem I always have is applying that algorithm to code. I've posted what I have so far. I have to do it this way, so don't tell me to combine functions or anything like that. Searching arrays like this really confuses me for some reason, so any help is great. Thanks!

    Code:
    #include <iostream>
    
    using namespace std;
    
    int board[8][8];
    
    void resetBoard();
    void displayBoard();
    void addQueen(int row, int column);
    void removeQueen(int row,int column);
    void solve(int n, int column, int row);
    
    bool isPathViable(int row, int column);
    bool isPathSuccess();
    
    int main()
    {
    	resetBoard();
    	
    	for(int i=1; i <= 8; ++i)
    		//solve(...);
    	
    	return 0;
    }
    
    void resetBoard()
    {
    	for(int i=0; i < 8; ++i)
    		for(int j=0; j < 8; ++j)
    			board[i][j]=0;
    }
    
    void displayBoard()
    {
    	for(int i=0; i < 8; ++i)
    	{
    		for(int j=0; j < 8; ++j)
    			cout << board[i][j] << " ";
    		
    		cout << "\n";
    	}
    }
    
    void addQueen(int row,int column)
    {
    	board[row][column]=1;
    }
    
    void removeQueen(int row,int column)
    {
    	board[row][column]=0;
    }
    
    void solve(int n,int row, int column)
    {
    	addQueen(row,column);
    
    	if(isPathSuccess())
    		displayBoard();
    
    	else if(isPathViable(row,column))
    		for(int i=1; i <= n; ++i)
    			solve(n,i,column+1);
    
    
    
    }
    
    
    bool isPathViable(int row, int column)
    {
    	for(int i=0; i < column; ++i)
    		if(board[row][i]==1)
    			return false;
    
    	//Really confused on how to search this and check if a queen is safe
    
    		else
    			return true;
    }
    
    bool isPathSuccess()
    {
    	int queens=0;
    
    	for(int i=0; i < 8;i++)
    		for(int j=0;j < 8;j++)
    			if(board[i][j]=1)
    				++queens;
    
    	if(queens==8)
    		return true;
    
    	else
    		return false;
    }
    Videogame Memories!
    A site dedicated to keeping videogame memories alive!

    http://www.videogamememories.com/
    Share your experiences with us now!

    "We will game forever!"

  2. #2
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719
    Can anyone help with this?
    Videogame Memories!
    A site dedicated to keeping videogame memories alive!

    http://www.videogamememories.com/
    Share your experiences with us now!

    "We will game forever!"

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by Sentral View Post
    Can anyone help with this?
    Help with what?

  4. #4
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719
    Quote Originally Posted by tabstop View Post
    Help with what?
    I've explained it. I don't know how to check if a queen is safe or not. How do I go about searching the board to find if a queen is in danger?
    Videogame Memories!
    A site dedicated to keeping videogame memories alive!

    http://www.videogamememories.com/
    Share your experiences with us now!

    "We will game forever!"

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    The queen is safe if there is no other queen in the same row, column, or diagonal. Looping over a row or column should be trivial. As far as diagonals go, if you want to save thinking, you can just search in each of the four diagonal directions NE, NW, SE, and SW looking for queens. So ask yourself: if you are at, say, [3][4] and want to move one square to the northeast, where you will be? What about two squares? Can you see a pattern?

  6. #6
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719
    Ok here is what I got to check if a path is viable, but I have a problem. I search through using for loops, and check if the element is equal to 1. If it is I return false because that path is not safe. However, this doesn't seem to work. The function returns numbers such as 253, or 252 which doesn't make sense. Anyone know why?

    Code:
    bool isPathViable(int row, int column)
    {
    	for(int i=0;i <= row; i++)	//Checks row
    		if(board[row][i]==1)
    			return false;
    
    	for(;row => 0,column => 0;--row,--column)	//Checks left and up diagonal 
    		if(board[row][column]==1)
    				return false;
    
    	for(;row => 0,column => 0;++row,--column)	//Checks left and down diagonal 
    		if(board[row][column]==1)
    				return false;
    
    	
    }
    Videogame Memories!
    A site dedicated to keeping videogame memories alive!

    http://www.videogamememories.com/
    Share your experiences with us now!

    "We will game forever!"

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Did you see that warning that says something like "not all paths return a value"? Did you notice how you don't ever bother to return true if the path is viable? Did you ever wonder what happened when you forgot to return a value and then tried to use it?

  8. #8
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719
    Thank you, I believe I got it now.

    Code:
    bool isPathViable(int row, int column)
    {
    	bool success;
    	
    	for( ;column >= 0; --column)	//Checks row
    	{
    		if(board[row][column]==1)
    			success=false;
    	
    		else if(board[row][column]==0)
    			success=true;
    	}
    	
    	for( ; row >= 0, column >= 0;--row, --column)	//Checks left and up diagonal
    	{
    		if(board[row][column]==1)
    			success=false;
    
    		
    		else if(board[row][column]==0)
    			success=true;
    	}
    	
    	for( ;row >= 0,column >= 0;++row,--column)	//Checks left and down diagonal 
    	{
    		if(board[row][column]==1)
    			success=false;
    
    		
    		else if(board[row][column]==0)
    			success=true;
    	}
    
    	return success;
    		
    }
    Last edited by Sentral; 03-10-2009 at 01:24 PM.
    Videogame Memories!
    A site dedicated to keeping videogame memories alive!

    http://www.videogamememories.com/
    Share your experiences with us now!

    "We will game forever!"

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    You still have two diagonals left to check, I think -- not to mention the fact that the third for-loop checks the diagonal, not of the square you want to look at, but of the square you finished the previous for loop at.

    And notice that if you find an enemy, success must remain false no matter what else happens -- no setting it back to true!

  10. #10
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719
    You still have two diagonals left to check, I think
    I think I did that in the last two for loops. The first checks North West direction, and the second checks South West.

    not to mention the fact that the third for-loop checks the diagonal, not of the square you want to look at, but of the square you finished the previous for loop at.
    What do you mean by this?

    And notice that if you find an enemy, success must remain false no matter what else happens -- no setting it back to true!
    So you're saying don't use a bool variable? Just return true or false? I've tried that but it didn't work because the first return it comes in contact with terminates the function. How can I get around this?


    Oh, and if I'm in first column and check if it's viable it returns false. How can this be?
    Last edited by Sentral; 03-10-2009 at 01:55 PM.
    Videogame Memories!
    A site dedicated to keeping videogame memories alive!

    http://www.videogamememories.com/
    Share your experiences with us now!

    "We will game forever!"

  11. #11
    Registered User
    Join Date
    Aug 2008
    Posts
    33
    Quote Originally Posted by Sentral View Post
    What do you mean by this?
    And notice that if you find an enemy, success must remain false no matter what else happens -- no setting it back to true![/
    Maybe because you function is searching for avaliablity. So if you search one path and recieve a false,
    you then re-use your boolean variable for the next loop. Possibly re-initalising it to true..?
    Last edited by Else; 03-10-2009 at 02:07 PM.

  12. #12
    Registered User
    Join Date
    Aug 2008
    Posts
    33
    return an INT sybolising which direction you have been compromised in...?

  13. #13
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719
    Quote Originally Posted by Else View Post
    Maybe because you function is searching for avaliablity. So if you search one path and recieve a false,
    you then re-use your boolean variable for the next loop. Possibly re-initalising it to true..?
    Why would I reuse it? If it's false that means there is a queen that is threatening, so why would I go on to check other directions?
    Videogame Memories!
    A site dedicated to keeping videogame memories alive!

    http://www.videogamememories.com/
    Share your experiences with us now!

    "We will game forever!"

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by Sentral View Post
    Why would I reuse it? If it's false that means there is a queen that is threatening, so why would I go on to check other directions?
    I don't know why you would want to. You do anyway, but I don't know why you would want to, and yes your variable does then get reset to true. The instant you get false, you want to return, because (a) checking more won't help so why bother and (b) this way you don't inadvertently destroy your result. Your first try was perfect in that regard, if only you hadn't forgotten to type "return true;" at the end of it.

    Your row and column variables are changed by the second for-loop, until they walk off the board. So at the start of the third for-loop, that's where you start moving southwest, from that ending square.

    You've got left+up and left+down, which means you have completely ignored right+down and right+up. You shouldn't.

  15. #15
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719
    I don't know why you would want to. You do anyway, but I don't know why you would want to, and yes your variable does then get reset to true. The instant you get false, you want to return, because (a) checking more won't help so why bother and (b) this way you don't inadvertently destroy your result. Your first try was perfect in that regard, if only you hadn't forgotten to type "return true;" at the end of it.
    Ok, so you are saying get rid of the "else's" and just return true at the end of the funtion, but still keep the "return false" in the if's?

    Your row and column variables are changed by the second for-loop, until they walk off the board. So at the start of the third for-loop, that's where you start moving southwest, from that ending square.
    Oh wow I didn't even notice that! So I would have to initialize the for-loop with some variable and then assign my row and column into those it won't modify them?

    You've got left+up and left+down, which means you have completely ignored right+down and right+up. You shouldn't.
    I believe this algorithm doesn't require that. You only have to check to the left because the placing of the queens goes from left to right. However, judging by my progress with this I could be wrong


    EDIT- Hmmmmm... I still get falses returned even if the queen is in a safe spot. This is frustrating!
    Last edited by Sentral; 03-10-2009 at 03:19 PM.
    Videogame Memories!
    A site dedicated to keeping videogame memories alive!

    http://www.videogamememories.com/
    Share your experiences with us now!

    "We will game forever!"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Allocating a 2D Array Differently
    By pianorain in forum C++ Programming
    Replies: 13
    Last Post: 12-15-2005, 02:01 AM
  2. Read file in 2D array
    By Chook in forum C Programming
    Replies: 1
    Last Post: 05-08-2005, 12:39 PM
  3. 2d array problem with vc++
    By LiLgirL in forum C++ Programming
    Replies: 10
    Last Post: 03-16-2004, 08:17 PM
  4. 2d array problem
    By LiLgirL in forum Windows Programming
    Replies: 1
    Last Post: 03-15-2004, 02:23 PM
  5. Simple 2D array problem...In a Hurry!
    By 67stangman in forum C++ Programming
    Replies: 8
    Last Post: 04-18-2002, 01:22 PM