Skip to content

Instantly share code, notes, and snippets.

@kmizu
Created December 9, 2020 08:03
Show Gist options
  • Save kmizu/b7cf14b445923c0daf00d0065b9e35e8 to your computer and use it in GitHub Desktop.
Save kmizu/b7cf14b445923c0daf00d0065b9e35e8 to your computer and use it in GitHub Desktop.
NQueen Problem Solver in Java
import java.util.*;
import java.awt.Point;
public class NQueen {
public static final String ANSI_GREEN = "\u001B[32m";
public static final String ANSI_RESET = "\u001B[0m";
public static final String ANSI_WHITE = "\u001B[37m";
private final int N;
private final Set<Point> queens;
public NQueen(int N) {
this.N = N;
this.queens = new HashSet<>();
}
private static int diff(int a, int b) {
return Math.abs(a - b);
}
private static boolean canPut(Set<Point> queens, Point p) {
if(queens.contains(p)) return false;
for(var q:queens) {
if(q.x == p.x || q.y == p.y) return false;
if(diff(q.x, p.x) == diff(q.y, p.y)) {
return false;
}
}
return true;
}
private boolean tryPut(int n) {
if(n == N) return true;
for(int x = 0; x < N; x++) {
for(int y = 0; y < N; y++) {
var point = new Point(x, y);
if(canPut(queens, point)) {
queens.add(point);
var succeed = tryPut(n + 1);
if(succeed) return true;
queens.remove(point);
}
}
}
return false;
}
public void solve() {
if(tryPut(0)) {
printBoard();
}
}
private void printBoard() {
for(int x = 0; x < N; x++) {
for(int y = 0; y < N; y++){
if(queens.contains(new Point(x, y))) {
System.out.print(ANSI_GREEN + "Q " + ANSI_RESET);
} else {
System.out.print(ANSI_WHITE + "X " + ANSI_RESET);
}
}
System.out.println();
}
}
public static void main(String[] args) {
var n = Integer.parseInt(args[0]);
var nqueen = new NQueen(n);
nqueen.solve();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment