LCM |
| Once I have the prime number generator, my first usage will be for LCM calculation. I just converted the way I used to find LCM in my school days into java code. Enjoyed a lot sloving this cute puzzle. Validated the results from my code @ http://www.solvemymath.com/online_math_calculator/general_math/least_common_multiple/lcm_calculator.php |
import blog.prime.IntPrimeGenerator;
import java.math.BigInteger;
import java.util.Random;
import java.util.Stack;
public class LCM {
private int[] list;
private Stack<Integer> resultStack;
private int allset;
private int prime;
private final PrimeGenerator<Integer> |
Thursday, July 14, 2011
LCM
Monday, June 20, 2011
Fun with Prime numbers
Fun with prime numbers |
| When I am trying to understand the importance of prime numbers, I am really surprised to know that prime numbers have influance not in just mathamatics and computer science but has influance on nature too. Periodical cicadas, Magicicada species, such as the 17-year and 13-year "locusts," are the longest-lived cicadas. They emerge during synchronized periods, often in spectacular numbers, every 17th or 13th year, respectively. More details refer: Cicadas and Magicicada .If you observe 13 and 17 both are prime numbers. Glenn Webb : A mathamatician found that periodical cicadas have prime number life cycles to avoid syncronization from predators. If cicadas reprductive cycles are not follwed prime and lets think it as 12 years and if predators reproduce at 4 then predators will get complete feast as both lifecycles are syncronized. For more details please refer : http://philosci40.unibe.ch/lehre/winter06/wtwg_bio/webb01.pdf Prime numbers have great infulance on hashing and cryptography. |
package blog.prime; import java.util.List; public interface PrimeGenerator<T extends Number> { // Return prime numbers between 'from' to 'upto' public List<T> getPrimeNumbersUpto(int from, int upto); // Return prime numbers between 0 to 'upto' public List<T> getPrimeNumbersUpto(int upto); // Returns fixed size of primes numbers from 0 public List<T> getPrimeNumbersSet(int size); // Returns fixed size of primes numbers from int public List<T> getPrimeNumbersSet(int from, int size); //Get near prime public T getNextProbablePrime(T val); //Get previous prime public T getPreProbablePrime(T val); // To checks for prime public boolean isPrime(T val); // Returns next prime near to val } package blog.prime; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.concurrent.CopyOnWriteArrayList; import java.util.concurrent.locks.Lock; import java.util.concurrent.locks.ReentrantLock; @ThreadSafe public enum IntPrimeGenerator implements PrimeGenerator<Integer> { integerSingletonPrime; private final int CACHE_INI_SIZE = 5000; private List<Integer> primeCache; private final Lock lock; private IntPrimeGenerator() { lock = new ReentrantLock(); primeCache = Collections.unmodifiableList (getPrimeNumbersSet(0,CACHE_INI_SIZE)); } @Override public List<Integer> getPrimeNumbersUpto(int from, int upto) { if(from < upto) throw new IllegalStateException("'from' cann't be greater than 'upto'"); int maxCachePrime = primeCache.get(CACHE_INI_SIZE); if(upto == maxCachePrime) return primeCache; if(upto < maxCachePrime) return primeCache.subList( primeCache.lastIndexOf(findNextNearPrime(from)), primeCache.lastIndexOf(findPreNearPrime(upto))); if(upto > maxCachePrime && from < maxCachePrime) return getList( primeCache.size(), upto, primeCache.subList( primeCache.lastIndexOf(findNextNearPrime(from)), upto)); else return getList(from, upto); } @Override public List<Integer> getPrimeNumbersUpto(int to) { return getPrimeNumbersUpto(2,to); } @Override public List<Integer> getPrimeNumbersSet(int size) { if(size <= CACHE_INI_SIZE) return primeCache.subList(0, size); else throw new IllegalStateException( "IntegerPrime doen't support more than "+CACHE_INI_SIZE+"size"); } @Override @jdk7("Coin : Improved type inference for generic instance creation (diamond)") public List<Integer> getPrimeNumbersSet(int from, int size) { lock.lock(); try { List<Integer> primes; if(primeCache == null) { primeCache = new CopyOnWriteArrayList<>(); primes = primeCache; } else { primes = new CopyOnWriteArrayList<>(); } while(primes.size() != size) { if(isPrime(from)) primes.add(from); from++; } return primes; } finally { lock.unlock(); } } @Override public boolean isPrime(Integer value) { int val = value.intValue(); if(val == 1) return false; if(val == 2 || val == 3) return true; //Ignore even numbers if((val & 0b0001) == 0) return false; //Search in cache. if(primeCache.contains(val)) return true; if(primeCache.get(primeCache.size()-1) > val) return false; int flag=1;
for(int i=2; i<=Math.sqrt(val); i++) {
if(primeCache.size() > i) {
if(val%primeCache.get(flag++) == 0) return false;
} else {
if(val%i == 0) return false;
}
}
return true;
}
private Integer findNextNearPrime(Integer val) {
while(true)
if(isPrime(++val)) return val;
}
private Integer findPreNearPrime(Integer val) {
while(true)
if(isPrime(--val)) return val;
}
private List<Integer> getList(int from, int upto) {
return getList(from, upto, new ArrayList<Integer>());
}
private List<Integer> getList(int from, int upto, List<Integer> primeList) {
for(int i=from;i<=upto; i++)
if(isPrime(i)) primeList.add(i);
return primeList;
}
private int getNearInBasePrime(int val) {
if(val > primeCache.get(CACHE_INI_SIZE-1))
throw new IllegalStateException("Value is out of scope");
int left = 0, right = CACHE_INI_SIZE, mid=0;
while(left != right-1) {
mid = (left + right) >> 1;
if(primeCache.get(mid) > val) right = mid;
else left = mid;
}
return left;
}
public Integer getNextProbablePrime(Integer value) {
int val = value.intValue();
if(val < 2) return 2;
if(primeCache.get(CACHE_INI_SIZE-1) > val) {
int left = getNearInBasePrime(val);
if(left != CACHE_INI_SIZE)
return primeCache.get( left + 1);
}
return findNextNearPrime(val);
}
public Integer getPreProbablePrime(Integer value) { int val = value.intValue(); if(val <= 2) throw new IllegalStateException("Not possible"); if(primeCache.get(CACHE_INI_SIZE-1) > val) { if(!primeCache.contains(val)) { int left = getNearInBasePrime(val); if(left != 0) return primeCache.get(left); } } return findPreNearPrime(val); } } @interface ThreadSafe { } @interface jdk7 { String value(); } |
Monday, May 16, 2011
JDK7 NIO.2 Change
JDK7 NIO.2 API change |
| My initial blog code ShuffelMP3 and AstuteSync will not work as some of JDK7 NIO.2 methods are refactored. The copy and exists methods have been moved to Files. I have updated my code and added some of JDK7 coin features. RED colored statement for recent NIO.2 JDK chnages. |
========= ShuffleMP3 ================== package javatrails; import java.io.IOException; import java.nio.file.*; import java.nio.file.attribute.*; import java.util.UUID; import static java.nio.file.StandardCopyOption.*; public class ShuffleMp3 { private static final String SOURCE = "/home/dhanvi/TEMP"; private static final String TARGET = "/home/dhanvi/TEST"; private static void copyThisFile(Path file) { try { Path targetPath = Paths.get(TARGET + System.getProperty("file.separator") + UUID.randomUUID().toString().replaceAll("-", "") + ".mp3"); Files.copy(file,targetPath, REPLACE_EXISTING); System.out.println("Copied " + file.toString() + " to " + targetPath.toString()); } catch (IOException | Exception ex) { ex.printStackTrace(); } } static class Mp3FileVisitor extends SimpleFileVisitor<Path> { @Override public FileVisitResult visitFile(Path file, BasicFileAttributes attrs) { if (file.toString().lastIndexOf(".mp3") >= 0 || file.toString().lastIndexOf(".MP3") >= 0) copyThisFile(file); return FileVisitResult.CONTINUE; } } public static void main(String... arg) { try { final Path path = Paths.get(SOURCE); if(!Files.exists(path)) throw new IllegalStateException("Sorry file doen't exists"); Files.walkFileTree(path, new Mp3FileVisitor()); } catch (@jdk7("Coin : Multi-catch and more precise rethrow") final IOException | IllegalStateException ex) { ex.printStackTrace(); } } } ========= AstuteSync ================== package javatrails; import java.io.IOException; import java.nio.file.*; import java.nio.file.attribute.*; import java.util.*; import java.util.Map.Entry; import java.util.concurrent.ConcurrentSkipListMap; import java.util.concurrent.locks.*; import static java.nio.file.FileVisitResult.*; import static java.nio.file.StandardCopyOption.*; import java.util.logging.Level; import java.util.logging.Logger; public class AstuteSync { private final static Lock lock = new ReentrantLock(); @jdk7("Coin : Improved type inference for generic instance creation (diamond)") private final Map<String,String> diffList = new ConcurrentSkipListMap<>(); private class SyncFileVisitor extends SimpleFileVisitor<Path> { private String head; public SyncFileVisitor(String head) { this.head = head.endsWith(System.getProperty("file.separator")) ? head.substring(0,head.length()-1) : head; } @Override public FileVisitResult preVisitDirectory(Path dir, BasicFileAttributes attrs) { toList(dir); return CONTINUE; } @Override public FileVisitResult visitFile(Path file, BasicFileAttributes attrs) { toList(file); return CONTINUE; } private void toList(Path file) { lock.lock(); try { if (diffList.remove(file.toString().replace(head, "")) == null) diffList.put(file.toString().replace(head, ""), file.toString()); } finally { lock.unlock(); } } } private void printDiffList() { if(diffList.isEmpty()) System.out.println("Both folders are in Sync."); else { System.out.println("Folder Diff:"); for(String s : diffList.values()) System.out.println(s); } } private void sync(final Path source, final Path target) { Set<Entry<String, String>> entries = diffList.entrySet(); for(Map.Entry<String,String> entry : entries) { try { Path tmpSource = Paths.get(entry.getValue()); Path tmpTarget = Paths.get( (entry.getValue().startsWith(target.toString()) ? source.toString() : target.toString()) + System.getProperty("file.separator") + entry.getKey()); Files.copy(tmpSource, tmpTarget, COPY_ATTRIBUTES); } catch (Exception ex) {ex.printStackTrace();} } } public void startSync(final String SOURCE, final String TARGET) { final Path source = Paths.get(SOURCE); final Path target = Paths.get(TARGET); if(!Files.exists(source) || !Files.exists(target)) throw new IllegalStateException("Sorry file doen't exists"); new Thread(new Runnable() {public void run() { try { Files.walkFileTree(source, new SyncFileVisitor(SOURCE)); } catch (IOException ex) { Logger.getLogger(AstuteSync.class.getName()).log(Level.SEVERE, null, ex); } }}).start(); new Thread(new Runnable() {public void run() { try { Files.walkFileTree(target, new SyncFileVisitor(TARGET)); } catch (IOException ex) { Logger.getLogger(AstuteSync.class.getName()).log(Level.SEVERE, null, ex); } }}).start(); Runtime.getRuntime().addShutdownHook(new Thread() { @Override public void run() { printDiffList(); if(!diffList.isEmpty()) sync(source, target); } }); } public static void main(String... arg) { new AstuteSync().startSync("/home/dhanvi/TEMP", "/home/dhanvi/TEST"); } } @interface jdk7 { String value(); } |
Thursday, March 10, 2011
Eight Queens - 2
I have tested my code with different board sizes and it is throwing the correct number of solutions :). When I started thinking of optimization. First thing came in mind was set of strings used for tracking blocked cells. Instead of having different heavy data structure, we can use the same board with different numeric for blocked cell. I have used '-1' for the same. |
import java.util.Set; import java.util.TreeSet; public class Chess8Queens { private static final int BOARD_SIZE = 8; private static final int[][] chessBoard = new int[BOARD_SIZE][BOARD_SIZE]; private static final Set<String> result = new TreeSet<String>(); static { for(int i=0; i < BOARD_SIZE; i++) for(int j=0; j < BOARD_SIZE; j++) chessBoard[i][j] = 0; } private static void printBoard(boolean isSuccess) { StringBuffer sb = new StringBuffer(); for (int i = 0; i < BOARD_SIZE; i++) { for (int j = 0; j < BOARD_SIZE; j++) { System.out.print(chessBoard[i][j] == -1 ? "* " : chessBoard[i][j] + " "); if(chessBoard[i][j] > 0 && isSuccess) sb.append(j).append("|"); } System.out.println(""); } if(isSuccess) result.add(sb.toString()); sb = null; System.out.println("Done :" + result.size()); } private static void updateBlockedSet(int row, int col, boolean isAdd) { int flag1 = 0, flag2 = 0; if (col > row) { flag1 = col - row; flag2 = col + row; for (int i = 0; i < BOARD_SIZE; i++) { if (col < BOARD_SIZE) chessBoard[i][col] = isAdd ? -1 : 0; if (row < BOARD_SIZE && col < BOARD_SIZE) chessBoard[row][i] = isAdd ? -1 : 0; if ((flag1 + i) < BOARD_SIZE) chessBoard[i][flag1+i] = isAdd ? -1 : 0; if ((flag2 - i) >= 0 && (flag2 - i) < BOARD_SIZE) chessBoard[i][flag2-i] = isAdd ? -1 : 0; } } else if (col < row) { flag1 = row - col; flag2 = col + row; for (int i = 0; i < BOARD_SIZE; i++) { if (col < BOARD_SIZE) chessBoard[i][col] = isAdd ? -1 : 0; if (row < BOARD_SIZE) chessBoard[row][i] = isAdd ? -1 : 0; if ((flag1 + i) < BOARD_SIZE) chessBoard[flag1+i][i] = isAdd ? -1 : 0; if ((flag2 - i) >= 0 && (flag2 - i) < BOARD_SIZE) chessBoard[flag2-i][i] = isAdd ? -1 : 0; } } else { for (int i = 0; i < BOARD_SIZE; i++) { flag1 = col > (BOARD_SIZE/2) ? (BOARD_SIZE-1)-col : col; flag2 = col + flag1; flag1 = col - flag1; chessBoard[i][col] = isAdd ? -1 : 0; chessBoard[row][i] = isAdd ? -1 : 0; chessBoard[i][i] = isAdd ? -1 : 0; if((flag2-i) >= 0 && (flag2-i) < BOARD_SIZE && (flag1 + i) >= 0 && (flag1 + i) < BOARD_SIZE) chessBoard[flag2-i][flag1+i] = isAdd ? -1 : 0; } } } private static void adjustBadPosition(int row) { if(row < 0) return; int tempj=0; boolean changed = false; for(int j= 0; j < BOARD_SIZE; j++ ) if(chessBoard[row][j] > 0) { chessBoard[row][j] = 0; tempj = j; changed = true; break; } if(changed) { for(int j=tempj+1; j<BOARD_SIZE; j++) chessBoard[row][j] = 0; for(int i=row+1; i<BOARD_SIZE; i++) for(int j= 0; j<BOARD_SIZE; j++ ) chessBoard[i][j] = 0; resetUpdateList(); chessBoard[row][tempj] = -1; } } private static void resetUpdateList() { for(int i=0; i<BOARD_SIZE; i++) for(int j= 0; j<BOARD_SIZE; j++ ) if(chessBoard[i][j] > 0 ) { int temp = chessBoard[i][j]; updateBlockedSet(i,j,true); chessBoard[i][j] = temp; } } public static Set<String> getPositions() { if(result.isEmpty()) { for( int row = 0; row < BOARD_SIZE; row++) { if(row < 0) break; for(int col = 0; col< BOARD_SIZE; col++) { if(chessBoard[row][col] == 0) { updateBlockedSet(row,col,true); chessBoard[row][col] = row+1; break; } else if(col == (BOARD_SIZE-1)){ adjustBadPosition(row-1); row = row - 2; break; } } if(row == (BOARD_SIZE-1)) { printBoard(true); adjustBadPosition(row); row--; } } } return result; } public static void main(String... arg) { for(String s: getPositions()) System.out.println(s); System.out.println(getPositions().size()); } } |
The output differ slightly from previous as 'B' is getting mixed with 8. I am printing *. * * * * * * * 1 * * * 2 * * * * 3 * * * * * * * * * 4 * * * * * * * * * * 5 * * * 6 * * * * * * * * * * * * 7 * * * * * 8 * * * Still lot of optimization can be done. Only 12 unique solutions are possible with 8 size board, instead of having many recursive loops, using simple mathematics rest 80 can be generated. |
Sunday, March 6, 2011
Eight Queens
Eight Queens problem :
The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that none of them can capture any other using the standard chess queen's moves.
I really enjoyed solving Eight queens problem manually as well as programatically.
Initially my code was returning 98. I literally diged a mountain to find the small rat (A small condition issue was throwing extra 6 wrong combination). Now I am getting unique 92 combination :).
Thank you very much 'Ranga Vure' for pointing out the issue.
import java.util.Set;
import java.util.TreeSet;
public class Chess8Queens {
private static final int chessBoard[][] = {{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0}};
private static final Set<String> blockedList = new TreeSet<String>();
private static final Set<String> result = new TreeSet<String>();
private static void printBoard(boolean isSuccess) {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
System.out.print(chessBoard[i][j] == 0 ?
blockedList.contains(i + "" + j) ? "B " : "O "
: chessBoard[i][j]+" ");
if(chessBoard[i][j] != 0 && isSuccess) sb.append(j).append("|");
}
System.out.println("");
}
if(isSuccess)
result.add(sb.toString());
sb = null;
System.out.println("Done :" + result.size());
}
private static void updateBlockedSet(int row, int col, boolean isAdd) {
int flag1 = 0, flag2 = 0;
boolean temp;
if (col > row) {
flag1 = col - row;
flag2 = col + row;
for (int i = 0; i < 8; i++) {
if (col < 8) {
temp = isAdd ? blockedList.add(i + "" + col + "")
: blockedList.remove(i + "" + col + "");
}
if (row < 8 && col < 8) {
temp = isAdd ? blockedList.add(row + "" + i + "")
: blockedList.remove(row + "" + i + "");
}
if ((flag1 + i) < 8) {
temp = isAdd ? blockedList.add(i + "" + (flag1 + i) + "")
: blockedList.remove(i + "" + (flag1 + i) + "");
}
if ((flag2 - i) < 8) {
temp = isAdd ? blockedList.add(i + "" + (flag2 - i) + "")
: blockedList.remove(i + "" + (flag2 - i) + "");
}
}
} else if (col < row) {
flag1 = row - col;
flag2 = col + row;
for (int i = 0; i < 8; i++) {
if (col < 8) {
temp = isAdd ? blockedList.add(i + "" + col + "")
: blockedList.remove(i + "" + col + "");
}
if (row < 8) {
temp = isAdd ? blockedList.add(row + "" + i + "")
: blockedList.remove(row + "" + i + "");
}
if ((flag1 + i) < 8) {
temp = isAdd ? blockedList.add((flag1 + i) + "" + (i) + "")
: blockedList.remove((flag1 + i) + "" + (i) + "");
}
if ((flag2 - i) < 8) {
temp = isAdd ? blockedList.add((flag2 - i) + "" + (i) + "")
: blockedList.remove((flag2 - i) + "" + (i) + "");
}
}
} else {
for (int i = 0; i < 8; i++) {
flag1 = col > 4 ? 7-col : col;
flag2 = col + flag1;
flag1 = col - flag1;
temp = isAdd ? blockedList.add(i + "" + col + "")
: blockedList.remove(i + "" + col + "");
temp = isAdd ? blockedList.add(row + "" + i + "")
: blockedList.remove(row + "" + i + "");
temp = isAdd ? blockedList.add(i + "" + i + "")
: blockedList.remove(i + "" + i + "");
if((flag2-i) >= 0 && (flag2-i) < 8 && (flag1 + i) >= 0 && (flag1 + i) < 8)
temp = isAdd ? blockedList.add((flag2-i) + "" + (flag1 + i))
: blockedList.remove((flag2-i) + "" + (flag1 + i));
}
}
}
private static boolean adjustBadPosition(int row) {
int tempj=0;
boolean changed = false;
for(int j= 0; j<8; j++ ) {
if(chessBoard[row][j] != 0) {
chessBoard[row][j] = 0;
tempj = j;
changed = true;
}
}
if(changed) {
for(int j=tempj+1; j<8; j++)
blockedList.remove(row+""+j);
for(int i=row+1; i<8; i++) {
for(int j= 0; j<8; j++ ) {
chessBoard[i][j] = 0;
blockedList.remove(i+""+j);
}
}
resetUpdateList();
blockedList.add(row+""+tempj);
return true;
}
return false;
}
private static void resetUpdateList() {
for(int i=0; i<8; i++) {
for(int j= 0; j<8; j++ ) {
if(chessBoard[i][j] != 0 ) {
updateBlockedSet(i,j,true);
}
}
}
}
public static Set<String> getPositions() {
if(result.isEmpty()) {
for( int row = 0; row < 8; row++) {
if(row < 0) break;
for(int col = 0; col< 8; col++) {
if(!blockedList.contains(row+""+col)) {
chessBoard[row][col] = row+1;
updateBlockedSet(row,col,true);
break;
} else if(col == 7){
adjustBadPosition(row-1);
row = row -2;
break;
}
}
if(row == 7) {
printBoard(true);
adjustBadPosition(row);
row--;
}
}
}
return result;
}
public static void main(String... arg) {
//System.out.println(result);
System.out.println(getPositions().size());
}
}
Sample output :
1 B B B B B B B
B B B B 2 B B B
B B B B B B B 3
B B B B B 4 B B
B B 5 B B B B B
B B B B B B 6 B
B 7 B B B B B B
B B B 8 B B B B
Done1
92 positions : I have listed only columns.
0|4|7|5|2|6|1|3| = 0,0 | 1,4| 2,7 | 3,5| 4,2| 5,6 | 6,1| 7,3 = Top Listed board
0|5|7|2|6|3|1|4|
0|6|3|5|7|1|4|2|
0|6|4|7|1|3|5|2|
1|3|5|7|2|0|6|4|
1|4|6|0|2|7|5|3|
1|4|6|3|0|7|5|2|
1|5|0|6|3|7|2|4|
1|5|7|2|0|3|6|4|
1|6|2|5|7|4|0|3|
1|6|4|7|0|3|5|2|
1|7|5|0|2|4|6|3|
2|0|6|4|7|1|3|5|
2|4|1|7|0|6|3|5|
2|4|1|7|5|3|6|0|
2|4|6|0|3|1|7|5|
2|4|7|3|0|6|1|5|
2|5|1|4|7|0|6|3|
2|5|1|6|0|3|7|4|
2|5|1|6|4|0|7|3|
2|5|3|0|7|4|6|1|
2|5|3|1|7|4|6|0|
2|5|7|0|3|6|4|1|
2|5|7|0|4|6|1|3|
2|5|7|1|3|0|6|4|
2|6|1|7|4|0|3|5|
2|6|1|7|5|3|0|4|
2|7|3|6|0|5|1|4|
3|0|4|7|1|6|2|5|
3|0|4|7|5|2|6|1|
3|1|4|7|5|0|2|6|
3|1|6|2|5|7|0|4|
3|1|6|2|5|7|4|0|
3|1|6|4|0|7|5|2|
3|1|7|4|6|0|2|5|
3|1|7|5|0|2|4|6|
3|5|0|4|1|7|2|6|
3|5|7|1|6|0|2|4|
3|5|7|2|0|6|4|1|
3|6|0|7|4|1|5|2|
3|6|2|7|1|4|0|5|
3|6|4|1|5|0|2|7|
3|6|4|2|0|5|7|1|
3|7|0|2|5|1|6|4|
3|7|0|4|6|1|5|2|
3|7|4|2|0|6|1|5|
4|0|3|5|7|1|6|2|
4|0|7|3|1|6|2|5|
4|0|7|5|2|6|1|3|
4|1|3|5|7|2|0|6|
4|1|3|6|2|7|5|0|
4|1|5|0|6|3|7|2|
4|1|7|0|3|6|2|5|
4|2|0|5|7|1|3|6|
4|2|0|6|1|7|5|3|
4|2|7|3|6|0|5|1|
4|6|0|2|7|5|3|1|
4|6|0|3|1|7|5|2|
4|6|1|3|7|0|2|5|
4|6|1|5|2|0|3|7|
4|6|1|5|2|0|7|3|
4|6|3|0|2|7|5|1|
4|7|3|0|2|5|1|6|
4|7|3|0|6|1|5|2|
5|0|4|1|7|2|6|3|
5|1|6|0|2|4|7|3|
5|1|6|0|3|7|4|2|
5|2|0|6|4|7|1|3|
5|2|0|7|3|1|6|4|
5|2|0|7|4|1|3|6|
5|2|4|6|0|3|1|7|
5|2|4|7|0|3|1|6|
5|2|6|1|3|7|0|4|
5|2|6|1|7|4|0|3|
5|2|6|3|0|7|1|4|
5|3|0|4|7|1|6|2|
5|3|1|7|4|6|0|2|
5|3|6|0|2|4|1|7|
5|3|6|0|7|1|4|2|
5|7|1|3|0|6|4|2|
6|0|2|7|5|3|1|4|
6|1|3|0|7|4|2|5|
6|1|5|2|0|3|7|4|
6|2|0|5|7|4|1|3|
6|2|7|1|4|0|5|3|
6|3|1|4|7|0|2|5|
6|3|1|7|5|0|2|4|
6|4|2|0|5|7|1|3|
7|1|3|0|6|4|2|5|
7|1|4|2|0|6|3|5|
7|2|0|5|1|4|6|3|
7|3|0|2|5|1|6|4|
The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that none of them can capture any other using the standard chess queen's moves.
I really enjoyed solving Eight queens problem manually as well as programatically.
Initially my code was returning 98. I literally diged a mountain to find the small rat (A small condition issue was throwing extra 6 wrong combination). Now I am getting unique 92 combination :).
Thank you very much 'Ranga Vure' for pointing out the issue.
import java.util.Set;
import java.util.TreeSet;
public class Chess8Queens {
private static final int chessBoard[][] = {{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0}};
private static final Set<String> blockedList = new TreeSet<String>();
private static final Set<String> result = new TreeSet<String>();
private static void printBoard(boolean isSuccess) {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
System.out.print(chessBoard[i][j] == 0 ?
blockedList.contains(i + "" + j) ? "B " : "O "
: chessBoard[i][j]+" ");
if(chessBoard[i][j] != 0 && isSuccess) sb.append(j).append("|");
}
System.out.println("");
}
if(isSuccess)
result.add(sb.toString());
sb = null;
System.out.println("Done :" + result.size());
}
private static void updateBlockedSet(int row, int col, boolean isAdd) {
int flag1 = 0, flag2 = 0;
boolean temp;
if (col > row) {
flag1 = col - row;
flag2 = col + row;
for (int i = 0; i < 8; i++) {
if (col < 8) {
temp = isAdd ? blockedList.add(i + "" + col + "")
: blockedList.remove(i + "" + col + "");
}
if (row < 8 && col < 8) {
temp = isAdd ? blockedList.add(row + "" + i + "")
: blockedList.remove(row + "" + i + "");
}
if ((flag1 + i) < 8) {
temp = isAdd ? blockedList.add(i + "" + (flag1 + i) + "")
: blockedList.remove(i + "" + (flag1 + i) + "");
}
if ((flag2 - i) < 8) {
temp = isAdd ? blockedList.add(i + "" + (flag2 - i) + "")
: blockedList.remove(i + "" + (flag2 - i) + "");
}
}
} else if (col < row) {
flag1 = row - col;
flag2 = col + row;
for (int i = 0; i < 8; i++) {
if (col < 8) {
temp = isAdd ? blockedList.add(i + "" + col + "")
: blockedList.remove(i + "" + col + "");
}
if (row < 8) {
temp = isAdd ? blockedList.add(row + "" + i + "")
: blockedList.remove(row + "" + i + "");
}
if ((flag1 + i) < 8) {
temp = isAdd ? blockedList.add((flag1 + i) + "" + (i) + "")
: blockedList.remove((flag1 + i) + "" + (i) + "");
}
if ((flag2 - i) < 8) {
temp = isAdd ? blockedList.add((flag2 - i) + "" + (i) + "")
: blockedList.remove((flag2 - i) + "" + (i) + "");
}
}
} else {
for (int i = 0; i < 8; i++) {
flag1 = col > 4 ? 7-col : col;
flag2 = col + flag1;
flag1 = col - flag1;
temp = isAdd ? blockedList.add(i + "" + col + "")
: blockedList.remove(i + "" + col + "");
temp = isAdd ? blockedList.add(row + "" + i + "")
: blockedList.remove(row + "" + i + "");
temp = isAdd ? blockedList.add(i + "" + i + "")
: blockedList.remove(i + "" + i + "");
if((flag2-i) >= 0 && (flag2-i) < 8 && (flag1 + i) >= 0 && (flag1 + i) < 8)
temp = isAdd ? blockedList.add((flag2-i) + "" + (flag1 + i))
: blockedList.remove((flag2-i) + "" + (flag1 + i));
}
}
}
private static boolean adjustBadPosition(int row) {
int tempj=0;
boolean changed = false;
for(int j= 0; j<8; j++ ) {
if(chessBoard[row][j] != 0) {
chessBoard[row][j] = 0;
tempj = j;
changed = true;
}
}
if(changed) {
for(int j=tempj+1; j<8; j++)
blockedList.remove(row+""+j);
for(int i=row+1; i<8; i++) {
for(int j= 0; j<8; j++ ) {
chessBoard[i][j] = 0;
blockedList.remove(i+""+j);
}
}
resetUpdateList();
blockedList.add(row+""+tempj);
return true;
}
return false;
}
private static void resetUpdateList() {
for(int i=0; i<8; i++) {
for(int j= 0; j<8; j++ ) {
if(chessBoard[i][j] != 0 ) {
updateBlockedSet(i,j,true);
}
}
}
}
public static Set<String> getPositions() {
if(result.isEmpty()) {
for( int row = 0; row < 8; row++) {
if(row < 0) break;
for(int col = 0; col< 8; col++) {
if(!blockedList.contains(row+""+col)) {
chessBoard[row][col] = row+1;
updateBlockedSet(row,col,true);
break;
} else if(col == 7){
adjustBadPosition(row-1);
row = row -2;
break;
}
}
if(row == 7) {
printBoard(true);
adjustBadPosition(row);
row--;
}
}
}
return result;
}
public static void main(String... arg) {
//System.out.println(result);
System.out.println(getPositions().size());
}
}
Sample output :
1 B B B B B B B
B B B B 2 B B B
B B B B B B B 3
B B B B B 4 B B
B B 5 B B B B B
B B B B B B 6 B
B 7 B B B B B B
B B B 8 B B B B
Done1
92 positions : I have listed only columns.
0|4|7|5|2|6|1|3| = 0,0 | 1,4| 2,7 | 3,5| 4,2| 5,6 | 6,1| 7,3 = Top Listed board
0|5|7|2|6|3|1|4|
0|6|3|5|7|1|4|2|
0|6|4|7|1|3|5|2|
1|3|5|7|2|0|6|4|
1|4|6|0|2|7|5|3|
1|4|6|3|0|7|5|2|
1|5|0|6|3|7|2|4|
1|5|7|2|0|3|6|4|
1|6|2|5|7|4|0|3|
1|6|4|7|0|3|5|2|
1|7|5|0|2|4|6|3|
2|0|6|4|7|1|3|5|
2|4|1|7|0|6|3|5|
2|4|1|7|5|3|6|0|
2|4|6|0|3|1|7|5|
2|4|7|3|0|6|1|5|
2|5|1|4|7|0|6|3|
2|5|1|6|0|3|7|4|
2|5|1|6|4|0|7|3|
2|5|3|0|7|4|6|1|
2|5|3|1|7|4|6|0|
2|5|7|0|3|6|4|1|
2|5|7|0|4|6|1|3|
2|5|7|1|3|0|6|4|
2|6|1|7|4|0|3|5|
2|6|1|7|5|3|0|4|
2|7|3|6|0|5|1|4|
3|0|4|7|1|6|2|5|
3|0|4|7|5|2|6|1|
3|1|4|7|5|0|2|6|
3|1|6|2|5|7|0|4|
3|1|6|2|5|7|4|0|
3|1|6|4|0|7|5|2|
3|1|7|4|6|0|2|5|
3|1|7|5|0|2|4|6|
3|5|0|4|1|7|2|6|
3|5|7|1|6|0|2|4|
3|5|7|2|0|6|4|1|
3|6|0|7|4|1|5|2|
3|6|2|7|1|4|0|5|
3|6|4|1|5|0|2|7|
3|6|4|2|0|5|7|1|
3|7|0|2|5|1|6|4|
3|7|0|4|6|1|5|2|
3|7|4|2|0|6|1|5|
4|0|3|5|7|1|6|2|
4|0|7|3|1|6|2|5|
4|0|7|5|2|6|1|3|
4|1|3|5|7|2|0|6|
4|1|3|6|2|7|5|0|
4|1|5|0|6|3|7|2|
4|1|7|0|3|6|2|5|
4|2|0|5|7|1|3|6|
4|2|0|6|1|7|5|3|
4|2|7|3|6|0|5|1|
4|6|0|2|7|5|3|1|
4|6|0|3|1|7|5|2|
4|6|1|3|7|0|2|5|
4|6|1|5|2|0|3|7|
4|6|1|5|2|0|7|3|
4|6|3|0|2|7|5|1|
4|7|3|0|2|5|1|6|
4|7|3|0|6|1|5|2|
5|0|4|1|7|2|6|3|
5|1|6|0|2|4|7|3|
5|1|6|0|3|7|4|2|
5|2|0|6|4|7|1|3|
5|2|0|7|3|1|6|4|
5|2|0|7|4|1|3|6|
5|2|4|6|0|3|1|7|
5|2|4|7|0|3|1|6|
5|2|6|1|3|7|0|4|
5|2|6|1|7|4|0|3|
5|2|6|3|0|7|1|4|
5|3|0|4|7|1|6|2|
5|3|1|7|4|6|0|2|
5|3|6|0|2|4|1|7|
5|3|6|0|7|1|4|2|
5|7|1|3|0|6|4|2|
6|0|2|7|5|3|1|4|
6|1|3|0|7|4|2|5|
6|1|5|2|0|3|7|4|
6|2|0|5|7|4|1|3|
6|2|7|1|4|0|5|3|
6|3|1|4|7|0|2|5|
6|3|1|7|5|0|2|4|
6|4|2|0|5|7|1|3|
7|1|3|0|6|4|2|5|
7|1|4|2|0|6|3|5|
7|2|0|5|1|4|6|3|
7|3|0|2|5|1|6|4|
Subscribe to:
Posts (Atom)