In case Flash no longer exists; a copy of this site is included in the Flashpoint archive's "ultimate" collection.

Dead Code Preservation :: Archived AS3 works from wonderfl.net

N-Queen Problem Solver - with GA

"N-Queen Problem Solver - with GA" is Released.
http://en.wikipedia.org/wiki/Eight_queens_puzzle
You can find this problem's answer with other algorithms, but genetic algorithm is also works so good.
We don't have to check vertical and horizontal conflict, because of data structure of population(implicitly preclude conflict).
I made one population: not n*n array of 0~1, n vector of 0~n-1. And it does not overlap each other, so we don't have to check vertically and horizontally.
So we do check just diagonally, and computation time is very fast.
Get Adobe Flash player
by greentec 26 Sep 2013

    Talk

    greentec at 26 Sep 2013 19:42
    if the searching speed is slow, add more population and reset. I found the answer of 50-queens problems within 200 generation with 500 population.
    makc3d at 27 Sep 2013 04:22
    code formatting is terrible :)
    greentec at 27 Sep 2013 05:11
    sorry for that. i usually work in flashdevelop and copy code to wonderfl, at that time additional <br> is created. i will fix that in later code.

    Tags

    Embed
/**
 * Copyright greentec ( http://wonderfl.net/user/greentec )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/6BLt
 */

