
5 вроде место в 90
![]() | Вы читаете журнал Вход Создать аккаунт в ЖЖ Подробности |





The eight queens puzzle is the problem of putting eight chess queens on an 8×8 chessboard such that none of them is able to capture any other using the standard chess queen's moves. The colour of the queens is meaningless in this puzzle, and any queen is assumed to be able to attack any other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens puzzle of placing n queens on an n×n chessboard.
class memberTypeКонструктор заполняет главную диагональ, а затем случайным образом перемешивает королев.
{
public int[] solution = new int[Program.MaxLength];
public float energy;
// Меняем положение коней из двух случаных столбцов местами.
public void TweakSolution()
{
int temp, x, y;
Random rnd = new Random();
x = rnd.Next(Program.MaxLength);
do
{
y = rnd.Next(Program.MaxLength);
}
while (x == y);
temp = this.solution[x];
this.solution[x] = solution[y];
this.solution[y] = temp;
}
public memberType()Дальше - больше :D. Энергия решения считается как количество конфликтов между королевами.
{
for (int i = 0; i < Program.MaxLength; i++)
{
solution[i] = i;
}
for (int i = 0; i < Program.MaxLength; i++)
{
TweakSolution();
}
}
public void ComputeEnergy()И последняя функция в классе решения просто выводит на экран оное.
{
int i, j, x, y, tempx, tempy, conflicts;
char [,]board = new char[Program.MaxLength,Program.MaxLength];
int[] dx = { -1, 1, -1, 1 };
int[] dy = { -1, 1, 1, -1 };
for (i = 0; i < Program.MaxLength; i++)
{
board[i,solution[i]] = 'Q';
}
conflicts = 0;
for ( i = 0; i < Program.MaxLength; i++)
{
x = i;
y = solution[i];
for ( j = 0; j < 4; j++)
{
tempx = x; tempy = y;
while (true)
{
tempx += dx[j];
tempy += dy[j];
if ((tempx < 0) || (tempx >= Program.MaxLength) || (tempy < 0) || (tempy >= Program.MaxLength))
break;
if (board[tempx,tempy] == 'Q') conflicts++;
}
}
}
energy = (float)conflicts;
}
public void emit()Теперь кульминация балета :D.
{
int MaxLength = Program.MaxLength;
char[,] board = new char[MaxLength, MaxLength];
int x, y;
for (x = 0; x < MaxLength; x++)
{
board[x, this.solution[x]] = 'Q';
}
for (y = 0; y < MaxLength; y++)
{
for (x = 0; x < MaxLength; x++)
{
if (board[x, y] != 'Q')
Console.Write(". ");
else
Console.Write("Q ");
}
Console.Write('\n');
}
Console.Write('\n');
}
}
class ProgramДо тех пор пока температура больше конечной выполняется алгоритм Metropolis Monte Carlo.
{
public static int MaxLength = 20; \\ размер доски
public static float InitialTemperature = 30.0f; \\ начальная температура
public static float FinalTemperature = 0.5f; \\ конечная температура
public static float Alpha = 0.99f; \\ во сколько раз уменьшается температура
public static int StepsPerChange = 100; \\ число итераций для каждого значения температуры
static void Main(string[] args)
{
int timer = 0, step, solution = 0, useNew, accepted;
float temperature = InitialTemperature;
memberType current, working, best;
StreamWriter Strw = new StreamWriter("strw");
Random rnd = new Random();
current = new memberType();
current.ComputeEnergy();
best = new memberType();
best.energy = 100.0f;
working = current;
T=Alpha*TИ в файл выводятся значения температуры, энергий и шага итерации.
while (temperature > FinalTemperature)В конце на экран выводится лучшее решение.
{
Console.WriteLine("Temperature: " + temperature);
accepted = 0;
for (step = 0; step < StepsPerChange; step++)
{
useNew = 0;
working.TweakSolution();
working.ComputeEnergy();
if (working.energy <= current.energy)
{
useNew = 1;
}
else
{
float test = (float)rnd.NextDouble();
float delta = working.energy - current.energy;
float calc = (float)Math.Exp(-delta / temperature);
if (calc > test)
{
accepted++;
useNew = 1;
}
}
if (useNew == 1)
{
useNew = 0;
current = working;
if (current.energy < best.energy)
{
best = current;
solution = 1;
}
else
{
working = current;
}
}
}
Strw.WriteLine("timer:" + timer++ + " Temperature:" + temperature +
" Best Energy: " + best.energy + " Accepted: " + accepted);
temperature *= Alpha;
}
Strw.Close();
if (solution == 1)
best.emit();
return;
}
}
}