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.
/**
* 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;
}
}
}