Известная задача о ферзях и простой алгоритм.
#include <stdio.h>
#include <time.h>
int board[32], count;
int can_place(int row,int col) {
int i = 1;
while((i < row) && (board[i] != col) && (abs(board[i]-col) != abs(i-row))) ++i;
return (i == row);
}
void queen(int row,int n) {
int col;
for(col=1; col<=n; ++col) {
if(can_place(row,col)) {
board[row] = col;
if(row==n) ++count; else queen(row+1, n);
}
}
}
void solve(int n) {
count = 0;
queen(1,n);
}
int main(int argc, char **argv) {
int N;
clock_t starttime, endtime; float runtime;
N = 13;
if (argc == 2) N = atoi(argv[1]);
printf("Solving %d Queens Problem ... \n", N );
starttime = clock();
solve(N);
endtime = clock();
runtime = (endtime-starttime)/1000.0;
printf(" %d solutions found, t = %f \n", count, runtime );
return 0;
}
Запускал на разных компьютерах и усреднял относительное время среднепотолочно. За попугая принято время выполнения на BlackBox.
Разные компиляторы от ETH дали сравнимые результаты: 80-90%.
Oberon-07 от akron1 - 40%.
Oxford oberon - 40%, а с выключенным JIT всего 6%.
XDS - 100%, с оптимизацией и отключением проверок - 170%.
Компиляторы С без оптимизации 50-90%, но это неинтересно.
Лучший результат у clang - 220%.
Потом идет PellesC - 200%.
GCC и старенький Watcom - по 160%.
lcc немного не дотянул - 90%.
TinyC - 50%.
JavaScript от гугла (V8): 100%,от мозиллы: 70%, и просто для интереса, JavaScript без JIT: от 5 до 20%.
LuaJit: 75%, просто Lua 4%.