# An attempt on 8 Queens Problem

Director, Product Strategy

I was trying out a different approach to 8-Queen's problem. I visualized each cell [that has a coordinate from (0,0) to (7,7) as a single number 10x + y. So you would have sort of an octal number set from 0 to 77. Each column would be 0-7, 10-17, 20-27 etc and so on till 70-77.

Each row would be 0-70, 1 to 71 etc, in increments of 10.

7 17 27 37 47 57 67 77

6 16 26 36 46 56 66 76

5 15 25 35 45 55 65 75

4 14 24 34 44 54 64 74

3 13 23 33 43 53 63 73

2 12 22 32 42 52 62 72

1 11 21 31 41 51 61 71

0 10 20 30 40 50 60 70

The solution was a recursive function that takes in a current column index [ranging from 0 to 7], and computing the matching lists of size 8, after applying an exclusion rule.

The exclusion rule is interesting.

For an item with value, lets say 43, the exclusion rule would test the row-wise, columnwise and diagonal collisions through a simple modulo-checking logic. The code is given below. Note that the code has not been subjected to any review, including self-review, though it generates the required 92 distinct permutations as the 8Q solution demands.

package equeen;

import java.io.FileWriter;

import java.util.ArrayList;

import java.util.List;

import java.util.Stack;

public class EightQueens {

public boolean computeMatches(int rowIndex, List matchedList) throws Exception{

if(matchedList.size() == 8) {

printToFile(matchedList);

}

boolean matched = false;

for(int i = 10*rowIndex ; i <= 10*rowIndex + 7 ; i++) {

int cellValue = i;

boolean isExcluded = computeExclusionRule(cellValue, matchedList);

if(!isExcluded) {

matched = true;

if(computeMatches(rowIndex+1,matchedList)) matched = !matched;

}

}

if(!matched && matchedList.size() > 0) {

matchedList.remove(matchedList.size() - 1);

return true;

}

else return false;

}

private boolean computeExclusionRule(int value, List matchedList) {

for(int i = 0 ; i < matchedList.size() ; i++) {

int prevNumber = Integer.parseInt("" + matchedList.get(i));

int diff = (value - prevNumber);

if((diff % 9 == 0 && (prevNumber % 10 > value % 10)) ||

(diff % 10 == 0) ||

(diff % 11 == 0 && (prevNumber % 10 < value % 10))) {

return true;

}

}

return false;

}

public static void main(String[] args) throws Exception {

EightQueens q = new EightQueens();

List emptyList = new ArrayList();

int ZEROTHCOLUMN_INDEX = 0;

long t = System.currentTimeMillis();

q.computeMatches(ZEROTHCOLUMN_INDEX,emptyList);

System.err.println("Number of ms for execution - " + (System.currentTimeMillis() - t));

}

private static FileWriter fw = null;

private static void printToFile(List matchedList) throws Exception {

if(fw == null) {

fw = new FileWriter("d:\\temp\\results.log");

}

String str = "";

for(int i = 0 ; i < matchedList.size() ; i++) {

int itemValue = Integer.parseInt("" + matchedList.get(i));

str += getCoords(itemValue) + " ";

}

fw.write(str + "\r\n");

fw.flush();

}

private static String getCoords(int cellValue) {

int x = cellValue/10;

int y = cellValue % 10;

return "(" + x + "," + y + ")";

}

}

#### Join the discussion

