Friday, September 26, 2014

Solving eight queens problem with random walk algorithm

Recently I wrote article about solving eight queens problem with electrical force analogy. But after thinking some time I came to conclusion that repulsion force from the board edges and repulsion force between queens will force queens to move in random fashion. So in general this queens behavior should be comparable to random walk algorithm. So seems that at least in this case concept of electric force is not needed - we should follow an Occams's razor principle and simply use random walk algorithm which will generate comparable results. Algorithm principle is very simple - one needs to have just a bunch of initial random values for some parameters (in queen case parameter would be X or Y position for the queen) and then in each subsequent iteration one just needs to apply some small random shift to each parameter value until solution is found. So this random walk concept I implemented in latest Java eight queens solver which you can download and use without restrictions. Code structure:

- JavaEightQueensProblem.
Main class which employs random walk algorithm for solving eight queens problem.

- RandomWalkerParameter.
Class which holds random value to shift in each algorithm iteration. Besides it holds two ranges - random value range, which defines number limits for random value and shift step range, which defines number limits for shift step. In each iteration random shift step is added to current random value.

- RandomWalkerUnit.
Class holding list of random walk parameters and state which defines unit has reached terminating value or not. If unit has reached terminating value - subsequent random shifts are not applied to unit parameters. Basically this class is just needed for grouping parameters. For example queen random unit will have two parameters - X,Y. So in queen case both values X,Y will be randomly mutated until queen will reach good position on board. So calculation terminating condition is meaningful only for X,Y pair - i.e. random unit will have two X,Y parameters in list for queen problem case.
- RandomWalker.
Class which executes random walk algorithm. Most important things which should be passed into RandomWalker constructor is: list of random walker units and object which will have method for checking if random walk unit has reached terminal state or not. This method will be then executed dynamically by using java reflection in each subsequent random walk iteration. By the way, you can pass class instance OR class itself into this calculator object parameter. Passing class itself is good if your terminal condition calculation method is static - so in this case you don't have to create class instance for calling method and thus it is reasonable for random walk constructor to accept class object itself. Next when random walker object is constructed one just needs to execute one method named "startRandomWalkSearch()" to begin looking for solution to some problem. This random search algorithm has no special magic in it :-), basic code is simple like this:
    public void startRandomWalkSearch() {
        Random rnd = new Random();
        int iterationsUntilRestart = 0;
        
        initializeRandomWalkUnits();
        for (int i = 0; i < iterationsToTry; i++) {
            iterationsUntilRestart++;
            
            if (unitsNotInTerminalState == 0) {
                iterationsUntilSolution = i + 1;
                return;
            }          
            
            if (iterationsUntilRestart > restartRandomWalkAfterIterations) {
                iterationsUntilRestart = 0;
                initializeRandomWalkUnits();
                continue;
            }
            
            for (int iUnit = 0; iUnit < randomWalkUnits.size(); iUnit++) {
                if (!randomWalkUnits.get(iUnit).terminalConditionReached) {
                    
                    for (RandomWalkerParameter randomWalkParameter : randomWalkUnits.get(iUnit).randomWalkerParameters) {
                        double stepValue;
                        double stepValueDiff = randomWalkParameter.stepRange[1] - randomWalkParameter.stepRange[0];

                        // calculate step value
                        if (randomWalkParameter.onlyIntegralValuesInStep)
                            stepValue = randomWalkParameter.stepRange[0] + (double)rnd.nextInt((int)(stepValueDiff + 1.0));
                        else
                            stepValue = randomWalkParameter.stepRange[0] + stepValueDiff * rnd.nextDouble();

                        // apply step
                        randomWalkParameter.value += stepValue;
                        randomWalkParameter.value = Math.min(randomWalkParameter.value, randomWalkParameter.valueRange[1]);
                        randomWalkParameter.value = Math.max(randomWalkParameter.value, randomWalkParameter.valueRange[0]);

                    }
                    // check terminal condition
                    Class[] types = new Class[2];
                    types[0] = List.class;
                    types[1] = int.class;
                    try {
                        boolean isJavaClass = terminalConditionCalculatorObject.getClass().toString().contains("java.lang.Class");
                        Method method;
                        if (isJavaClass)
                            method = ((Class)terminalConditionCalculatorObject).getMethod(terminalConditionCalculatorMethod, types);
                        else
                            method = terminalConditionCalculatorObject.getClass().getMethod(terminalConditionCalculatorMethod, types);
                        
                        randomWalkUnits.get(iUnit).terminalConditionReached = 
                                                        (boolean)method.invoke(terminalConditionCalculatorObject, randomWalkUnits, iUnit);    
                        if (randomWalkUnits.get(iUnit).terminalConditionReached)
                            unitsNotInTerminalState--;
                    } 
                    catch ( NoSuchMethodException | 
                            NullPointerException | 
                            SecurityException | 
                            IllegalAccessException | 
                            InvocationTargetException e) {
                        throw new RuntimeException(e.toString());
                    }
                }
            }
        }
    }
Algorithm idea is to initialize each unit's parameters to some random value. Then there is for loop which applies small random step to parameter value and then checks if this unit has reached terminal(solution) state or not, by calling terminal condition calculation method using reflection.
And there is some unit test package which checks if random walk algorithm works - if you will want to modify algorithm. So you will need to see if random walk has good integrity after that or not :-) There is just one test package:

- RandomWalkerTest.
. What it does is - creates random walk object for performing random search if some number X can be factorized into A * B. This test package has two tests inside - testRandomWalkSearchNumberWasFactorized which tests if number was factorized correctly and test named testRandomWalkSearchNumberWasNotFactorized which expects that factorization must fail, because we pass prime number for factorization, which of course can't be factorized into smaller parts.
Have fun in using random walk search algorithm !!

No comments:

Post a Comment

Comment will be posted after comment moderation.
Thank you for your appreciation.