If we are interested in calculating solutions of large dimensions we can use the following randomized algorithm.
#include
#include
#include
#define MAXDIM 128
typedef struct {
int n;
int placed[MAXDIM];
int seq[MAXDIM];
int col;
} state, *stateptr;
void compute(stateptr st, int pf, int *cptr)
{
if(st->col == st->n){
if(pf){
for(int rind=0; rind < st->n; rind++){
for(int cind=0; cind < st->n; cind++){
char m = (st->placed[cind] == rind ? '*' : '.');
putchar(m);
}
putchar('\n');
}
putchar('\n');
}
(*cptr)++;
return;
}
for(int nxt=0; nxt< st->n; nxt++){
int admit = 1;
for(int cind=0; cind < st->col; cind++){
if(st->placed[st->seq[cind]] == nxt)
admit = 0;
if(st->placed[st->seq[cind]] + st->seq[cind] ==
nxt + st->seq[st->col])
admit = 0;
if(st->placed[st->seq[cind]] - st->seq[cind] ==
nxt - st->seq[st->col])
admit = 0;
}
if(admit){
st->placed[st->seq[st->col]] = nxt;
st->col++;
compute(st, pf, cptr);
st->col--;
}
}
}
int main(int argc, char **argv)
{
unsigned int seed = 0;
int n = 8;
int print = 0;
if(argc>=2){
sscanf(argv[1], "%d", &n);
if(n<1 || n>MAXDIM){
fprintf(stderr, "dims out of range, got %d\n", n);
exit(-1);
}
}
if(argc>=3){
if(!strcmp(argv[2], "yes")){
print = 1;
}
else if(!strcmp(argv[2], "no")){
print = 0;
}
else{
fprintf(stderr, "print flag either yes/no\n");
exit(-2);
}
}
if(argc>=4){
sscanf(argv[3], "%d", &seed);
}
if(argc>=5){
fprintf(stderr, "usage: %s \n", argv[0]);
exit(-3);
}
srand(seed);
state st; st.n = n; st.col = 0;
int pos;
for(pos=0; pos0; pos--){
int exch = rand() % (pos+1);
int tmp = st.seq[pos];
st.seq[pos] = st.seq[exch];
st.seq[exch] = tmp;
}
for(pos=0; pos0) putchar(' ');
printf("%d", st.seq[pos]);
}
putchar('\n');
int count = 0;
compute(&st, print, &count);
printf("total %d solutions found\n", count);
}
This will find e.g. the following $48\times 48$ board:
.....*..........................................
..................................*.............
...............................*................
.................................*..............
.......*........................................
.............*..................................
....*...........................................
........................*.......................
.............................*..................
..............................................*.
.....................................*..........
.......................................*........
..............*.................................
.................*..............................
..........*.....................................
........*.......................................
...........*....................................
...........................*....................
.*..............................................
.........................................*......
................................*...............
....................................*...........
...................*............................
..............................*.................
...........................................*....
..........................*.....................
....................*...........................
...............................................*
............................................*...
........................................*.......
..................*.............................
.............................................*..
......................*.........................
......*.........................................
.........................*......................
...................................*............
..........................................*.....
............*...................................
..*.............................................
......................................*.........
...*............................................
.......................*........................
................*...............................
............................*...................
.....................*..........................
*...............................................
...............*................................
.........*......................................
Here is a $64\times 64$ board:
.*..............................................................
.......................................................*........
...............................................*................
..........................*.....................................
..............*.................................................
.......*........................................................
.............................................*..................
......*.........................................................
..............................................*.................
...............*................................................
.............................................................*..
.........................................................*......
..*.............................................................
..................*.............................................
.................................................*..............
.............*..................................................
.........*......................................................
.....................*..........................................
................................*...............................
................*...............................................
...*............................................................
..................................*.............................
......................*.........................................
..............................*.................................
...................................*............................
....................*...........................................
.................*..............................................
...........................................*....................
..................................................*.............
......................................*.........................
............................................................*...
...................................................*............
........................................*.......................
....................................................*...........
.......................*........................................
.....................................................*..........
............*...................................................
....*...........................................................
..............................................................*.
...................*............................................
*...............................................................
............................*...................................
...............................................................*
...............................*................................
...........................................................*....
.......................................*........................
..........................................................*.....
.................................*..............................
............................................*...................
...........................*....................................
...........*....................................................
........................*.......................................
........*.......................................................
........................................................*.......
.............................*..................................
....................................*...........................
..........*.....................................................
.........................................*......................
.....................................*..........................
.....*..........................................................
..........................................*.....................
.........................*......................................
......................................................*.........
................................................*...............
And to conclude, an example of a $100\times 100$ board:
...........................................................*........................................
.........................................................................................*..........
..................................................................................................*.
......................................................................*.............................
...............................................*....................................................
.............*......................................................................................
....................*...............................................................................
...................................................................*................................
...........*........................................................................................
...............*....................................................................................
....................................................*...............................................
.....................*..............................................................................
.................*..................................................................................
..................................................*.................................................
..........................................................................................*.........
......................................................*.............................................
..................*.................................................................................
........*...........................................................................................
.....*..............................................................................................
..........................*.........................................................................
....................................*...............................................................
.......................................................................*............................
..........................................*.........................................................
................................................................*...................................
.......*............................................................................................
...*................................................................................................
.....................................................*..............................................
.................................................................................................*..
.............................................................*......................................
...................................................................................*................
.........................*..........................................................................
..................................................................................*.................
.................................*..................................................................
..............*.....................................................................................
........................................................................*...........................
....................................................................................*...............
................................*...................................................................
.........................................................................*..........................
...........................................................................................*........
......................................*.............................................................
.....................................................................*..............................
..................................*.................................................................
........................*...........................................................................
............................................................*.......................................
.........................................................*..........................................
................*...................................................................................
....*...............................................................................................
.......................................................................................*............
..............................................*.....................................................
.....................................*..............................................................
..............................................................................*.....................
...................................................................................................*
...........................................................................*........................
........................................................................................*...........
..................................................................*.................................
...........................*........................................................................
................................................................................*...................
...................................................*................................................
......................*.............................................................................
........................................................*...........................................
............................................................................................*.......
............................................................................*.......................
.............................................................................................*......
.........*..........................................................................................
......*.............................................................................................
........................................*...........................................................
.............................................*......................................................
...................................*................................................................
...............................................................................*....................
...............................................................................................*....
..............................................................*.....................................
.......................................................*............................................
.................................................*..................................................
...........................................*........................................................
..........................................................................*.........................
................................................*...................................................
.....................................................................................*..............
................................................................................................*...
............................................*.......................................................
............................*.......................................................................
...................*................................................................................
..........*.........................................................................................
..........................................................*.........................................
...............................................................*....................................
.*..................................................................................................
............*.......................................................................................
..*.................................................................................................
..............................*.....................................................................
.............................................................................*......................
.............................*......................................................................
..............................................................................................*.....
.......................*............................................................................
.......................................*............................................................
*...................................................................................................
...............................*....................................................................
.................................................................................*..................
......................................................................................*.............
.........................................*..........................................................
.................................................................*..................................
....................................................................*...............................