Win a copy of Beginning Java 17 Fundamentals: Object-Oriented Programming in Java 17 this week in the Java in General forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Tim Cooke
• Campbell Ritchie
• Ron McLeod
• Liutauras Vilda
• Jeanne Boyarsky
Sheriffs:
• Junilu Lacar
• Rob Spoor
• Paul Clapham
Saloon Keepers:
• Tim Holloway
• Tim Moores
• Jesse Silverman
• Stephan van Hulst
• Carey Brown
Bartenders:
• Al Hobbs
• Piet Souris
• Frits Walraven

# eight queens problem without backtracking

Greenhorn
Posts: 7
• Number of slices to send:
Optional 'thank-you' note:
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

Rancher
Posts: 1012
27
• Number of slices to send:
Optional 'thank-you' note:
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.

Greenhorn
Posts: 7
• Number of slices to send:
Optional 'thank-you' note:
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

Sheriff
Posts: 26966
84
• Number of slices to send:
Optional 'thank-you' note:
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: 1012
27
• Number of slices to send:
Optional 'thank-you' note:
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: 1012
27
• Number of slices to send:
Optional 'thank-you' note:
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.

Greenhorn
Posts: 7
• Number of slices to send:
Optional 'thank-you' note:
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: 1012
27
• Number of slices to send:
Optional 'thank-you' note:
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.

author
Posts: 23912
142
• 1
• Number of slices to send:
Optional 'thank-you' note:

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

Bartender
Posts: 1205
22
• Number of slices to send:
Optional 'thank-you' note:
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.

Sheriff
Posts: 7113
184
• Number of slices to send:
Optional 'thank-you' note:
You shouldn't post a complete solution in BJ until the OP has.

Ryan McGuire
Bartender
Posts: 1205
22
• Number of slices to send:
Optional 'thank-you' note:

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: 26966
84
• Number of slices to send:
Optional 'thank-you' note:

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.

Saloon Keeper
Posts: 8943
76
• Number of slices to send:
Optional 'thank-you' note:
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.