package {
    import com.bit101.components.Label;

    import com.bit101.components.NumericStepper;

    import com.bit101.components.PushButton;

    import com.bit101.components.Window;

    import flash.display.Sprite;

    import flash.events.Event;

    import flash.events.MouseEvent;

    import flash.display.Bitmap;

    import flash.display.BitmapData;

    import flash.geom.ColorTransform;

    import flash.geom.Matrix;

    import com.bit101.charts.LineChart;
    
    public class FlashTest extends Sprite {
        
        public var problemN:int = 12;

        public var fitnessMax:int = problemN * problemN;

        public var prevBestFitness:int = 0;

        public var bestFitness:int = 0;

        

        public var fitnessLineChart:LineChart;

        public var fitnessLineChartLabel:Label;

        public var chartRefreshCycle:int = 50;

        public var bestFitnessLineChart:LineChart;

        public var bestFitnessLineChartLabel:Label;

        public var bestData:Array = [];

        

        public var tile_width:int = 30;

        public var tile_height:int = 30;

        public var board_width:int = tile_width * problemN;

        public var queenSize:int = 30;

        

        public var tileBitmapData:BitmapData;

        public var tileBitmap:Bitmap;

        public var gridSprite:Sprite;

        

        public var queenBitmapData:BitmapData;

        public var queenBitmap:Bitmap;

        public var queenSprite:Sprite;

        

        public var generationNo:int = 0;

        public var endGenerationNo:int = 10000;

        public var populationNum:int = 50;

        public var population:Vector.<Vector.<int>>=new Vector.<Vector.<int>>(populationNum);

        public var populationScore:Vector.<int> = new Vector.<int>(populationNum);

        public var selectionExpect:Vector.<int>;

        

        public var queenGraphic:Sprite;

        

        public var eliteRate:Number = 0.05;

        public var parentRate:Number = 0.4;

        public var mutationRate:Number = 0.03;

        

        public var redQueenColt:ColorTransform;

        

        public var uiWindow:Window;

        public var startButton:PushButton;

        public var stopButton:PushButton;



        public var resetButton:PushButton;

        public var titleLabel:Label;

        public var generationLabel:Label;

        public var fitnessLabel:Label;

        public var nLabel:Label;

        public var nNumericStepper:NumericStepper;

        public var populationLabel:Label;

        public var populationNumericStepper:NumericStepper;

        public var parentLabel:Label;

        public var parentNumericStepper:NumericStepper;

        public var mutationLabel:Label;

        public var mutationNumericStepper:NumericStepper;

        public var boardMaxWidthLabel:Label;

        public var boardMaxWidthNumericStepper:NumericStepper;

        

        public var graphWindow:Window;
        

        public function FlashTest() {
            // write as3 code here..
            if (stage) init();

            else addEventListener(Event.ADDED_TO_STAGE, init);
        }
        
        private function init(e:Event = null):void 

        {

            removeEventListener(Event.ADDED_TO_STAGE, init);

            // entry point

            

            stage.scaleMode = "noScale";

            
            tileBitmapData = new BitmapData(465, 465, true, 0x00ffffff);

            gridSprite = new Sprite();

            tileBitmap = new Bitmap(tileBitmapData);

            addChild(tileBitmap);

            

            initTileGrid(problemN, problemN);

            

            initPopulation(populationNum, problemN);

            

            queenBitmapData = new BitmapData(465, 465, true, 0x00ffffff);

            queenBitmap = new Bitmap(queenBitmapData);

            addChild(queenBitmap);

            

            queenGraphic = new Sprite();

            with (queenGraphic.graphics)

            {

                lineStyle(0, 0x000000);

                beginFill(0x000000);

                drawCircle(0, -12, 2);

                drawCircle(5, -10, 2);

                drawCircle(10, -8, 2);

                drawCircle(-5, -10, 2);

                drawCircle(-10, -8, 2);

                moveTo( -8, 0);

                lineTo( -10, -8);

                lineTo( -5, 0);

                lineTo( -5, -10);

                lineTo( -2, 0);

                lineTo( 0, -12);

                lineTo( 2, 0);

                lineTo( 5, -10);

                lineTo( 5, 0);

                lineTo( 10, -8);

                lineTo( 8, 0);

                

                lineTo( 6, 2);

                lineTo( 5, 5);

                lineTo( 8, 10);

                lineTo( -8, 10);

                lineTo( -5, 5);

                lineTo( -6, 2);

                lineTo( -8, 0);

                endFill();

                

                lineStyle(1, 0xffffff);

                moveTo(-4, 5);

                lineTo(4, 5);

                moveTo( -5, 2);

                lineTo(5, 2);

            }

            

            redQueenColt = new ColorTransform(0.5, 0.5, 0.5, 1, 255, 0, 0, 0);

            

            uiWindow = new Window(this, 300, 10, "Control");

            uiWindow.width = 150;

            uiWindow.height = 250;

            uiWindow.hasMinimizeButton = true;
            
            uiWindow.alpha = 0.7;

            startButton = new PushButton(uiWindow, 10, 30, "Start", onStart);

            startButton.width = 43;

            startButton.height = 40;

            stopButton = new PushButton(uiWindow, startButton.x + startButton.width, startButton.y, "Stop", onStop);

            stopButton.width = 43;

            stopButton.height = 40;

            resetButton = new PushButton(uiWindow, stopButton.x + stopButton.width, stopButton.y, "Reset", onReset);

            resetButton.width = 43;

            resetButton.height = 40;

            titleLabel = new Label(uiWindow, 10, startButton.y + startButton.height, "N-Queen Solver - with GA");

            generationLabel = new Label(uiWindow, 10, titleLabel.y + titleLabel.height, "Generation : " + String(generationNo) + " / " + String(endGenerationNo));

            fitnessLabel = new Label(uiWindow, 10, generationLabel.y + generationLabel.height, "Best Fit. : " + String(bestFitness));

            nLabel = new Label(uiWindow, 10, fitnessLabel.y + fitnessLabel.height, "N");

            nNumericStepper = new NumericStepper(uiWindow, uiWindow.width - 90, nLabel.y);

            nNumericStepper.step = 1;

            nNumericStepper.width = 80;

            nNumericStepper.minimum = 2;

            nNumericStepper.maximum = 50;

            nNumericStepper.value = problemN;

            //nNumericStepper.enabled = false;

            populationLabel = new Label(uiWindow, 10, nLabel.y + nLabel.height, "Population");

            populationNumericStepper = new NumericStepper(uiWindow, uiWindow.width - 90, populationLabel.y);

            populationNumericStepper.width = 80;

            populationNumericStepper.value = populationNum;

            populationNumericStepper.step = 50;

            populationNumericStepper.minimum = 50;

            parentLabel = new Label(uiWindow, 10, populationLabel.y + populationLabel.height, "Parent %");

            parentNumericStepper = new NumericStepper(uiWindow, uiWindow.width - 90, parentLabel.y);

            parentNumericStepper.width = 80;

            parentNumericStepper.value = parentRate * 100;

            parentNumericStepper.step = 5;

            parentNumericStepper.minimum = 10;

            mutationLabel = new Label(uiWindow, 10, parentLabel.y + parentLabel.height, "Mutation %");

            mutationNumericStepper = new NumericStepper(uiWindow, uiWindow.width - 90, mutationLabel.y, onChangeValue);

            mutationNumericStepper.name = "mu";

            mutationNumericStepper.width = 80;

            mutationNumericStepper.value = mutationRate * 100;

            mutationNumericStepper.step = 0.5;

            mutationNumericStepper.minimum = 0;

            boardMaxWidthLabel = new Label(uiWindow, 10, mutationLabel.y + mutationLabel.height, "Board Max");

            boardMaxWidthNumericStepper = new NumericStepper(uiWindow, uiWindow.width - 90, boardMaxWidthLabel.y);

            boardMaxWidthNumericStepper.width = 80;

            boardMaxWidthNumericStepper.value = problemN * tile_width;

            boardMaxWidthNumericStepper.step = 20;

            boardMaxWidthNumericStepper.minimum = 200;

            boardMaxWidthNumericStepper.maximum = 460;

            

            graphWindow = new Window(this, 5, 300, "Graph");

            graphWindow.width = 455;

            graphWindow.height = 150;

            graphWindow.hasMinimizeButton = true;
            
            graphWindow.alpha = 0.7;

            

            fitnessLineChart = new LineChart(graphWindow, 40, 40, null);

            fitnessLineChart.showGrid = true;

            fitnessLineChart.showScaleLabels = true;

            fitnessLineChart.lineColor = 0xff0080;

            fitnessLineChart.width = 170;

            fitnessLineChartLabel = new Label(graphWindow, 10, fitnessLineChart.y - 20, "All Population Fitness");

            fitnessLineChartLabel.x = fitnessLineChart.x;

            fitnessLineChart.autoScale = false;

            fitnessLineChart.maximum = fitnessMax;

            fitnessLineChart.minimum = -1 * fitnessMax;

            

            bestFitnessLineChart = new LineChart(graphWindow, fitnessLineChart.x + fitnessLineChart.width + 50 + 5, fitnessLineChart.y, null);

            bestFitnessLineChart.showGrid = true;

            bestFitnessLineChart.showScaleLabels = true;

            bestFitnessLineChart.lineColor = 0x00ff00;

            bestFitnessLineChart.width = 170;

            bestFitnessLineChartLabel = new Label(graphWindow, 10, bestFitnessLineChart.y - 20, "Best Population Fitness");

            bestFitnessLineChartLabel.x = bestFitnessLineChart.x;

            bestFitnessLineChart.autoScale = false;

            bestFitnessLineChart.maximum = fitnessMax;

            bestFitnessLineChart.minimum = 0;

            

            

        }

        

        private function onChangeValue(e:Event):void

        {

            switch(e.target.name)

            {

                case "mu": //mutation

                    mutationRate = e.target.value / 100;

                    

                    break;

            }

        }

        

        private function onStart(e:Event):void

        {

            addEventListener(Event.ENTER_FRAME, onLoop);

            startButton.enabled = false;

            stopButton.enabled = true;

            resetButton.enabled = false;

            

            nNumericStepper.enabled = false;

            populationNumericStepper.enabled = false;

            parentNumericStepper.enabled = false;

        }

        

        private function onStop(e:Event):void

        {

            removeEventListener(Event.ENTER_FRAME, onLoop);

            stopButton.enabled = false;

            startButton.enabled = true;

            resetButton.enabled = true;

            

            nNumericStepper.enabled = true;

            populationNumericStepper.enabled = true;

            parentNumericStepper.enabled = true;

        }

        

        private function onReset(e:Event):void

        {

            problemN = nNumericStepper.value;

            fitnessMax = problemN * problemN;

            board_width = boardMaxWidthNumericStepper.value;

            tile_width = board_width / problemN;

            tile_height = tile_width;

            

            initTileGrid(problemN, problemN);

            

            generationNo = 0;

            populationNum = populationNumericStepper.value;

            initPopulation(populationNum, problemN);

            

            drawBestPosition(population[0]);

            bestFitness = evalPopulation(population[0]);

            

            drawUI();

            

            fitnessLineChart.maximum = fitnessMax;

            fitnessLineChart.minimum = -1 * fitnessMax;

            bestFitnessLineChart.maximum = fitnessMax;

            bestFitnessLineChart.minimum = 0;

            

            bestData = [];

        }

        

        private function onLoop(e:Event):void

        {

            var i:int;

            var j:int;

            var temp:int;

            

            //select

            sortDescending();

            

            var selectionSum:int = 0;

            selectionExpect = new Vector.<int>(populationNum * parentRate);

            for (i = 0; i < populationNum * parentRate ; i += 1)

            {

                selectionExpect[i] = Math.max(1, populationScore[i]);

                selectionSum += selectionExpect[i];

                //trace(selectionExpect[i]);

            }

            

            

            

            //crossover

            for (i = populationNum * eliteRate; i < populationNum; i += 1) //i = pop * elite => elite preserve; not elite => new pop

            {

                var firstParent:int = Math.random() * selectionSum;

                var secondParent:int = Math.random() * selectionSum;

                

                for (j = 0; j < selectionExpect.length; j += 1)

                {

                    if (firstParent < selectionExpect[j])

                    {

                        firstParent = j;

                        break;

                    }

                    

                    firstParent -= selectionExpect[j];

                }

                

                for (j = 0; j < selectionExpect.length; j += 1)

                {

                    if (secondParent < selectionExpect[j])

                    {

                        secondParent = j;

                        break;

                    }

                    

                    secondParent -= selectionExpect[j];

                }

                

                if (firstParent == secondParent) //same parent - reSelect

                {

                    i -= 1;

                    continue;

                    //trace("HI");

                }

                else //find crossover point

                {

                    for (var k:int = 0; k < problemN; k += 1)

                    {

                        population[i][k] = population[firstParent][k];

                    }

                    

                    var crossOverPoint1:int = Math.random() * (problemN - 1);

                    var crossOverPoint2:int = int( Math.random() * (problemN - crossOverPoint1) ) + crossOverPoint1;

                    //trace(crossOverPoint1, crossOverPoint2);

                    

                    for (k = crossOverPoint1; k < crossOverPoint2; k += 1)

                    {

                        if (population[i][k] != population[secondParent][k])

                        {

                            for (var l:int = 0; l < problemN; l += 1)

                            {

                                if (population[i][l] == population[secondParent][k] && l != k) 

                                {

                                    temp = population[i][l];

                                    population[i][l] = population[i][k];

                                    population[i][k] = temp;

                                    break;

                                }

                            }

                        }

                        else

                        {

                            population[i][k] = population[secondParent][k];

                        }

                        

                    }

                    

                }

            }

            

            //mutate

            for (i = populationNum * eliteRate; i < populationNum; i += 1) //not elite => mutation

            {

                for (j = 0; j < problemN; j += 1)

                {

                    if (Math.random() < mutationRate)

                    {

                        var second:int = Math.random() * problemN;

                        while (second == j)

                        {

                            second = Math.random() * problemN; //trace("HI" + j);

                        }                        

                        

                        temp = population[i][j];

                        population[i][j] = population[i][second];

                        population[i][second] = temp;

                    }

                }

            }

            

            prevBestFitness = bestFitness;

            var bestPopulationIndex:int = 0;

            

            for (i = 0; i < populationNum; i += 1)

            {

                populationScore[i] = evalPopulation(population[i]);

                if (Math.max(bestFitness, populationScore[i]) != bestFitness)

                {

                    bestFitness = Math.max(bestFitness, populationScore[i]);

                    bestPopulationIndex = i;

                }

            }

            

            generationNo += 1;

            

            //draw Route & bestChart

            bestData.push(bestFitness);

            

            if(prevBestFitness != bestFitness)

            {

                drawBestPosition(population[bestPopulationIndex]);

                drawBestChart();

            }

            

            drawUI();

            

            if (generationNo >= endGenerationNo || evalPopulation(population[bestPopulationIndex]) == fitnessMax)

            {

                sortDescending();

                

                drawChart(true);

                

                onStop(new Event(MouseEvent.CLICK));

                //removeEventListener(Event.ENTER_FRAME, onLoop);

            }

            

        }

        

        private function drawBestChart():void

        {

            bestFitnessLineChart.data = bestData;

            

            bestFitnessLineChart.draw();

        }

        

        private function drawChart(sw:Boolean):void

        {

            if (generationNo % chartRefreshCycle == 2 || sw == true)

            {

                var dataArray:Array = [];

                for (var i:int = 0; i < populationScore.length; i += 1)

                {

                    dataArray.push(populationScore[i]);

                }

                fitnessLineChart.data = dataArray;

                fitnessLineChart.minimum = 0;

                fitnessLineChart.draw();

                //trace(dataArray);

            }

        }

        

        private function drawUI():void

        {

            generationLabel.text = "Generation : " + String(generationNo) + " / " + String(endGenerationNo);

            fitnessLabel.text = "Best Fit. : " + String(bestFitness);

        }

        

        private function drawBestPosition(pop:Vector.<int>):void

        {

            queenBitmapData.fillRect(queenBitmapData.rect, 0x00ffffff);

            var mat:Matrix;

            var redArray:Array = [];

            for (var j:int = 0; j < pop.length; j += 1)

            {

                redArray.push(0);

            }

            

            for (var i:int = 0; i < pop.length - 1; i += 1) //diagonal check - left down, right down

            {

                for (j = i + 1; j < pop.length; j += 1)

                {

                    if (Math.abs(pop[i] - pop[j]) == Math.abs(i - j))

                    {

                        redArray[i] = 1;

                        redArray[j] = 1;

                    }

                }

            }

            

            for (i = 0; i < pop.length; i += 1)

            {

                mat = new Matrix();

                if (tile_width < queenSize)

                {

                    mat.scale(tile_width / queenSize, tile_width / queenSize);

                }

                

                mat.translate((pop[i]+1) * tile_width, (i+1) * tile_height);

                mat.translate( -1 * tile_width / 2, -1 * tile_height / 2);

                

                

                if (redArray[i] == 0)

                {

                    queenBitmapData.draw(queenGraphic, mat);

                }

                else //draw Red Queen

                {

                    queenBitmapData.draw(queenGraphic, mat, redQueenColt);

                }

                

            }

            

            

        }

        

        private function sortDescending():void

        {

            var temp:Array = [];

            var obj:Object;

            

            for (var i:int = 0; i < population.length; i += 1)

            {

                obj = new Object();

                obj.population = population[i];

                obj.score = populationScore[i];

                temp.push(obj);

            }

            

            temp.sortOn("score", Array.NUMERIC | Array.DESCENDING);

            

            for (i = 0; i < population.length; i += 1)

            {

                population[i] = temp[i].population;

                populationScore[i] = temp[i].score;

            }

            

            drawChart(false);

            

        }

        

        private function initTileGrid(tileNum_X:int, tileNum_Y:int):void

        {

            tileBitmapData.fillRect(tileBitmapData.rect, 0x00ffffff);

            

            //print Tile Grid

            gridSprite.graphics.clear();

            gridSprite.graphics.lineStyle(1, 0xffffff, 1);

            gridSprite.graphics.beginFill(0xc0c0c0, 1);

            gridSprite.graphics.drawRect(0, 0, tileNum_X * tile_width, tileNum_Y * tile_height);

            gridSprite.graphics.endFill();

            for (var i:int = 0; i < tileNum_X; i += 1)

            {

                gridSprite.graphics.moveTo(i * tile_width, 0);

                gridSprite.graphics.lineTo(i * tile_width, tileNum_Y * tile_height);

            }

            for (i = 0; i < tileNum_Y; i += 1)

            {

                gridSprite.graphics.moveTo(0, i * tile_height);

                gridSprite.graphics.lineTo(tileNum_X * tile_width, i * tile_height);

            }

            

            tileBitmapData.draw(gridSprite);

            

            

        }

        

        private function initPopulation(populationNum:int, randomNum:int):void

        {

            for (var i:int = 0; i < populationNum; i += 1)

            {

                var onePopulation:Array = printRandomNumber(randomNum, randomNum);

                population[i] = new Vector.<int>(randomNum);

                

                for (var j:int = 0; j < randomNum; j += 1)

                {

                    population[i][j] = onePopulation[j];

                }

                //trace(population[i]);

                

                //init Score

                populationScore[i] = evalPopulation(population[i]);

                //trace("population: ", population[i], "score: ", populationScore[i]);

            }

            

            generationNo += 1;

        }

        

        private function evalPopulation(pop:Vector.<int>):int

        {

            var score:int = problemN * problemN;

            

            for (var i:int = 0; i < pop.length - 1; i += 1) //diagonal check - left down, right down

            {

                for (var j:int = i + 1; j < pop.length; j += 1)

                {

                    if (Math.abs(pop[i] - pop[j]) == Math.abs(i - j))

                    {

                        score -= problemN;

                    }

                }

            }

            

            return score;

            

        }

        

        private function printRandomNumber(n:int, k:int) : Array

        {

            var original:Array=[];

            var result:Array=[];

            var i:int;

            var randInt:int;

            var temp:Object;

            

            for(i=0;i<n;i+=1)

            {

                original.push(i);

            }

            

            for(i=0;i<k;i+=1)

            {

                randInt = Math.random()*(n-i) + i;

                temp = original[i];

                original[i] = original[randInt];

                original[randInt] = temp;

                result.push(original[i]);

            }

            

            return result;

        }
    }
}