Thread: 8 Queens, problem with searching 2D array

  1. #16
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719
    Ok, here is the code that I'm still having trouble with. It returns false, even when the queen is in a safe spot, and if it's in the first column with no other queens. I'm only checking to the left, because the recursive algorithm places queens from left to right. This seems so simple, yet it doesn't want to work. Any help is appreciated, I've been going crazy trying to figure out what's wrong.

    Code:
    bool isPathViable(int row, int column)
    {
    	
    	
    	for(int i=column;i >= 0; --i)	//Checks row
    	{
    		if(board[row][i]==1)
    			return false;
    	
    	}
    	
    	for(int j=row, k=column ; row >= 0, column >= 0;--row, --column)	//Checks left and up diagonal
    	{
    		if(board[j][k]==1)
    			return false;
    
    	}
    	
    	for(int u=row, h=column ;row >= 0,column >= 0;++row,--column)	//Checks left and down diagonal 
    	{
    		if(board[u][h]==1)
    			return false;
    	}
    
    	return true;
    		
    }
    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. #17
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Did you put the queen on the board already? If so, the very first thing you do is check the square you just filled.

  3. #18
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719
    Here is full code. However, I get weird results when I check for a queen.

    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 row, int column);
    
    int main()
    {
    	int n=8;
    
    	resetBoard();
    	
    	
    	/*for(int i=0; i < n; ++i)
    		solve(n,0,i);*/
    
    	addQueen(3,2);
    	addQueen(3,3);
    	displayBoard();
    	cout << isPathViable(3,3);
    
    	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(row,column))
    		displayBoard();
    
    	else if(isPathViable(row,column))
    		for(int i=0; i < n; ++i)
    			solve(n,i,column+1);
    	
    	removeQueen(row,column);
    }
    
    bool isPathViable(int row, int column)
    {
    	
    	
    	for(int i=column;i >= 0; --i)	//Checks row
    	{
    		if(board[row][i]==1)
    			return false;
    	
    	}
    	
    	for(int j=row, k=column ; row >= 0, column >= 0;--row, --column)	//Checks left and up diagonal
    	{
    		if(board[j][k]==1)
    			return false;
    
    	}
    	
    	for(int u=row, h=column ;row >= 0,column >= 0;++row,--column)	//Checks left and down diagonal 
    	{
    		if(board[u][h]==1)
    			return false;
    	}
    
    	return true;
    		
    }
    
    bool isPathSuccess(int row, int column)
    {
    	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 && isPathViable(row,column))
    		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!"

  4. #19
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    So the answer to the question is "yes". You put the queen down on a square, and then you check whether the square is covered. By definition, it will be covered, by the queen you just put down. You have to check before placing the queen, not after.

  5. #20
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719
    Quote Originally Posted by tabstop View Post
    So the answer to the question is "yes". You put the queen down on a square, and then you check whether the square is covered. By definition, it will be covered, by the queen you just put down. You have to check before placing the queen, not after.
    Oh I see, that was pretty stupid.

    I'm now having trouble with the actual function that solves it, when I display the board to see what is going on, almost all the board is covered in ones.

    Code:
    int main()
    {
    	int n=8;
    
    	resetBoard();
    	
    
    
    
    	for(int i=0; i < n; ++i)
    		solve(n,i,0);
    
    	displayBoard();
    
    
    	return 0;
    }
    Code:
    void solve(int n,int row, int column)
    {
    	addQueen(row,column);
    
    	if(isPathSuccess(row,column))
    		displayBoard();
    
    	else if(isPathViable(row,column))
    		for(int i=0; i < n; ++i)
    			solve(n,i,column+1);
    	removeQueen(row,column);
    }
    Videogame Memories!
    A site dedicated to keeping videogame memories alive!

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

    "We will game forever!"

  6. #21
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    if(board[i][j]=1)

    is assignemnt not comparison
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  7. #22
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719
    Quote Originally Posted by vart View Post
    if(board[i][j]=1)

    is assignemnt not comparison
    Thanks I missed that somehow. It corrected the board flooding with 1's, but now no queens are placed, even though I am placing them in my solve function.


    I've found that if I comment out the removeQueen function, all the 1's are straight down the first column, but there are no queens in the other columns. For some reason it's not incrementing to the next column, but shouldn't the "column+1" that I have deal with that?
    Last edited by Sentral; 03-11-2009 at 10:28 AM.
    Videogame Memories!
    A site dedicated to keeping videogame memories alive!

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

    "We will game forever!"

  8. #23
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by Sentral View Post
    Thanks I missed that somehow. It corrected the board flooding with 1's, but now no queens are placed, even though I am placing them in my solve function.
    I have this vague feeling that removeQueen might remove the queens from the board.

  9. #24
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719
    Quote Originally Posted by tabstop View Post
    I have this vague feeling that removeQueen might remove the queens from the board.
    Yes, you're right, but only at the specified "row,column" position and only if it ever reaches that point. Once the for loop in the solve function terminates, it would then call removeQueen, which would take that away from the board because that spot won't work.
    Videogame Memories!
    A site dedicated to keeping videogame memories alive!

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

    "We will game forever!"

  10. #25
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by Sentral View Post
    Yes, you're right, but only at the specified "row,column" position and only if it ever reaches that point. Once the for loop in the solve function terminates, it would then call removeQueen, which would take that away from the board because that spot won't work.
    Note that "only if it ever reaches that point" is the same as "always", since there is no control path through the function that does not execute that line.

  11. #26
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    bool isPathViable(int row, int column)

    is called AFTER the Queen is placed in the (row,column)

    if(board[row][i]==1) for i == column will be ALWAYS true

    so

    Code:
    void solve(int n,int row, int column)
    {
        if(isPathViable(row,column))
       {
            addQueen(row,column);
            if(column == 8)
                displayBoard();
            else
                for(int i=0; i < n; ++i)
                    solve(n,i,column+1);
            removeQueen(row,column);
       }
    }
    so,ething like that maybe?
    Last edited by vart; 03-11-2009 at 10:41 AM.
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  12. #27
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719
    Quote Originally Posted by tabstop View Post
    Note that "only if it ever reaches that point" is the same as "always", since there is no control path through the function that does not execute that line.
    I thought since I made a recursive call, it would go the beginning of the function, and not execute the remove function. So why would I need a control path?
    Videogame Memories!
    A site dedicated to keeping videogame memories alive!

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

    "We will game forever!"

  13. #28
    Registered User
    Join Date
    Mar 2009
    Posts
    344
    I'd check that this expression in the for() statements

    row >= 0, column >= 0

    really does what you hope it does. You'd probably want some sort of logical operator there instead of the comma.

    Come to think of it, the variables used inside the for loop might need some tweaking as well. The way it's written you're only checking one square for each for loop, but you're doing it a bunch of times.

  14. #29
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by Sentral View Post
    I thought since I made a recursive call, it would go the beginning of the function, and not execute the remove function. So why would I need a control path?
    Control paths are not sometime things; every function by definition has (at least one) control path that specifies which statements are executed. (Some people call them "flowcharts" and draw them with boxes.) They exist whether or not you pay attention to them.

    Recursive calls are fine and all, but a function always returns to where it was called from, so the function that calls itself recursively will still finish and run the rest of the function.

  15. #30
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719
    Quote Originally Posted by KCfromNC View Post
    I'd check that this expression in the for() statements

    row >= 0, column >= 0

    really does what you hope it does. You'd probably want some sort of logical operator there instead of the comma.

    Come to think of it, the variables used inside the for loop might need some tweaking as well. The way it's written you're only checking one square for each for loop, but you're doing it a bunch of times.
    I've fixed that, but I didn't post that code.

    Control paths are not sometime things; every function by definition has (at least one) control path that specifies which statements are executed. (Some people call them "flowcharts" and draw them with boxes.) They exist whether or not you pay attention to them.

    Recursive calls are fine and all, but a function always returns to where it was called from, so the function that calls itself recursively will still finish and run the rest of the function.
    I've put an else if(!isPathViable(row,column)) in the solve function, but It still didn't work. Why won't my recursive call increment to the next column. It doesn't even seem like it's getting called.
    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