10 Replies - 3848 Views - Last Post: 05 May 2009 - 06:43 AM Rate Topic: -----

#1 virgul  Icon User is offline

  • D.I.C Regular

Reputation: 44
  • View blog
  • Posts: 269
  • Joined: 18-March 09

little help with 8 queens

Posted 03 May 2009 - 02:22 PM

So this is actually a friends project that im helping him out with, but i cant figure out how to make it work properly. looking through the code, it needs a lot of work, but i dont want to change it to much, because after all it is his project.

Here is my friends take on the attacking queens thing.
You place the first queen and from there the program will place the rest of the queens showing one answer.

Here is what the problem is. with this code, once it gets to a point where there is no solution for the placement of the second queen, aka there are no longer any places for the next queen to be placed, yet there arnt 8, the program stops (i did this, to stop it from giving an error, shows what its got so far.)


So here is where the placement is done
public class subQueens extends queen
{
	int[][] arrayBoard;
	int queen = 0;
	board BOARD;
	boolean done = false;
	public subQueens(board Board)
	{
		BOARD = Board;
		arrayBoard = Board.getBoard();
		tryPlacement();
	}
	
	public void tryPlacement()
	{
		if(!done)
		{
		   
			placeNextQueen(0);
		}
		if(done)
		{
			System.out.println("Done!");
		}
	}
	
	public boolean placeNextQueen(int y)   // places queens 2-8
	{
//		 System.out.println(x+1);
	   
		if(queen == 8)
		{
			return true;
		}
		for(int x = 0; x < 8; x++)
		{
			if(arrayBoard[x][y]==0)
			{
				BOARD.placeQueen(x,y);
				queen++;
				done = placeNextQueen(y+1);
				if(done)
				{
					return true;
				}
			}
		}
		
		 System.out.println("try " + (queen + 1));
		
//			 queen++;
		// if we get here it needs to restart
		return false;
	}

}


My problem is i dont know how to get it to "restart" from the second queen

any help would be great.

Is This A Good Question/Topic? 0
  • +

Replies To: little help with 8 queens

#2 333OnlyHalfEvil  Icon User is offline

  • D.I.C Addict

Reputation: 24
  • View blog
  • Posts: 674
  • Joined: 20-March 09

Re: little help with 8 queens

Posted 03 May 2009 - 02:41 PM

Can you explain the scope of the project a little more? By queens, do you mean queen pieces for chess? What are the queens attacking? Also, can you post the class queen that subqueen is extending and the class board?
Was This Post Helpful? 0
  • +
  • -

#3 Mikeyp926  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 29
  • View blog
  • Posts: 205
  • Joined: 20-March 09

Re: little help with 8 queens

Posted 03 May 2009 - 02:42 PM

http://www.dreaminco...snippet3386.htm

Here's a code snippet showing this program working. You could modify it pretty easily to take the input for where to place the first queen. Hopefully this helps you. I don't have time right now to debug your code and try and figure out what is going on, but if I get a chance later I'll try and fix it up.

I can tell you right now though that the problem is probably with this
"if(arrayBoard[x][y]==0)" Think about what you are checking here? You're just checking if there is already a queen in that spot, so if there isn't you automatically put a queen there. What you really want to check is if putting a queen there causes a conflict with other queens already placed, right? think about how you can do that, and look at the snippet for an example. I actually wrote another method that returned whether or not a certain placement causes a conflict.

Hope this helps and that I understood you correctly!
-Michael
Was This Post Helpful? 0
  • +
  • -

#4 virgul  Icon User is offline

  • D.I.C Regular

Reputation: 44
  • View blog
  • Posts: 269
  • Joined: 18-March 09

Re: little help with 8 queens

Posted 03 May 2009 - 03:34 PM

I was actually looking at that snippet earlier today, the only thing i dont get about it is how to actually change where to put the first queen.

o, and for
if(arrayBoard[x][y]==0)
what is going on here is everytime a piece is placed on the board all possible attacking positions are filled with 1's. this way there are no conflicts.


o and 333OnlyHalfEvil this is a chess board, 8*8, and you have 8 queens and you are trying to place them all on the board so they cant attach eachother, good reference is http://en.wikipedia....t_queens_puzzle.
Was This Post Helpful? 0
  • +
  • -

#5 Mikeyp926  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 29
  • View blog
  • Posts: 205
  • Joined: 20-March 09

Re: little help with 8 queens

Posted 03 May 2009 - 10:55 PM

Ah, ok, I wasn't sure what the BOARD.placeQueen(x, y); did, but I guess that explains it :)

As for using the snippet, it shouldn't be too hard to take user input to set the starting input.

Assuming you have the starting position in an int startPos, then just right after you fill the board with hyphens in the main method, add a queen at that position
board[0][startPos] = 'Q';



And then when you originally call the solve method you would call it on the second row rather than the first
if(solve(sizeOfBoard, board, 1))
				{		//if true, we know that the board array contains a solution
						printBoard(sizeOfBoard, board);
				}
				else
				{		//if false, we know that no solutions exist on this size of board
						System.out.println("No solutions are possible with this board size.");
				}



I haven't tested this, but it seems like it should work.
However, this is assuming that you are only allowing the user to place the queen in the first row of the board. The snippet assumes that queens have only been placed above the current row. Hopefully the assignment says the user can only place it in the first row. If they are allowed to place it anywhere, then at least a few changes would have to be made, but it still would be doable.

