C++ N queens problem

Discussion in 'OT Technology' started by durondude, Jun 11, 2007.

  1. durondude

    durondude OT Addict

    Joined:
    May 7, 2001
    Messages:
    24,058
    Likes Received:
    5
    Location:
    Earth, The Planet
    :wiggle:
    fastest evar! Kinda cheating and not as fun as brute force method but way faster!

    Code:
    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    vector <int> addVectors( vector <int> & a , vector <int> & b ){
    	vector <int> temp;
    
    	for( int x = 0 ; x < a.size() ; x ++ )
    		temp.push_back( a[x] );
    
    	for( int x = 0 ; x < b.size() ; x++ )
    		temp.push_back( b[x] );
    
    	return temp;
    }
    
    void listPieces( vector <int> pieces ){
    	for( int x = 0 ; x < pieces.size() ; x ++ ){
    		cout << "(" << pieces[x] << "," << x << ")" << endl;
    	}
    }
    
    void drawBoard( vector <int> & pieces ){
    	for( int x = 0 ; x < pieces.size() ; x++ )
    		cout << " _";
    
    	cout << endl;
    
    	for( int y = 0 ; y < pieces.size() ; y ++ ){
    		for( int x = 0 ; x < pieces.size() ; x ++ ){
    			if( pieces[y]-1 == x ){
    				cout << "|o";
    			} else {
    				cout << "|_";
    			}
    		}
    		cout << "|" << endl;
    	}
    }
    
    int main( void ){
    	int num, rem;
    	vector <int> evens;
    	vector <int> odds;
    	vector <int> queens;
    
    	cout << "N?: ";
    	cin >> num;
    
    	if( ( num == 2 ) || ( num == 3 ) ){
    		cout << "Sorry, " << num << " won't work, please enter a number that is = 1 or > or = to 4" << endl;
    		return 0;
    	}
    
    	rem = num % 12;
    
    	for( int x = 2 ; x <= num ; x += 2 ){
    		evens.push_back( x );
    	}
    
    	for( int x = 1 ; x <= num ; x += 2 ){
    		odds.push_back( x );
    	}
    
    	if( rem == 8 ){//switch pairs
    		vector <int> temp;
    
    		for( int x = 0 ; x < odds.size() ; x += 2 ){
    			temp.push_back( odds[x+1] );
    			temp.push_back( odds[x] );
    		}
    		odds = temp;
    	}
    
    	if( ( rem == 3 ) || ( rem == 9 ) ){//move 2 to end of list.
    		evens.erase( evens.begin() );
    		evens.push_back( 2 );
    	}
    
    	if( rem == 2 ){//switch places of 1 and 5 , move 5 to the end of the list
    		//switch 1 and 3
    		odds.erase( odds.begin() );
    		odds.erase( odds.begin() );
    
    		if( num > 4 ){
    			odds.erase( odds.begin() );
    			odds.push_back( 5 );
    		}
    
    		odds.insert( odds.begin() , 1 );
    		odds.insert( odds.begin() , 3 );
    	}
    
    	if( ( rem == 3 ) || ( rem == 9 ) ){
    		int a = odds[0];
    		int b = odds[1];
    
    		odds.erase( odds.begin() );
    		odds.erase( odds.begin() );
    
    		odds.push_back( a );
    		odds.push_back( b );
    	}
    	
    	queens = addVectors( evens , odds );
    
    	drawBoard( queens );
    	listPieces( queens ); 
    
    	return 0;
    }
    I'll post the brute force method also if anyone is interested
     
  2. deusexaethera

    deusexaethera OT Supporter

    Joined:
    Jan 27, 2005
    Messages:
    19,712
    Likes Received:
    0
    What the hell are you talking about?
     
  3. durondude

    durondude OT Addict

    Joined:
    May 7, 2001
    Messages:
    24,058
    Likes Received:
    5
    Location:
    Earth, The Planet
    The eight queens puzzle is the problem of putting eight chess queens on an 8×8 chessboard such that none of them is able to capture any other using the standard chess queen's moves. The colour of the queens is meaningless in this puzzle, and any queen is assumed to be able to attack any other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens puzzle of placing n queens on an n×n chessboard.
     
  4. durondude

    durondude OT Addict

    Joined:
    May 7, 2001
    Messages:
    24,058
    Likes Received:
    5
    Location:
    Earth, The Planet
    compile it and run it to see what the hell i am talking about
     
  5. durondude

    durondude OT Addict

    Joined:
    May 7, 2001
    Messages:
    24,058
    Likes Received:
    5
    Location:
    Earth, The Planet
    here is the slow method

    anyone know how I could speed this up?
    Code:
    #include <vector>
    #include <iostream>
    #include <string>
    
    using namespace std;
    
    class queen;
    class row;
    class square;
    
    class queen{
    public:
    	queen( int col );
    	bool shiftRight( int num );
    	int getCol();
    
    private:
    	int col;
    };
    
    class row{
    public:
    	square & operator[]( const int index );
    	void resize( const int num );
    	int size();
    	bool checkRow();
    	
    private:
    	vector <square> data;
    };
    
    class square{
    public:
    	square();
    	void occupy();
    	void unOccupy();
    	bool isOccupied();
    private:
    	bool occupied;
    };
    
    queen::queen( int col ){
    	queen::col = col;
    }
    
    bool queen::shiftRight( int num ){
    	if( col + 1 < num ){
    		col++;
    		return true;
    	} else {
    		return false;
    	}
    }
    
    int queen::getCol(){
    	return queen::col;
    }
    
    square & row::operator[]( const int index ){
    	return row::data[ index ];
    }
    
    void row::resize( const int num ){
    	row::data.resize( num );
    }
    
    int row::size(){
    	return row::data.size();
    }
    
    bool row::checkRow(){
    	for( int c = 0 ; c < row::data.size() ; c ++ ){
    		if( row::data[c].isOccupied() ) return false;
    	}
    
    	return true;
    }
    
    square::square()
    {
    	square::occupied = false;
    }
    
    void square::occupy(){
    	square::occupied = true;
    }
    
    void square::unOccupy(){
    	square::occupied = false;
    }
    
    bool square::isOccupied(){
    	if( occupied ) return true;
    	else return false;
    }
    
    bool checkSquare( vector <row> & board , int x , int y , int size ){
    	//cout << "Checking square (" << x << "," << y << ")" << endl;
    
    	//check row for queens
    	//cout << "Checking row - ";
    	if( board[y].checkRow() ){
    		//cout << "empty" << endl;		
    	} else {
    		//cout << "taken" << endl;
    		//cout << "Failed" << endl;
    		
    		return false;
    	}
    	//cout << "Success" << endl;
    
    	//check column for queens
    	//cout << "Checking column - ";
    	for( int c = 0 ; c < board.size() ; c ++ ){ //check squares above
    		if( board[c][x].isOccupied() ){
    			//cout << "taken" << endl;
    			//cout << "Failed" << endl;
    
    			return false;
    		} else {
    			//cout << "empty" << endl;
    		}
    	}
    	//cout << "Success" << endl;
    	
    	//check diagonals (the fun part)
    	int x1 = x;
    	int y1 = y;
    	for(;;){ // Check squares behind and above
    		if( ( x1 < 0 ) || ( y1 < 0 ) ){
    			break;
    		}
    
    		if( board[y1][x1].isOccupied() ){
    			return false;
    		}		
    
    		x1--;
    		y1--;
    	}
    
    	
    	x1 = x;
    	y1 = y;
    	for(;;){ // Check squares behind and below
    		if( ( x1 < 0 ) || ( y1 >= board.size() ) ){
    			break;
    		}
    
    		if( board[y1][x1].isOccupied() ){
    			return false;
    		}
    
    		x1--;
    		y1++;
    	}
    	
    	x1 = x;
    	y1 = y;
    	for(;;){ // Check squares infront and above
    		if( ( x1 >= board.size() ) || ( y1 < 0 ) ){
    			break;
    		}
    
    		if( board[y1][x1].isOccupied() ){
    			return false;
    		}
    
    		x1++;
    		y1--;
    	}
    	
    	x1 = x;
    	y1 = y;
    	for(;;){ // Check squares infront and below
    		if( ( x1 >= board.size() ) || ( y1 >= board.size() ) ){
    			break;
    		}
     
    		if( board[y1][x1].isOccupied() ){
    			return false;
    		}
    
    		x1++;
    		y1++;
    	}
    	
    
    	//if no queens found return true
    	//cout << "- Square ok!" << endl;
    	return true;
    }
    
    void fillBoard( vector <row> & board , int size ){
    	board.resize( size );
    	for( int c = 0 ; c < size ; c ++ ){
    		board[c].resize( size );
    	}
    
    	for( int c = 0 ; c < board.size() ; c ++ ){
    		for( int r = 0 ; r < board[ c ].size() ; r ++ ){
    			board[ c ][ r ].unOccupy();
    		}
    	}
    }
    
    void drawBoard( vector <row> & board ){
    	for( int x = 0 ; x < board.size() ; x ++ ){
    		cout << " _";
    	}
    	cout << endl;
    
    	for( int y = 0 ; y < board.size() ; y ++ ){
    		for( int x = 0 ; x < board.size() ; x ++ ){
    			if( board[y][x].isOccupied() )
    				cout << "|o";
    			else
    				cout << "|_";
    		}
    		cout << "|" << endl;
    	}
    }
    
    void listQueens( vector <queen> queens ){
    	cout << queens.size() << " Queens!" << endl;
    	for( int x = 0 ; x < queens.size() ; x ++ ){
    		cout << "(" << queens[x].getCol()+1 << "," << x+1 << ")" << endl;
    	}
    }
    
    void clearRow( vector <row> & board , int row ){
    	for( int x = 0 ; x < board.size() ; x ++ ){
    		board[x][row].unOccupy();
    	}
    }
    
    void updateBoard( vector <row> & board , vector <queen> & queens , int num ){
    	fillBoard( board , num );
    
    	for( int y = 0 ; y < queens.size() ; y ++ ){
    		int x = queens[y].getCol();
    		board[y][x].occupy();
    	}
    }
    
    int main( void ){
    	int num;
    	bool allFound = false;
    	int crow = 0;
    	int ccol = 0;
    	bool nextRow = false;
    	vector <queen> queens;
    
    	cout << "Number of rows?: ";
    	cin >> num;
    
    	vector <row> board;	
    
    	fillBoard( board , num );
    
    	while( allFound == false ){
    		nextRow = false;
    
    		if( ccol >= num ){
    			//cout << "Backtrack" << endl;
    			crow-=1;
    			ccol = queens.back().getCol() + 1;
    			queens.pop_back();
    			updateBoard( board , queens , num );
    			//drawBoard( board );
    		}
    
    		if( ccol < num ){
    			//cout << "Trying (" << ccol+1 << "," << crow+1 << ") - ";
    			if( checkSquare( board , ccol , crow , num ) ){
    				//cout << "Good." << endl;
    
    				queen temp( ccol );
    				queens.push_back( temp );
    				nextRow = true;
    				ccol = 0;
    				crow++;
    
    				updateBoard( board , queens , num );
    				//drawBoard( board );
    			} else {
    				//cout << "No good, next" << endl;
    
    				ccol++;
    			}
    		}
    
    		if( crow >= num ){
    			allFound = true;
    			break;
    		}
    
    		//cout << "Row: " << crow << ", Col: " << ccol << endl;
    		updateBoard( board , queens , num );
    		//drawBoard( board );
    	}
    
    	updateBoard( board , queens , num );
    	drawBoard( board );
    	listQueens( queens );
    
    	return 0;
    }
    
     
  6. deusexaethera

    deusexaethera OT Supporter

    Joined:
    Jan 27, 2005
    Messages:
    19,712
    Likes Received:
    0
    Once you actually posted a description, it was immediately clear what you were doing. Thanks.
     
  7. Sexual Vanilla

    Sexual Vanilla New Member

    Joined:
    May 23, 2005
    Messages:
    6,305
    Likes Received:
    0
    Location:
    South Carolina
    Knights Tour > Queens
     
  8. durondude

    durondude OT Addict

    Joined:
    May 7, 2001
    Messages:
    24,058
    Likes Received:
    5
    Location:
    Earth, The Planet
    please explain
     
  9. deusexaethera

    deusexaethera OT Supporter

    Joined:
    Jan 27, 2005
    Messages:
    19,712
    Likes Received:
    0
    Real software > Math games
     
  10. Sexual Vanilla

    Sexual Vanilla New Member

    Joined:
    May 23, 2005
    Messages:
    6,305
    Likes Received:
    0
    Location:
    South Carolina
  11. durondude

    durondude OT Addict

    Joined:
    May 7, 2001
    Messages:
    24,058
    Likes Received:
    5
    Location:
    Earth, The Planet
    true, I was helping my cousin with his C++ hw
     
  12. samm

    samm Next in Line

    Joined:
    Dec 22, 2000
    Messages:
    2,630
    Likes Received:
    0
    Location:
    San Jose, CA

Share This Page