chess queens problem

Which would be the fastest algorithm to solve the chess queens problem (8 queens on a chessboard not to attack one another)?

) Which would be the fastest algorithm to solve the chess queens problem ) (8 queens on a chessboard not to attack one another)?

Hardcoded database algorithm.

In other words, take the solutions from somewhere and hardcode them into the program.



SaSW, Willem (at stack dot nl)

Given that each placed queen eliminates MANY spaces, I'd say a brute-force algorithm will probably work best. You know there has to be 1 queen in each rank, so 7 nested loops (from 1 to 8) will do this, each variable tracking the column of one of the first 7 queens. Checking files is trivial (if any two variables are the same, they queens are in the same file). For diagonals, if the file difference (in absolute value) euqals the rank difference, they are in the same diagonal. Actually, due to symmetry, the outermost loop (or, the loop for any given queen) only has to go from 1 to 4, not 1 to 8.

[SPOILER]

I claim that the next algorithm, (written in C++) is the fastest to give all the solution of the chess queens problem. (correction at line 10)

// 8 chess queens solution: // 8 can be changed with N for the general case #include <iostream.h> typedef char val; unsigned n; void intSch (val a[], unsigned k, unsigned n) { val t = a[k]; a[k] = a[n]; a[n] = t;} void showSol (val a[], unsig

I claim that the next algorithm, (written in C++) is the fastest to give all the solution of the chess queens problem. (correction at line 10)

// 8 chess queens solution: // 8 can be changed with N for the general case #include <iostream.h> typedef char val; unsigned n; void intSch (val a[], unsigned k, unsigned n) { val t = a[k]; a[k] = a[n]; a[n] = t;} void showSol (val a[], unsigned n) { for (unsigned j = 1; j &lt;= n; j++) for (unsigned k = 2; k &lt;= j; k++) if ( ( (a[j])-a[k])!=(j-k) )&amp;&amp;( (a[k])-a[j])!=(j-k) ) ) { for (unsigned i = 1; i &lt;= n; i++) {cout &lt;&lt; a[i]; cout &lt;&lt; &#039;n&#039;;} } } void genSol (val a[], unsigned n) { if (!n) showSol (a, ::n); else = t;} void showSol (val a[], unsigned n) { for (unsigned j = 1; j <= n; j++) for (unsigned k = 2; k <= j; k++) if ( ( (a[j])-a[k])!=(j-k) )&&( (a[k])-a[j])!=(j-k) ) ) { for (unsigned i = 1; i <= n; i++) {cout << a[i]; cout << 'n';} } } void genSol (val a[], unsigned n) { if (!n) showSol (a; cout << 'n';} } } void genSol (val a[], unsigned n) { if (!n) showSol (a, ::n); else for (unsigned k = n; k; k

)> Which would be the fastest algorithm to solve the chess queens problem )> (8 queens on a chessboard not to attack one another)? ) [SPOILER] ) ) ) I claim that the next algorithm, (written in C++) is the fastest to give all ) the solution of the chess queens problem. (correction at line 10) ) ) <snip>

I dispute your claim by claiming that the following shell-script is faster than your algorithm:

cat QueenSolutions.txt

(The contents of QueenSolutions.txt are left as an exercise to the reader)

SaSW, Willem (at stack dot nl)

You could use MCris's proggie to prepare the file.

Reminds me of a routine we implemented on a microcode machine without a divide op code, to divide by three:

if input = 384 then return 128 else return result from a load of shifts and subtracts endif

as an input value of 384 was far more popular than any other value, being the standard block size concerned.

I have visited that site and the say their algorithm does a _probabilistic_ local search. My algorithm, as you said, is exhaustive and does NOT imply any probability or even 'try and verify' scheme. By the way, did anyone figured out how it works, or should I explain it? It is rather simple...

That contest is over now and it seems that the final solution for 14 cubic board IS 172.

All the best, Miron Cristea

)> How does your 8x8 exhaustive solver stack against the (almost) constant time )> algorithms at http://www.cit.gu.edu.au/~sosic/nqueens.html for finding )> solutions to large e.g. 10^6 x 10^6 boards? If you have improved upon those )> then I suggest you publish! ) ) I have visited that site and the say their algorithm does a ) _probabilistic_ local search. My algorithm, as you said, is exhaustive

You say that as if a probabilistic search is something bad.

) and does NOT imply any probability or even 'try and verify' scheme. By ) the way, did anyone figured out how it works, or should I explain it? ) It is rather simple...

I looked at it for a coupla seconds, I would say it generates all possible permutations of 1..n, then checks if the diagonals clash and prints out all permutations for which no diagonal collisions occur.

I won't even go into the use of arbitrary constants, or the fact that you're using C++ instead of ordinary C for no reason whatsoever.

By the way, have you ever heard of branch-and-bound ?

SaSW, Willem (at stack dot nl)

Does your program find solutions faster? Exhaustive search is fine if you are searching a space small enough, otherwise other methods need to be used because the search space is too large to find solutions in reasonable time.

You may be surprised to find that many people in this group can not only read your code but improve upon it.
http://members.aol.com/bitzenbeitz/Contests/ AttackingQueens/Descripti...

The point is that for n>=14 the problem was and still is unsolved - no the final solution for n=14 is not 172, the current best known solution is 172 as I stated. The reason it isn't solved is that using the best known exhaustive algorithm, n=14 is expected to take a years cpu to solve and noone has set up the a distributed project yet to do that. Q(3,14)=172 was obtained by heuristic techniques - i.e. not exhaustive, the same argument you used to dismiss the probalistic approach above, so I'm sure you will appreciate it.

The reason I mentioned these projects to you is that if your algorithm/program has promise then it should hold up against the current best programs out there. Further I thought you might be interested in seeing what others have achieved at the cutting edge of algorithm development for these problems.

I must say you seem very quick to dismiss other peoples work in this area. I suggest you take a step back and open yourself up to the possibility that you could actually learn quite a bit by reading and listening to the input from others.

Cheers,