Problems with the eight queens problem

This is a discussion on Problems with the eight queens problem within the C++ Programming forums, part of the General Programming Boards category; I heard from a friend of mine of the eight queens problem and I write a program to find all ...

  1. #1
    Registered User
    Join Date
    Aug 2007
    Posts
    13

    Problems with the eight queens problem

    I heard from a friend of mine of the eight queens problem and I write a program to find all solutions to it. My problem is that it doesn't find any solutions and Wikipedia says there must be 92 solutions to it. After writing the code it does look like I have used the backtracking method (see http://en.wikipedia.org/wiki/Eight_q...rsive_solution)

    I haven't only placed the code that deals with empty columns because I first wanted to see if the program worked.

    Here is the header:
    Code:
    #include <iostream>
    
    class chessboard
    {
    public:
    	chessboard();
    	void set_queen(const int &a, const int &b);
    	void remove_queen(const int &a, const int &b);
    	bool isqueen(const int &a, const int &b);
    	bool iseight();
    	bool ispossible(const int &a, const int &b);
    	bool isrowempty(const int &i);
    	void output();
    private:
    	/*
    	The 8x8 matrix field represents a chessboard
    	If there is a queen on the position, the value will be 1
    	If the position is under attack by a queen, the value will be -1
    	If a position is free then the value will be 0
    	*/
    	int field[8][8];
    };
    
    // Set all positions on the chessboard free
    chessboard::chessboard()
    {
    	for (int i = 0; i < 8; i++)
    		for (int j = 0; j < 8; j++)
    			field[i][j] = 0;
    }
    
    void chessboard::set_queen(const int &a, const int &b)
    {
    	field[a][b] = 1;			// Set the position of the new queen
    	
    	for (int i = 0; i < 8; i++)
    	{
    		if (i != a)				// Skip the place where the new queen is installed
    			field[i][b] = -1;	// Occupy the horizontal row seen from the new queen
    		if (i != b)				// Skip the place where the new queen is installed
    			field [a][i] = -1;	// Occupy the vertical row seen from the new queen
    	}
    	// The next four for-statements occupy the diagonal position seen from the new queen
    	// There are four for-statements: it goes diagonal forward and diagonal backward
    	for (int i = a + 1, j = b + 1; i < 8 && j < 8; i++, j++)
    		field[i][j] = -1;
    	for (int i = a + 1, j = b - 1; i < 8 && j >= 0; i++, j--)
    		field[i][j] = -1;
    	for (int i = a - 1, j = b + 1; i >= 0 && j < 8; i--, j++)
    		field[i][j] = -1;
    	for (int i = a - 1, j = b - 1; i >= 0 && j >= 0; i--, j--)
    		field[i][j] = -1;
    }
    
    void chessboard::remove_queen(const int &a, const int &b)
    {
    	field[a][b] = 0;
    	
    	// First set all positions that are under attack to 0
    	for (int i = 0; i < 8; i++)
    		for (int j = 0; j < 8; j++)
    			if (field[i][j] == -1)
    				field[i][j] = 0;
    	
    	// Then set the positions that are under attack to 0
    	// The positions that were under attack only by the removed queen
    	// aren't under attack now any more
    	for (int i = 0; i < 8; i++)
    		for (int j = 0; j < 8; j++)
    			if (field[i][j] == 1)
    				set_queen(i, j);
    }
    
    bool chessboard::isqueen(const int &a, const int &b)
    {
    	if (field[a][b] == 1)
    		return true;
    	else
    		return false;
    }
    
    bool chessboard::iseight()
    {
    	int queens = 0;
    	
    	for (int i = 0; i < 8; i++)
    		for (int j = 0; j < 8; j++)
    			if (field[i][j] == 1)
    				queens++;
    	if (queens == 8)
    		return true;
    	else
    		return false;
    }
    
    bool chessboard::ispossible(const int &a, const int &b)
    {
    	if (field[a][b])
    		return false;
    	else
    		return true;
    }
    
    bool chessboard::isrowempty(const int &i)
    {
    	for (int j = 0; j < 8; j++)
    		if (field[i][j] == 1)
    			return false;
    	return true;
    }
    
    void chessboard::output()
    {
    	for (int i = 0; i < 8; i++)
    		for (int j = 0; j < 8; j++)
    			if (field[i][j] == 1)
    				std::cout << char(97 + i) << j+1 << " ";
    	std::cout << std::endl;
    }
    and here is the code of my program
    Code:
    /***************************************************************************
    	The eight queens problem by Wicket under GPLv2
    
    This program will calculate all the possible solutions to place eight queens
    on a chessboard. 
    
    The program will start to place a queen at the first possible place and go
    on to place more queens on the next possible place until it reaches the end
    of the chessboard. It will produce output to the screen if there are eight
    queens placed on the chessboard. Then it removes the last queen and goes to
    place queens from the position next to the last removed queen. This goes on
    until the queen is removed from a8. After that it isn't possible to place
    eight queens on a chessboard
    ***************************************************************************/
    
    #include "chessboard.h"
    
    int main()
    {
    	chessboard board;
    	int a = 0, b = 0, counter = 0;
    	
    	// Run this while loop as long as all the posibilities haven't been checked
    	while(!board.isrowempty(0) || a == 0)
    	{
    		for (int i = a; i < 8; i++)
    			for (int j = b; j < 8; j++)
    				if (board.ispossible(i, j))		// Check if it is possible to place a queen
    					board.set_queen(i, j);
    		board.output(); 						// TEMPORARY: testing if everything is working
    		
    		// Produce output to screen if there are eight queens on the chessboard
    		if (board.iseight())
    		{
    			std::cout << ++counter << ": ";
    			board.output();
    		}
    		
    		// Remove the last queen
    		bool loop_break = false;
    		for (int i = 7; i >= 0; i--)
    		{
    			for (int j = 7; j >= 0; j--)
    				if (board.isqueen(i, j))
    				{
    					board.remove_queen(i, j);
    					// Set the start of the for-loops that will place queens on the field
    					// at the position next to the removed queen
    					if (j == 7)
    					{
    						a = i + 1;
    						b = 0;
    					}
    					else
    					{
    						a = i;
    						b = j + 1;
    					}
    					loop_break = true;
    					break;
    				}
    			if (loop_break)
    				break;
    		}
    		//board.output(); 							// TEMPORARY: testing if algorithms working
    	}
    	
    	return 0;
    }
    Note: just after the first double for in main the program will output how the queens are placed. So your screen will put much output. This line is for testing if it does everything well.

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I find problems such as these are more easily solved with recursion.

    In pseudocode:
    Code:
    solve(depth):
         if depth == 8: print solution
         else:
               for each square in depth-th row:
                   if square is free:
                        mark position
                        solve(depth + 1)
                        unmark position
    I also tackled this problem and decided that the board only tells whether a square is under fire or not and stored the positions of queens in a different array. This makes marking and unmarking board easier (the same function just adds +1 or -1 to all square affected by this queen - not even caring whether the square occupied by the queen gets marked more than once).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Bin packing problem....
    By 81N4RY_DR460N in forum C++ Programming
    Replies: 0
    Last Post: 08-01-2005, 06:20 AM
  2. Words and lines count problem
    By emo in forum C Programming
    Replies: 1
    Last Post: 07-12-2005, 04:36 PM
  3. problem: online on winxp and linux red hat
    By gemini_shooter in forum Linux Programming
    Replies: 5
    Last Post: 05-29-2005, 03:14 PM
  4. Resources with Dev C++ Problem (many simple problems)
    By Zeusbwr in forum Windows Programming
    Replies: 4
    Last Post: 04-07-2005, 12:08 AM
  5. binary tree problem - help needed
    By sanju in forum C Programming
    Replies: 4
    Last Post: 10-16-2002, 06:18 AM

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