I like playing games, from board games to computer games to logic puzzles. However, the type of puzzles that intrigue me most are the logic puzzles that really need a computer to be solved (or perhaps I am too lazy to think them through all the way and a computer is a really useful tool for anyone too lazy to think puzzles through for themselves?).
Luckily for me, one of my colleagues and friends, Menno also likes these types of puzzles and we have been playing the game of ’solve this problem with a computer program’ for some time now. The interesting part of it is that Menno programs in JavaScript while I program in C++, Java or Emacs Lisp.
Some of the puzzles we have tackled up to now include ‘17 square’ and ‘The N Queen‘ problem. With 2 people looking at a problem individually of course yields 2 completely different solutions, especially when the solutions are programmed in 2 totally different languages.
Since these type of puzzles take up a lot of my spare programming time I figured it would make good blog posts and might inspire Menno to post his solutions as well.
The first puzzles I would like to pose is the Eight Queen problem, also known as N Queen, since you can pose it with an arbitrary number really.
The problem states that you have a board of N by N squares on which you want to place N Queens (with the movement restrictions of the chess game, just to be clear) in such a manner that none of the Queens are attacked. This problem has 92 possible solutions of which 12 are unique, the rest are reflections or rotations of the board.
Many approaches will lead to a solution of this problem but I chose to use recursion to solve it and implement it in Java, although I have a partially working Emacs Lisp version as well, but am having some weirdness with the recursion not ending up the way I expected it…
Without further lingering, here is my solution:
package credmp.games;
public class EightQueens {
private int SIZE = 8;
private int board[];
private int solutions = 0;
public EightQueens() {
board = new int[SIZE];
}
public EightQueens(int size) {
this.SIZE = size;
board = new int[SIZE];
}
public int getSolutions() {
return solutions;
}
public void solve(int row) {
for (int column = 0; column < SIZE; column++) {
if (is_safe(board[row - 1] = column, row - 1)) {
if (row < SIZE) solve(row + 1); else print_board();
}
}
}
private boolean is_safe(int column, int row) {
for (int i = 1; i <= row; i++) {
int current = board[row - i];
if (current == column ||
current == column - i ||
current == column + i)
return false;
}
return true;
}
private void print_board() {
++solutions;
for (int i = 0; i < (SIZE * 4 + 1); ++i)
System.out.print("-");
System.out.println();
for (int row = 0; row < SIZE; row++) {
for (int column = 0; column < SIZE; column++ ) {
System.out.print(column == board[row] ? "| X " : "| ");
}
System.out.print("|\n");
for (int i = 0; i < (SIZE * 4 + 1); ++i)
System.out.print("-");
System.out.print("\n");
}
}
public static void main(String args[]) {
long start = System.currentTimeMillis();
EightQueens eq = new EightQueens(8);
eq.solve(1);
long end = System.currentTimeMillis();
System.out.println("Time spent: " +
(end - start) + "ms for solutions:" +
eq.getSolutions() );
}
}
Code
Code, games, N queens