• dfgdzf Wednesday, August 6, 2008
• Mscwsldv Friday, August 8, 2008
tDeegS comment4, kinney drug auto door handle, http://www.donorione.it/img/glyph/2/blog.php?p=15576#1 kinney drug auto door handle, 307, andreas auto cheat code grand san theft, http://www.pr-jozef.com/brisi/8/blog.php?p=8567#1 andreas auto cheat code grand san theft, 2280, sst auto loans, http://www.memoimpex.co.yu/jomla/media/8/blog.php?p=3654#1 sst auto loans, gaam, hans auto parts elk river, http://www.sonbarbassa.com/galeria/7/blog.php?p=22991#1 hans auto parts elk river, 8-], auto restoration school, http://www.cofitalia.it/francese/solarr/3/blog.php?p=1428#1 auto restoration school, 913,
• fghdf Saturday, August 9, 2008
• Ramu Saturday, September 27, 2008
Hi,
I happened to see this logic, when one prospective recruit copied this code as his own!
Interesting with the encoded cell number. But on the first impression the 'exclusion rule' may not be computationally simpler or better than plain checks, especially if you consider that a queen position does not need co-ordinates (x and y), but just col is enough as there should be one in each row.
• Abdul Bijur Vallarkodath Sunday, October 12, 2008
I was asked this exact same question during my interview for Oracle during my S7 campus placements and this is what i told him.
when you are doing a brute force search to place the next queen in the search criteria, what is pretty obvious to us is that we cannot place this queen in the same row and same column of any of the queens that are already on board. Now what remains is the diagonals which can go anyway. (i1 = i2 and j1 = j2).
So what do we do about the diagonal power of the queens, now what we do is, call a function which will check whether the principal diagonal elements of the minor matrix formed by that element has any of the previous queens. (The classic i1 = j1 or i2 = j2). This should be fairly simple to implement with a function doing everything for you.
Again, "if there are many solutions to a single problem, the simplest one is the best solution" and hence at any point comparing any (i,j) using i1 = i2 or j1 = j2 and i1+j1 = i2+j2 for the entire solution is hugely simpler than either mine or yours.
Cheers,
Abdul
p.s. We should catch us sometimes, its been a long time. (abdulbijur@gtalk/aim/hotmail)
• Jim Hathaway Monday, December 22, 2008
Hello,
I would like to share the following site:
Eight Queens solution using GWT
I have used the Java code from this blog entry and incorporated it into a web site using the Google Web Toolkit to display the solutions. The site also tracks the amount of time each browser takes to calculate the Eight Queens Solution.
See my Blog entry here
Thanks,
Jim
• Bethanie Lenius Sunday, October 3, 2010
Probably Sanchez was purely jealous the War Criminals within the administration didn't call him "indispensible". That particular rejection most likely will hurt.
• Marjory Smiling Friday, October 8, 2010
I must say that is a really nice article, I already knew all this, but never thought about writing about it hehe
• Arletta Castillion Tuesday, October 19, 2010
Courteney cox is fab i think she is a great actress and that i wish her all the very best in her furture life
• Kelly the Bulldog Expert Friday, October 22, 2010
I have enjoyed your article points. My study has shown your points to be true, however I have also seen the opposite from other articles like this one. Do you have any recommendations for getting more quality ideas on dog training or related topics? I would certainly appreciate it!
• Anjanette Lamirande Friday, November 5, 2010
I was giving her bread cut into small pieces, diced fruit, finely chopped chicken breast, frozen peas and carrots (had to cut the carrots down a little), shredded cheese, cheerios, sometimes a whole wheat fig newton cut into little pieces, puffed kashi cereal, gee- anything really. Sometimes fruit is slippery and they can't pick it up yet but I would spoon feed it to her and she loved it. Now she's 10 mo and I have pretty much stopped buying jars, unless I need them for convenience.
• Kai Bribiesca Thursday, December 2, 2010
i think that Kate Winslet is cute, and has a pleasant shape. she made my heart break on Titanic, and i cried, would you consider i watch that present 21 times, due to Kate and Leonardo.
• Basil Tuesday, April 26, 2011
Great goods from you, man. I've understand your stuff previous to and you're just too magnificent. I actually like what you have acquired here, really like what you're saying and the way in which you say it. You make it entertaining and you still take care of to keep it wise. I can't wait to read much more from you. This is actually a wonderful website.
• free insurance car quotes Wednesday, April 27, 2011
• kalibracja telewizji Wednesday, April 27, 2011
Did you ever thought about adding a little bit more your thoughts? I suggest, what you write is important and everything. But its no punch, no pop! Maybe if you had given a pic or two, a video? You might have such a powerful blog if you let people see what you are talking about instead of reading it only.
• wgv versicherung Wednesday, April 27, 2011
finding an it support provider could be a real mine field, I indicate asking any companies you think about for references from happy clients
• kopfschmerzen hausmittel Wednesday, April 27, 2011
Great post. Always keep more interesting publications. Been following your blog for Three days now and I should say I am beginning to much like your post. I need to know how do I subscribeto your site?
Dear Guru, what entice you to post an article. This article was extremely interesting, especially since I was trying to find thoughts on this subject last Thursday.
• drip feed blast Thursday, April 28, 2011
I truly prefer your blog and i really value the superb quality content you are submitting right here for no cost for your online audience. Can you tell us which weblog platform you are employing?
• craigslist posting software Thursday, April 28, 2011
I know this is off topic but I wanna share this peice of data with everyone I can; do not imagine in psychics! I perceive it appears insane but my heart was broken nowadays as one tried to bring back again reminiscences of a lost adore one. He was so convincing it's disgusting! They are scammers! Anyway stellar site, but much more written content please!
• Bubble Shooter Games Thursday, April 28, 2011
I am having 404 pages actually regularly, I’m not too sure why nevertheless if I refresh the website it returns alright.
• Mario Games Thursday, April 28, 2011
I genuinely prefer your weblog and i seriously respect the fantastic quality written content you are submitting here for free for your online viewers. Can you inform us which blog platform you are utilizing?
• casino online Thursday, April 28, 2011
I employed to be questioning if you may enjoy to be a customer poster on my web site? and in trade you may embody a hyperlink your post? Satisfy reply once you get an opportunity and I will deliver you my get in touch with particulars - thanks. In any case, in my language, there aren't significantly excellent obtain prefer it.
• online casino Thursday, April 28, 2011
Hi. I wished to shed you a speedy phrase to express my thanks. Ive been following your blog for a month or two or so and possess captured a ton of great details and loved the proceedure youve organized your site. I am attempting to run my really own weblog nonetheless I really feel its too normal and I need to give attention to a number of smaller topics. Being all things to all people is just not all that its cracked until be
• best cash isas Friday, April 29, 2011
Its good to read this blog.Thanks for sharing it.