Does this help?

If you want to stick with the way that your friend started doing it that is fine also. Sometime these recursive solutions are kinda tricky to debug, but I'd suggest using the debugger and stepping through everything to see why the program isn't working entirely.

Are you using an ide like eclipse?

-Michael

This post has been edited by Mikeyp926: 03 May 2009 - 10:56 PM

Was This Post Helpful? 0
  • +
  • -

#6 virgul  Icon User is offline

  • D.I.C Regular

Reputation: 44
  • View blog
  • Posts: 269
  • Joined: 18-March 09

Re: little help with 8 queens

Posted 03 May 2009 - 11:42 PM

well, that makes sense, i was having it still starting on 0, thats prolly why i couldnt figure out how to change your version. if i cant get my friends to work then i will try that.

Now the thing with my friends program is there is no actual error in the program, whats going on is its finding that there are no more positions left and just stopping even though its supposed to place 8 queens it stops at the current number.


an example run is this if the first coordinates are (8,8)
1	5	1	1	1	1	1	1	

1	1	1	5	1	1	1	1	

5	1	1	1	1	1	1	1	

1	1	5	1	1	1	1	1	

1	1	1	1	1	1	1	1	

1	1	1	1	1	1	1	1	

1	1	1	1	1	1	1	1	

1	1	1	1	1	1	1	5


1's are where attacking is possible, so there are no more places to place the next queens, meaning end of program
Was This Post Helpful? 0
  • +
  • -

#7 Mikeyp926  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 29
  • View blog
  • Posts: 205
  • Joined: 20-March 09

Re: little help with 8 queens

Posted 04 May 2009 - 12:21 AM

Hmmmm, I'm not sure I fully understand your example run. What does the 5 represent?
Was This Post Helpful? 0
  • +
  • -

#8 virgul  Icon User is offline

  • D.I.C Regular

Reputation: 44
  • View blog
  • Posts: 269
  • Joined: 18-March 09

Re: little help with 8 queens

Posted 04 May 2009 - 07:40 AM

5 is a queen, i know it makes much more sense to be using a char[][], but he has no idea what that is. So he used an int[][].
Was This Post Helpful? 0
  • +
  • -

#9 Mikeyp926  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 29
  • View blog
  • Posts: 205
  • Joined: 20-March 09

Re: little help with 8 queens

Posted 04 May 2009 - 12:59 PM

Ok, well that makes sense then.

I think the way you are approaching this problem might not work. Rather then marking which squares are being attacked, I think you should make a method that checks whether or not a square is being attacked. I'll explain why.

In the situation you described, you are correct that you can't place a queen anywhere on the 5th row. However, instead of the program ending it should actually go back to the 4th row and keep moving that queen over until it finds another legal position. So in this case it would move over to the 7th column right? And then your program would continue on.

So basically, if you try to place a queen in a row and there are no available spots, rather that ending, your program should go back up one row and move that queen over to the next legal spot. This keeps happening until you find an arrangement that solves the problem.

However, the way that you are doing it, when you place a queen it marks all the spaces that it can attack. Then if you end up having to move the queen that you have already placed, due to no possible solutions with that placement, how would you remove the marks in the places it can attack? You wouldn't really know which to remove, because maybe multiple queens attack one square?

I would recommend only placing a queen in the array, and then if you have to come back and move it later on you can just remove the Q or 5 and replace it with - or 0. This should at least help fix your problem. Also, it would probably be easier to do this way. You could just write a method to check a given position to see if it is being attacked, and based on that result place the queen there or go on to the next spot.

Does this make sense? This is a rather tough problem and even tougher to put into written words that accurately say what you are trying to express.

If you are having trouble with understanding how to handle the situation where no open positions exist, look at the very end of the Wikipedia article. They have an animation showing the correct backtracking.

Hope this helps!
-Michael

This post has been edited by Mikeyp926: 04 May 2009 - 01:01 PM

Was This Post Helpful? 0
  • +
  • -

#10 virgul  Icon User is offline

  • D.I.C Regular

Reputation: 44
  • View blog
  • Posts: 269
  • Joined: 18-March 09

Re: little help with 8 queens

Posted 04 May 2009 - 09:46 PM

Mikeyp926 i used your suggestion for your program, works perfectly. now all i got to do is try to use your concepts in my friends program.
Was This Post Helpful? 0
  • +
  • -

#11 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon


Reputation: 6966
  • View blog
  • Posts: 14,572
  • Joined: 16-October 07

Re: little help with 8 queens

Posted 05 May 2009 - 06:43 AM

I had to post to this, because this little gem made my eyes cross:
board BOARD;
public subQueens(board Board) {
	BOARD = Board;
//...



Ouch. Be consistent, you'll thank yourself later. On to the problem...

The easiest way to do this is to just mark positions as unavailable as you go. Each time you place a queen, mark all the the positions that queen can attack as filled. Then just look at the still available slots for the next round.

I don't want to give it all away, but this amused me enough that I gave it a go. Here's my solution method:
Board solve(Board board, int queens) {
	if (queens<1) { return board; }
	for(Board.Pos pos : board.getAvailablePos()) {
		Board newBoard = new Board(board);
		newBoard.setQueen(pos);
		Board solved = solve(newBoard, queens-1);
		if (solved!=null) { return solved; }
	}
	return null;
}



If you can write a board class to offer those methods, you're there. Isn't OOP fun?

Hope this helps.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1