The code works fine, however, i am unable to optimize it such that i'll solve case n=13 in under a second.
Perhaps there's a different algorithm I could use? Or, some one to optimize the recursion? gprof says that ~40% of the time is being used in the function canPlace() and ~40-50% in solve2()
Code: Select all
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
//the board representation
static unsigned int rows[14] = {0};
static unsigned int diagonal[29] = {0};
static unsigned int odiagonal[29] = {0};
static unsigned int board[14] = {0};
static unsigned int solutions[3][14];
static unsigned int count = 0;
static unsigned int total=0;
inline void mark(unsigned int col,unsigned int i)
{
rows[i] = 1;
diagonal[total + col - i] = 1;
odiagonal[col + i - 1] = 1;
}
inline void clear(unsigned int col,unsigned int i)
{
rows[i] = 0;
diagonal[total + col - i] = 0;
odiagonal[col + i - 1] =0;
}
inline void print()
{
memmove(solutions[count], board, sizeof(int) * (total + 1));
}
inline bool canPlace(unsigned int column, unsigned int i)
{
return (rows[i] == 0 && diagonal[total + column - i] == 0 && odiagonal[column + i -1] == 0);
}
inline void solve2(unsigned int column)
{
unsigned int i;
for(i = 1; i <= total; ++i)
{
if(canPlace(column, i))
{
if(column == total)
{
board[column] = i;
if(count <3)
{
print();
}
++count;
board[column]=0;
}
else
{
board[column] = i;
mark(column, i);
solve2(column + 1);
clear(column, i);
board[column] = 0;
}
}
}
}
inline void outputSolutions()
{
unsigned int i,j;
FILE* fout = fopen("checker.out", "w+");
for(i = 0; i < 3; ++i)
{
for(j = 1; j <= total; ++j)
{
if(j != total)
fprintf(fout, "%d ", solutions[i][j]);
else
fprintf(fout, "%d", solutions[i][j]);
}
fprintf(fout, "\n");
}
fprintf(fout, "%d\n", count);
}
int main()
{
FILE* blah = fopen("checker.in", "r");
unsigned int d;
fscanf(blah, "%d", &d);
total = d;
solve2(1);
outputSolutions();
}
Is there really such a good algorithm or should I believe that they have pre-calculated & printed the answer for n = 13 ? 