• Post Reply Bookmark Topic Watch Topic
  • New Topic

eight queens problem without backtracking  RSS feed

 
rahul adams
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello

I am doing problems from "Introduction to Java Programming" by Daniel Liang (10 ed.). There is this problem of eight queens on chess board. Now, this is a chapter on single dimensional arrays and author has not introduced any recursion discussion till this point. Eight queens problem is a special version of N queens problem with N=8. I emailed author and he said that the problem can be solved without using backtracking/recursion. All the approaches I have seen on the net use backtracking. I tried very hard to come up with solution but have not succeeded so far. Can anybody tell me any hints ?

Thanks
 
Les Morgan
Rancher
Posts: 779
19
C++ Java MySQL Database Netbeans IDE Oracle Tomcat Server
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You iterate through the entire board placing a Queen as can be done accordingly.  So you begin by checking placement of your queen at (0,0), by iterating through all squares to see if there is another queen that would make (0, 0) illegal. There is not so you place it. Now you check(0, 1)  for validity of your second queen by iterating through all of the board again, (0, 1) fails for you retain your queen count and move on to (0, 2).... until you have completed your task.
 
rahul adams
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Les

So I will need to keep track of the forbidden positions on the board. Thats what I found hard to do. There might be a case where after filling 5 queens, all further positions are blocked. In that I will need to backtrack to the first queen and start all over again. So it seems to me that this problem can not be solved without backtracking. What do you think ?

thanks
 
Paul Clapham
Sheriff
Posts: 22844
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's a method which doesn't use backtracking: Put eight queens on the board randomly and see if it's a valid solution; repeat until you get a valid solution.
 
Les Morgan
Rancher
Posts: 779
19
C++ Java MySQL Database Netbeans IDE Oracle Tomcat Server
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I do not agree. Using backtracking in recursion is much different than iterative methods.  What you are looking for is an A* iterative method. If you do not get a valid answer and have to throw out your board and start with (01), then that is an iterative method, there is no backtracking used.
 
Les Morgan
Rancher
Posts: 779
19
C++ Java MySQL Database Netbeans IDE Oracle Tomcat Server
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Back in the day that I was doing my CS BA, I took a graduate course in AI, we were asked by the instructor for volunteers so he could study problem solving methods in the humans, the 8 Queens problem was one he used to see how we would set it up. My thought was if I place with a knight style of patter, I would have the most success.  It was a novel thought and we didn't have to implement, he wanted to see how we would approach the problem.

With backtracking you are literally reversing through the layers of recursion back to see if you can find a solution from the previous level... In recursion you may go all the way through and hit 7 Queens on the board, then you cannot place the 8th, so you backtrack to when you had seven, if you fail there you back track to when you had 6, and if you fail there you backtrack to where you had 5. At each level backtracked you try alternate placements to see if you can find an over all solution to the problem.

When you do something iteratively there is no back track, you start over, and seek a different start, then continue.  When you have exhausted your options, then you try a different placement algorithm, but the idea is to iteratively go through an A* algorithm--British Museum--and take the first solution; thus, clipping the rest of the attempts, or alternatively, you save that one and continue with your A* iteration.
 
rahul adams
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Paul, your approach is nice but may take long time I guess since we are using randomness here. Les, I see your point. Now the difficult part is to figure out how to identify the forbidden positions as we move on with the queens. Any ideas on it ?
 
Les Morgan
Rancher
Posts: 779
19
C++ Java MySQL Database Netbeans IDE Oracle Tomcat Server
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I would calculate each position for validity as you test placement, I would also make an 8x8 grid or array to be able to logically reference and use a simple placement counter to see when 8 have been placed.

Remember to reset everything between generations.
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

In my opinion, this is actually a classic case of a recursive method simplifying an iterative method. To do one queen, you will need two nested loops (assuming one for horizontal and one for vertical). And to do eight queens, you will need 16 nested loops.

So, yes, iterative is possible (to reach all combinations). And yes, you can optimize it down to eight nested loops. And furthermore, yes, with randoms, or some math technique mentioned later, you can get it down to one nested loop.... but... why? Recursion works best here.

Anyway, you can also have a mathematical representation to define the state. Say, each queen needs 6 bits of data, since each queen can be in 64 possible positions. With 8 queens, that is 48 bits of data. So, you can loop through a 48 bit number to find a valid state. With this algorithm, you also need to check to see if any queens are in the same square too, to avoid that invalid case.

Henry
 
Ryan McGuire
Ranch Hand
Posts: 1143
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I can think of a hokey way to do with no backtracking. 

Use 8 nested loops from 0 to 63 to represent the position of each queen.



Or does using a loop count as backtracking?

[EDIT] Now that I reread some of the previous comments, I think this is a lot like what others had in mind.  Maybe.
 
Knute Snortum
Sheriff
Posts: 4288
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You shouldn't post a complete solution in BJ until the OP has.
 
Ryan McGuire
Ranch Hand
Posts: 1143
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Knute Snortum wrote:You shouldn't post a complete solution in BJ until the OP has.


I wouldn't call this complete, but point taken.  Unfortunately, the option to edit or delete is no longer available.
 
Paul Clapham
Sheriff
Posts: 22844
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
rahul adams wrote:Paul, your approach is nice but may take long time I guess since we are using randomness here.


Your original post didn't mention anything about finding effective or efficient solutions, it only asked about solutions which didn't require recursion or backtracking.

But you may be right, although guesswork is not a good strategy for evaluating the speed of some code. You might find that a well-designed random algorithm is faster than you think.
 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The solutions here are avoiding recursion, but whether or not it avoids "backtracking" is up for interpretation. Even a many-level nested set of loops implements a form of backtracking. So, with this poetic license in mind I would propose keeping a stack of row/col positions as you test each one and decide if the next push should increment the column by one, or increment the row by one and reset the column back to zero. Of course if you reach the last column for the current row you'd have to start popping the stack to get back to a prior state. This can be done with a single loop that continues as long as the stack size is less than eight.
 
rahul adams
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks all.  I think I got sufficient feedback on the ideas for solution. I will think along these lines and try to come up with the solution.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!