Giudoku Official Site
N-Queens Puzzle

This important puzzle is first a mathematical one, and was first posed by a chess player in 1848. It's the problem of posing n queens on a nxn chess board so that no queen can attack one another. In other words, no queen can be in the same row, column or diagonal as another one. The solution is not unique and exists only for n=1, n=4 and for n > 4.
The most famous version of the puzzle involves 8 queens, but I'm going to describe the generalized version.

The algorithm I'm going to use is one of the simplest ones. It's based on backtracking: a backtracking algorithm incrementally builds a possible combination, until it finds out a contradiction and comes back to a previous point to try another combination. When the algorithm arrives to a complete combination, that combination is valid: in our case, it's immediately returned to the calling method, because I'm not interested in printing out all the possible solutions (which for n=8 are 92 already!) but in finding just one.

The core method solve() is quite easy to understand. It uses the support class Board to manage the board and the queens.
For every row in the matrix, poses the queen in that row, and if it's okay (no conflict is created with previous queens) continues with the next queen. When k queens have been placed without problems, the solution is found. An important note: the queen number is exactly the column number of the queen in the matrix. This is a little trick to make sure no queens are in the same column without having to check, and improves performance a little by eliminating some of the invalid combinations. Other tricks like this are usually employed to fasten the algorithm.

The main code is shown below, for the Board class, click here.

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
public class Queens
{
  public static void main(String[] args)
  {
    int k = 0;
    
    try
    {
      k = Integer.parseInt(args[0]);
      Board b = solve(k);
      System.out.println("A configuration was found!");
      System.out.println();
      System.out.println(b);
    }
    catch (ArrayIndexOutOfBoundsException e)
    {
      System.out.println("The program requires exactly an argument");
      System.out.println("indicating the number of queens and the size of the board");
    }
    catch (NegativeArraySizeException e)
    {
      System.out.println("The argument must be a positive number");
    }
    catch (NumberFormatException e)
    {
      System.out.println("The argument is not a valid integer");
    }
    catch (IllegalStateException e)
    {
      System.out.println("No possible configuration exists for k = " + k);
    }
    
  }
  
  public static Board solve(int k)
  {
    Board b1 = new Board(k);
    
    if(!solve(b1, k, 0))
    {
      throw new IllegalStateException();
    }
    
    return b1;
  }
  
  public static boolean solve(Board b1, int k, int queen)
  {
    if (queen >= k)
    {
      return true;
    }
    
    for (int row = 0; row < k; row++)
    {
      b1.setQueenOnPosition(row, queen);
      
      if (!isThereConflict(b1, queen))
      {
        if (solve (b1, k, queen+1))
        {
          return true;
        }
      }
    }
    
    return false;
  }

  /*
   * Checks if any of the previous queens "annoys" this one
   */
  public static boolean isThereConflict(Board B, int queen)
  {
    for (int j = 0; j < queen; j++)
    {
      if (B.queensInFight(j, queen))
      {
        return true;
      }
    }
    
    return false;
  }
        
}