An attempt on 8 Queens Problem

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;
matchedList.add(cellValue);
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 + ")";
}

}

Comments:

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,

Posted by Mscwsldv on August 08, 2008 at 01:09 PM PDT #

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.

Posted by Ramu on September 26, 2008 at 06:15 PM PDT #

Hey Ram, glad to see your orablog. 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)

Posted by Abdul Bijur Vallarkodath on October 11, 2008 at 09:02 PM PDT #

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

Posted by Jim Hathaway on December 22, 2008 at 01:03 PM PST #

Probably Sanchez was purely jealous the War Criminals within the administration didn't call him "indispensible". That particular rejection most likely will hurt.

Posted by Bethanie Lenius on October 03, 2010 at 04:00 AM PDT #

I must say that is a really nice article, I already knew all this, but never thought about writing about it hehe

Posted by Marjory Smiling on October 07, 2010 at 05:13 PM PDT #

Courteney cox is fab i think she is a great actress and that i wish her all the very best in her furture life

Posted by Arletta Castillion on October 19, 2010 at 05:50 AM PDT #

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!

Posted by Kelly the Bulldog Expert on October 21, 2010 at 11:24 PM PDT #

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.

Posted by Anjanette Lamirande on November 05, 2010 at 07:39 AM PDT #

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.

Posted by Kai Bribiesca on December 02, 2010 at 02:28 AM PST #

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.

Posted by Basil on April 26, 2011 at 07:34 AM PDT #

Are you able to provide more info about this? Thanks

Posted by free insurance car quotes on April 26, 2011 at 08:16 PM PDT #

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.

Posted by kalibracja telewizji on April 26, 2011 at 08:28 PM PDT #

finding an it support provider could be a real mine field, I indicate asking any companies you think about for references from happy clients

Posted by wgv versicherung on April 26, 2011 at 08:28 PM PDT #

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?

Posted by kopfschmerzen hausmittel on April 26, 2011 at 08:29 PM PDT #

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.

Posted by filme gratis downloaden on April 26, 2011 at 08:30 PM PDT #

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?

Posted by drip feed blast on April 27, 2011 at 08:05 PM PDT #

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!

Posted by craigslist posting software on April 27, 2011 at 09:25 PM PDT #

I am having 404 pages actually regularly, I’m not too sure why nevertheless if I refresh the website it returns alright.

Posted by Bubble Shooter Games on April 27, 2011 at 11:17 PM PDT #

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?

Posted by Mario Games on April 28, 2011 at 01:07 AM PDT #

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.

Posted by casino online on April 28, 2011 at 03:25 AM PDT #

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

Posted by online casino on April 28, 2011 at 03:37 PM PDT #

Its good to read this blog.Thanks for sharing it.

Posted by best cash isas on April 29, 2011 at 05:36 AM PDT #

Post a Comment:
  • HTML Syntax: NOT allowed
About

Principal Product Manager

Search

Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today