Hey Everyone! Thanks for your help on my previous endevors. But, I've been working on this program for..... weeks, maybe months, and it's slowly evolved from different versions. This version uses OOP heavily, and it almost works. Okay, if you are not familiar with the '8 queens' problem, the objective is to place 8 queens on a chess board with none of them in location to attack each other. That's what my program does: sets 8 queens on a chess board, with none of them in position to attack another one.

My program seems to work, all the way up to the last queen. Whenever it goes to the 8th queen, it seems to forget to put down the seventh after it picks it up.

Okay, I'll provide a quick summary of how my program works. Basically, it starts with a queen, finds the first avaliable space that it can go in, sets it down, and shows what spaces are then able to be hit by that queen. It continues this way until no spaces are avaliable. Once that happens, it picks up the previous queen, and sets it down in a place it hasn't been set. If it has to go back more than one, it clears the spaces that the queens that are currently picked up have been in. I believe this will make every combination.

So here is my code now, I won't edit out my comments, cause they might provide some insight to what I'm thinkin about what might be wrong.

import java.util.ArrayList;

public class Queens2
{
    private int x = 0;
    private int y = 0;
    private int x2 = 0;
    private int y2 = 0;
    boolean pickedUp = false; 
    static int numberCreated = 0;
    //static Queens2[] allqueens = new Queens2[8];
    static ArrayList<Queens2> allqueens = new ArrayList<Queens2>(); 
    static ArrayList<Queens2> allqueens2 = new ArrayList<Queens2>();
    static ArrayList<Queens2> allqueens3 = new ArrayList<Queens2>();
    static int goTryCount = 0;
    int arrayNumber;
    int goTryCount2 = 0;
    private int[][] board2 ={{0,0,0,0,0,0,0,0},
                             {0,0,0,0,0,0,0,0},
                             {0,0,0,0,0,0,0,0},
                             {0,0,0,0,0,0,0,0},
                             {0,0,0,0,0,0,0,0},
                             {0,0,0,0,0,0,0,0},
                             {0,0,0,0,0,0,0,0},
                             {0,0,0,0,0,0,0,0} };
    static Queens2 lastQueen;
    static int[][] board = { {0,0,0,0,0,0,0,0},
                             {0,0,0,0,0,0,0,0},
                             {0,0,0,0,0,0,0,0},
                             {0,0,0,0,0,0,0,0},
                             {0,0,0,0,0,0,0,0},
                             {0,0,0,0,0,0,0,0},
                             {0,0,0,0,0,0,0,0},
                             {0,0,0,0,0,0,0,0} };
                             
                             
    
    public Queens2()
    {
        arrayNumber = numberCreated;
        goTryCount2 = 0;
        allqueens.add(this);
        pickedUp = true;
        goTry();
        numberCreated++;
    }
    
    private void goTry()
    {
        goTryCount++;
        goTryCount2++;
        if (goTryCount > 88)
        {
            //This is around where the program messes up...
            System.out.print("");
        }
        // I shouldn't need this,  cause It's done when you set it down now....
        allqueens2.clear();
        allqueens3.clear();
        nextStuff();
        for (Queens2 currentQueen2 : allqueens2)
        {
            if (currentQueen2 == null)
            {}
            else
            {
                currentQueen2.setDown();
                //Sets everyting down again,  so that two locations taken by the queens
                //are still at the put as a 1,  not a 0
            }
        }
        
        while (board [x] [y] != 0 || board2 [x] [y] != 0)
        {
            y++;
            
            if (y > 7)
            {
                y = 0;
                x++;
                if (x > 7) //Moves it through (0,0) to (8,0) then picks up the last one and sets it down 
                //if there is an avaliable spot
                // if not, it picks up the one before that, sets it down,  then the first one picked up... ect.,  
                {
                    //---------------------------------------------------------------
                    allqueens2.clear();
                    allqueens3.clear();
                    nextStuff();
                    int queenToPickUpLocation = allqueens2.indexOf(lastQueen);
                    
                    for (Queens2 currentQueen : allqueens3)
                    {
                        int yes = allqueens3.indexOf(currentQueen);
                        if (yes > queenToPickUpLocation)
                        {
                            currentQueen.board2Clear();
                            int queenLocation = allqueens.indexOf(currentQueen);
                            allqueens.get(queenLocation).board2Clear();
                            
                            
                            //I need to make sure the actuall objects are also being cleared
                            //Not just the Aliases....
                            
                            //Now What did I make this for.... Is this the solution to my problems?
                            int queenToPick = -1;
                            for (Queens2 currentQueen3 : allqueens)
                            {
                                if (currentQueen3.getArrayNumber() == arrayNumber)
                                {
                                    queenToPick = allqueens3.indexOf(currentQueen3);
                                }
                            }
                            
                        }
                    }
                    //I'm using the previous alias,  and I need to use the new one.....
                    /** for (Queens2 currentQueen2 : allqueens2)
                    {
                        if (currentQueen2 == null)
                        {}
                        else
                        {
                           currentQueen2.setDown();
                        }
                     }
                     */
                    
                    (allqueens2.get(queenToPickUpLocation)).pickUp();
                    x = 0;
                    y = 0;
                }
                //------------------------------------------------------------------------------------------------
             }
         }
         setDown();
      }
    
