Solving eight queens problem with electrical force analogy

In this problem I wanted to design and test some innovative algorithm approach for finding solution to eight queens puzzle. Algorithm idea is based on electrical force analogy. Hypothesis for algorithm design was that if queens are affected by some electrical field which pushes queens from each other by some law - after some iterations queens should arrange into stable positions which will compose solution. Idea was successful. But for this algorithm to work one needs 3 repulsion forces: - electrical force. (Two queens pushes themselves apart so that distance between them increases. Imagine queens as some electric particles of same charge, for example electrons :-) ).
- repulsion from same line. (If two queens share same horizontal,vertical or diagonal - they pushes each other so that they must leave same line.)
- repulsion from board borders. (Borders are imagined as same charge particles as queens, so borders pushes queens to the center of board.)
Below are pictures which graphically represents these 3 pushing forces. Forces are pictured as vectors by which green queen affects blue queen.

Electrical force:


Repulsion from same line force:

There are six possible repulsion directions from the line occupied by two queens. Currently algorithm calculates these six repulsion directions and takes one random direction from those six. Not all directions are equal. It can be that those two queens may be moved to other line at next iteration. So algorithm may be improved to skip directions which forms other common line between those two queens. But this improvement was not in the scope of this article :-)

Repulsion from board borders:

It was imagined that borders pushes queens to the center of board - as board would be a circle, not a rectangle. So this approximation is not very accurate - next improvement for algorithm :-) But for this scope that approach is good enough and works. So in the end superposition of these three forces accumulated from all queens and borders pushes targeted queen into right position - partial solution of eight queens problem. And finally we get solution. Algorithm was developed with JAVA programming language. This is my first experience with JAVA, so don't expect nice OO patern :-) I was developing with NetBeans IDE, which is a great tool for JAVA. You can download this solution and use as you need from here. Class structure of JAVA project is following:

- ChessBoard.
Holds information about queens, chess board representation data for printing board to output, groups code which targets queen objects.

- CollisionDetector.
Very small class which actually holds just one function "hasCollision" for calculating are two queens on the same position.

- EightQueensSolver.
Abstracts solution problem at a highest level. Most important method is SolveEightQueensProblem() which is structured as following:

    public boolean SolveEightQueensProblem() {
        final int totalIterations = 10000;
        boolean found;
        
        for (int iterations = 0; iterations < totalIterations; iterations++) {
            findMaximumTwoWrongQueens();
            if (currentWrongPositions == 0)
                return true;
            if (currentWrongPositions == 1) {
                found = findBruteForceSolutionFor1Queen();
                if (found)
                    return true;
            }
            if (currentWrongPositions == 2) {
                found = findBruteForceSolutionFor2Queens();
                if (found)
                    return true;
            }
        }
        return false;
    }

All our algorithm magic goes into function "findMaximumTwoWrongQueens()" - where by using above mentioned forces algorithm finds out at most two queens in wrong positions and then later SolveEightQueensProblem() performs brute force on those two queens positions. findMaximumTwoWrongQueens is structured as following (not very important code here is skipped for representing reader most useful algorithm part.):

    private void findMaximumTwoWrongQueens() {
        final int iterationsForTwoWrongPositions = 300;

        currentWrongPositions = 8;
        
        while (currentWrongPositions > 2) {
            chessBoard = new ChessBoard();
            chessBoard.RandomlyPlaceEightQueens();

            for (int i = 0; i < iterationsForTwoWrongPositions; i++) {
                chessBoard.ApplyElectricForce();
                chessBoard.UpdateChessBoard();
                currentWrongPositions = chessBoard.numberOfQueensInWrongPositions();
                if (currentWrongPositions < 3)
                    break;
            }            
        }        
    }

Here most interesting code is function ApplyElectricForce() which calculates new movement direction for each queen by calling method CalculateGlobalMovementDirection(Queen, ChessBoard). Method CalculateGlobalMovementDirection() is structured as following:

    public Tuple CalculateGlobalMovementDirection(Queen queen, ChessBoard chessBoard) {
        Tuple direction = Tuple.zeroTuple;
        Tuple directionInfluenceZoneRepulsion = Tuple.zeroTuple;
        Tuple directionElectricForceFromQueen = Tuple.zeroTuple;
        Tuple directionElectricForceFromBoardBorders = Tuple.zeroTuple;
         
        if (queen == null)
           throw new RuntimeException("queen is null");
         
        if (chessBoard == null)
         throw new RuntimeException("chessboard is null");
                
        for (int i = 0; i < 8; i++) {
            if (queen.Id.equals(chessBoard.queens[i].Id) == false) {
                directionInfluenceZoneRepulsion = RepulsionFromTheSameLineDirectionFromAnotherQueen(queen, chessBoard.queens[i]);
                directionElectricForceFromQueen = ElectricForceDirectionFromAnotherQueen(queen, chessBoard.queens[i]);
                
                if (Tuple.AreTuplesTheSame(directionInfluenceZoneRepulsion, Tuple.zeroTuple))
                    directionElectricForceFromQueen = Tuple.zeroTuple;
                
                direction = Tuple.AddTuples(direction, 
                                            Tuple.AddTuples
                                                (
                                                 Tuple.multiplyScalar(6,  directionInfluenceZoneRepulsion),
                                                 Tuple.multiplyScalar(2,  directionElectricForceFromQueen)
                                                )
                                            );
            }
        }
        
        // add borders effect
        directionElectricForceFromBoardBorders = ElectricForceDirectionFromBoardBorders(queen);
        direction = Tuple.AddTuples(
                                    Tuple.multiplyScalar(1,   direction), 
                                    Tuple.multiplyScalar(5,   directionElectricForceFromBoardBorders)
                                    ); 
                
        return Tuple.NormalizeTuple(direction);
    }

This method is the key to success of our algorithm and is most important code part.

- Geometry.
This class abstracts methods for detecting if two queens are on the same line - be it horizontal,vertical or diagonal.

- JavaEightQueensProblem.
Class which holds main() method, i.e. main program.

- Queen.
Very tiny class which just abstracts some queen attributes such as queen identification on board, queen position, queen movement direction and queen state determining if it reached position not influenced by other queens or not.

- RepulsionForce.
This class has several very important methods: ElectricForceDirectionFromAnotherQueen - calculates direction of target queen affected by source queen electrical force; RepulsionFromTheSameLineDirectionFromAnotherQueen - calculates direction of target queen affected by source queen force which pushes queen from the same line; ElectricForceDirectionFromBoardBorders - calculates direction of target queen affected by board borders electrical force which pushes queen towards the center of board; CalculateGlobalMovementDirection - calculates direction of target queen which is aggregation of all directions produced by forces of 7 other queens and direction produced by board borders repulsion force.

- Tuple.
Helper class which introduces Tuple abstraction and methods which groups vector algebra operations. Here Tuple is used as vector in plane.
That's it about solution code. Now I think it would be fun to see some movie of solution formation under effect of repulsion forces. On each algorithm run some random solution is found. Here it is my favorite one:

So in this algorithm run after 1397 iterations queens arranges into such beautiful solution lattice:


Conclusion:
Seems electrical force analogy is useful for solving eight queens problem and may be useful too for solving other general problems where not exists exact algorithm for finding solution, but some general algorithms are used - such as genetic algorithms, genetic programming, etc. One just needs to make a good abstraction for repulsion/attraction forces which pushes problem state from bad solutions or attracts towards better partial ones.
Have fun using electrical force analogy in algorithms !