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:
...........................................................*........................................ .........................................................................................*.......... ..................................................................................................*. ......................................................................*............................. ...............................................*.................................................... .............*...................................................................................... ....................*............................................................................... ...................................................................*................................ ...........*........................................................................................ ...............*.................................................................................... ....................................................*............................................... .....................*.............................................................................. .................*.................................................................................. ..................................................*................................................. ..........................................................................................*......... ......................................................*............................................. ..................*................................................................................. ........*........................................................................................... .....*.............................................................................................. ..........................*......................................................................... ....................................*............................................................... .......................................................................*............................ ..........................................*......................................................... ................................................................*................................... .......*............................................................................................ ...*................................................................................................ .....................................................*.............................................. .................................................................................................*.. .............................................................*...................................... ...................................................................................*................ .........................*.......................................................................... ..................................................................................*................. .................................*.................................................................. ..............*..................................................................................... ........................................................................*........................... ....................................................................................*............... ................................*................................................................... .........................................................................*.......................... ...........................................................................................*........ ......................................*............................................................. .....................................................................*.............................. ..................................*................................................................. ........................*........................................................................... ............................................................*....................................... .........................................................*.......................................... ................*................................................................................... ....*............................................................................................... .......................................................................................*............ ..............................................*..................................................... .....................................*.............................................................. ..............................................................................*..................... ...................................................................................................* ...........................................................................*........................ ........................................................................................*........... ..................................................................*................................. ...........................*........................................................................ ................................................................................*................... ...................................................*................................................ ......................*............................................................................. ........................................................*........................................... ............................................................................................*....... ............................................................................*....................... .............................................................................................*...... .........*.......................................................................................... ......*............................................................................................. ........................................*........................................................... .............................................*...................................................... ...................................*................................................................ ...............................................................................*.................... ...............................................................................................*.... ..............................................................*..................................... .......................................................*............................................ .................................................*.................................................. ...........................................*........................................................ ..........................................................................*......................... ................................................*................................................... .....................................................................................*.............. ................................................................................................*... ............................................*....................................................... ............................*....................................................................... ...................*................................................................................ ..........*......................................................................................... ..........................................................*......................................... ...............................................................*.................................... .*.................................................................................................. ............*....................................................................................... ..*................................................................................................. ..............................*..................................................................... .............................................................................*...................... .............................*...................................................................... ..............................................................................................*..... .......................*............................................................................ .......................................*............................................................ *................................................................................................... ...............................*.................................................................... .................................................................................*.................. ......................................................................................*............. .........................................*.......................................................... .................................................................*.................................. ....................................................................*...............................