8 Queens, problem with searching 2D array

This is a discussion on 8 Queens, problem with searching 2D array within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by vart bool isPathViable(int row, int column) is called AFTER the Queen is placed in the (row,column) if(board[row][i]==1) ...

  1. #31
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719
    Quote Originally Posted by vart View Post
    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?
    I seem to get the same results with this, as I do with my code, just a blank board. Perhaps it is the loop in the main function that is messing me up?

    EDIT- I've changed the loop in main, and I get queens that are placed, but they are kind of random, and don't follow the rules.
    Last edited by Sentral; 03-11-2009 at 11:16 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!"

  2. #32
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719
    I've fixed it up a lot more. I got it to place the first queen in the top-left corner, then place the second queen in a way that it is safe from the first. However, after this, it doesn't go on to the other columns.

    Main:
    Code:
    int main()
    {
    	int n=8;
    
    	resetBoard();
    	
            for(int i=0;i < 8;i++)
    		solve(8,0,i);
    
            displayBoard();
    
            return 0;
    }
    Solve:
    Code:
    void solve(int n,int row, int column)
    {
    	if(isPathSuccess(row,column))
    		displayBoard();
    	
    	else if(isPathViable(row,column))
    	{
    		addQueen(row,column);
    		
    		cout << "[" << row << "," << column << "]" << endl;
    		
    		for(int i=0; i < n; ++i)
    			solve(n,i,column+1);
    	}
    	
    	else
    		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!"

  3. #33
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,424
    why do you remove the Queen from the cell where you have not placed it?
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  4. #34
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719
    Quote Originally Posted by vart View Post
    why do you remove the Queen from the cell where you have not placed it?
    I'm not sure that's the part I need help with. How would I remove the Queen that I placed, but that is in a threatening position?

    I'm not really sure where to place the removeQueens function, and what to pass it, I've tried putting it everywhere it seems.
    Last edited by Sentral; 03-11-2009 at 01:16 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!"

  5. #35
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,424
    Code:
    #include <iostream>
    
    using namespace std;
    
    
    void displayBoard(int size);
    void addQueen(int row, int column);
    void removeQueen(int row,int column);
    void solve(int size, int column, int row);
    
    bool isPathViable(int row, int column);
    
    const int size = 8;
    int board[size][size] = {0};
    
    
    int main()
    {
    	for(int i=0;i < size;i++)
    		solve(size,i,0);
    
    	return 0;
    }
    
    void solve(int size,int row, int column)
    {
    
    	if(isPathViable(row,column))
    	{
    		addQueen(row,column);
    
    		if(column == size - 1)
    		{
    			displayBoard(size);
    		}
    		else
    		{
    			for(int i=0; i < size; ++i)
    			{
    				if(i != row)
    					solve(size,i,column+1);
    			}
    		}
    		removeQueen(row,column);	
    	}
    	return ;
    }
    
    bool isPathViable(int row, int column)
    {
    	for(int i=column-1;i >= 0; --i)	//Checks row
    	{
    		if(board[row][i]==1)
    			return false;
    
    	}
    
    	for(int j=row-1, k=column-1 ; j >= 0, k >= 0;--j, --k)	//Checks left and up diagonal
    	{
    		if(board[j][k]==1)
    			return false;
    
    	}
    
    	for(int u=row+1, h=column-1 ;u >= 0,h >= 0;++u,--h)	//Checks left and down diagonal 
    	{
    		if(board[u][h]==1)
    			return false;
    	}
    
    	return true;
    
    }
    
    void displayBoard(int size)
    {
    	for(int i=0; i < size; ++i)
    	{
    		for(int j=0; j < size; ++j)
    			cout << board[i][j] << " ";
    
    		cout << "\n";
    	}
    	cout << "\n";
    	cout << "\n";
    }
    
    void addQueen(int row,int column)
    {
    	board[row][column]=1;
    }
    
    void removeQueen(int row,int column)
    {
    	board[row][column]=0;
    }
    find n differencies...
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  6. #36
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719
    Thanks! It seems so simple, but I see what I messed up. I've been going crazy trying to figure this out!
    Videogame Memories!
    A site dedicated to keeping videogame memories alive!

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

    "We will game forever!"

Page 3 of 3 FirstFirst 123
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, 01: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, 07:17 PM
  4. 2d array problem
    By LiLgirL in forum Windows Programming
    Replies: 1
    Last Post: 03-15-2004, 01: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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21