An attempt on 8 Queens Problem (Ramkumar Menon's Blog)

An attempt on 8 Queens Problem

By Ramkumar Menon on June 30, 2008 11:07 PM

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 + ")";
}

}

Tags:

Permalink

Ramkumar Menon's Blog

Principal Consultant