    private void setDown()
    {
        int queenToPick = -1;
        for (Queens2 currentQueen : allqueens)
        {
            if (currentQueen.getArrayNumber() == arrayNumber)
            {
                queenToPick = allqueens.indexOf(currentQueen);
            }
        }
        allqueens.get(queenToPick).setPickedUp(false);
        // This isn't working, Not Sure why...
        pickedUp = false;
        x2 = 0;
        while (x2 < 7)
        {
            x2++;
            if31(1);
        }
        if31(1);
        y2 = 0;
        while (y2 < 7)
        {
            y2++;
            if32(1);
        }
        if32(1);
        y2 = y;
        x2 = x;
        while (y2 < 7 && x2 < 7)
        {
            x2++;
            y2++;
            if33(1);
        }
        if33(1);
        x2 = x;
        y2 = y;
        while (y2 < 7 && y2 >= 1 && x2 < 7)
        {
            x2++;
            y2--;
            if33(1);
        }   
        if33(1); 
        x2 = x;
        y2 = y;
        while (y2 < 7 && y2 >= 1 && x2 < 7 && x2 >= 1)
        {
            x2--;
            y2--;
            if33(1);
        }
        if33(1);
        x2 = x;
        y2 = y;
        while (y2 < 7 && x2 < 7 && x2 >= 1)
        {
            x2--;
            y2++;
            if33(1);
        }
        if33(1);
        x2 = x;
        y2 = y;
        board[x] [y] = 2;
        board2[x] [y] = 1;
        allqueens.get(queenToPick).setBoard2(x,y,1);
    }
    
    private void setBoard2(int x3, int y3, int n)
    {
        board2[x3][y3] = n;
    }
    
    public void pickUp()
    {
        //int locationOfQueen = (allqueens.indexOf(this));
        //(allqueens.get(locationOfQueen)).setPickedUp(true);
        int queenToPick = -1;
        for (Queens2 currentQueen : allqueens)
        {
            if (currentQueen.getArrayNumber() == arrayNumber)
            {
                queenToPick = allqueens.indexOf(currentQueen);
            }
        }
        allqueens.get(queenToPick).setPickedUp(true);
        pickedUp = true;
        x2 = 0;
        while (x2 < 7)
        {
            if31(0);
            x2++;
        }
        if31(0);
        y2 = 0;
        while (y2 < 7)
        {
            if32(0);
            y2++;
        }
        if32(0);
        y2 = y;
        x2 = x;
        while (y2 < 7 && x2 < 7)
        {
            x2++;
            y2++;
            if33(0);
        }
        if33(0);
        x2 = x;
        y2 = y;
        while (y2 < 7 && y2 >= 1 && x2 < 7)
        {
            x2++;
            y2--;
            if33(0);
        }
        if33(0);
        x2 = x;
        y2 = y;
        while (y2 < 7 && y2 >= 1 && x2 < 7 && x2 >= 1)
        {
            x2--;
            y2--;
            if33(0);
        }
        if33(0);
        x2 = x;
        y2 = y;
        while (y2 < 7 && x2 < 7 && x2 >= 1)
        {
            x2--;
            y2++;
            if33(0);
        }
        if33(0);
        x2 = x;
        y2 = y;
        setX(0);
        setY(0);
        allqueens2.clear();
        allqueens3.clear();
        nextStuff();
        for (Queens2 currentQueen2 : allqueens2)
        {
            if (currentQueen2 == null)
            {}
            else
            {
                currentQueen2.setDown();
                //Sets everyting down again,  so that two locations taken by the queens
                //are still at the put as a 1,  not a 0
            }
        }
        goTry();
    }
    
  
    public static int[][] getBoard()
    {
        return board;
    }
    public boolean getPickedUp()
    {
        return pickedUp;
    }
    
