Comment by HarHarVeryFunny
4 hours ago
What's the logic for putting the initial queen in a corner rather than using the same heuristic as for the remaining places?
4 hours ago
What's the logic for putting the initial queen in a corner rather than using the same heuristic as for the remaining places?
I was wondering that too. One would think that with a greedy approach, 1 square diagonally from the corner would be better. (But that doesn't work as well.)
Idk but here’s more reading https://en.wikipedia.org/wiki/Mathematical_chess_problem#Dom...
The only ones of these I've tried before (on an old 8-bit computer, where the challenge was to keep runtime acceptable) are the knight's tour and the 8-queens "independence" (no co-attacking) problems.
For the knight's tour all you need is a simple heuristic, consistently applied, of doing the hardest bits first - visiting the next square that has fewest remaining squares that lead to it, meaning that you start in a corner. This is what has me wondering about the puzzle/heuristic being discussed where the first placement is using a different heuristic.
On a slow computer the trick to a fast 8-queens solution is to recognize that a minimal constraint is that the queens need to all be on different rows and columns, so you can start by using an efficient permutation algorithm to generate permutations of {1, 2, .. 8} (corresponding to column placement of queen on n'th row), then just check the diagonals of this reasonable number of candidates.