    public int getX()
    {
        return x;
    }
    
    public int getY()
    {
        return y;
    }
    
    private void setX(int num)
    {
        x = num;
    }
    
    private void setY(int num)
    {
        y = num;
    }
    
    private void setPickedUp (boolean eh)
    {
        pickedUp = eh;
    }
    
    public int getArrayNumber()
    {
        return arrayNumber;
    }
    
    private void nextStuff ()
    {
        for (Queens2 next : allqueens)
        {
            allqueens3.add(next);
            if (!next.getPickedUp())
            {
                allqueens2.add(next);
                lastQueen = next;
            }
        }
    }
    
    private void if31(int num)
    {
        if (board[x2] [y] == 3)
        {
        }
        else
        {
            board[x2] [y] = num;
        }
    }
    
    private void if32(int num)
    {
        if (board[x] [y2] == 3)
        {
        }
        else
        {
            board[x] [y2] = num;
        }
    }
    
    private void if33(int num)
    {
        if (board[x2] [y2] == 3)
        {
        }
        else
        {
            board[x2] [y2] = num;
        }
    }
    
    public void board2Clear()
    {
        int r = 0;
        int s = 0;
        while ( s < 7)
        {
            board2[r] [s] = 0;
            r++;
            if ( r > 7)
            {
                r = 0;
                s++;
            }
        }
    }
    
    public static void printBoard()
    {
        for (int[] p : board)
        {
            for(int l : p)
            {
                System.out.print(l + " ");
            }
            System.out.println();
        }
            
    }
    
    public void printBoard2()
    {
        for (int[] p : board2)
        {
            for(int l : p)
            {
                System.out.print(l + " ");
            }
            System.out.println();
        }
            
    }
    
    public boolean checkOnBoard()
    {
        if (board[x][y] == 2)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
        
}

I believe some of my methods aren't being used for anything, and some of them are kinda pointless, sorry!

Thanks for your help!

(It's amazing how big the code gets..... I never thought I wrote 400 lines of code... even if some of them are just blank lines with curly brackets.)

Oh yeah, I forgot!
I didn't write a driver class as I was running it on BlueJ using it's ability to creat objects, and also, this is not a homework assignment, I'm doing it for fun, and I had been debugging for a long time before I posted this.

Seems like a simply program, why would it take so long?

Theres only 8!=40,320 positions to look at then test.

If you put a queen in each column, then first queen has 8 options, next has 7, and so on, so filling up a position this way means you just need to test diagonal attacks.

I reckon it would probably be even faster using a bitboard instead of a double array.

so if square a8 has index 0, h8 index 7, a1 index 56, h1 index 63.
Each square has a binary value
2^index=1<<index

So you could have
long queens=(1<<q1_index) | (1<<q2_index) | ... | (1<<q8_index)

And then apply some other technique to make sure theres at most 1 queen on any diagonal,
eg queens & DIAGONAL_a3_to_f8_MASK == 0 or 1<<x.

Just an idea

True, I did think of that about half way through, that each Queen must be in each column and row, and so that does narrow down the combinations a bit. We don't learn bitboards until next year I believe, but I wouldn't mind getting a head start! Anyone know of a good way to learn it easily? Any tutorials around?

But, nonetheless, it might be time to restart this program from scratch again... I won't do it quite yet, but it feels so close to the solution.......

This article has been dead for over six months. Start a new discussion instead.