Back in the day BYTE magazine had a puzzle contest - solve the 8-queens problem and find all the solutions.
As a kid, it seemed obvious to me that a good model was the digits 1 through 8, representing the row that a queen would be in. Doing a recursive backtracker on an ordering of the digits and testing each pair for diagonal (digit i minus digit j was equal to +/- i-j) and my BASIC program spit out the solutions in twenty minutes.
I didnt enter the contest because I figured everybody would do that. Turns out when the editor published the 'best' solutions, they all, every single one, modeled the board as an 8 by 8 array and ran around following diagonals iteratively. And took hours to complete.
Anyway, choosing a good solution model is most of the problem solved.
That's very cool. I don't quite understand your solution, are you saying that because you used the i:j relationship as a constant it meant you only needed to store positions rather than a whole board? I've never been interested in 8-queens but I'm keen to play with it now
Yeah, the key is in how you model it. It's not a chessboard with 64 squares you need to fill some of, it's a permutation of 8 numbers, the location of the one queen in that row.
You still need to get the backtracking correct and there's some minor tricks to work out, but that'll get you up to n=8 working quite well.
To be clear, the digit at position i is the row number of the queen in column i.
So 12345678 is every queen along the diagonal (clearly not a solution).
The model (8 different digits representing row in that column) no queen was in the same row or column, by construction. So only the diagonal test remains.
JoeAltmaier · · focus · HN ↗
As a kid, it seemed obvious to me that a good model was the digits 1 through 8, representing the row that a queen would be in. Doing a recursive backtracker on an ordering of the digits and testing each pair for diagonal (digit i minus digit j was equal to +/- i-j) and my BASIC program spit out the solutions in twenty minutes.
I didnt enter the contest because I figured everybody would do that. Turns out when the editor published the 'best' solutions, they all, every single one, modeled the board as an 8 by 8 array and ran around following diagonals iteratively. And took hours to complete.
Anyway, choosing a good solution model is most of the problem solved.
anitil · · focus · HN ↗
kadoban · · focus · HN ↗
You still need to get the backtracking correct and there's some minor tricks to work out, but that'll get you up to n=8 working quite well.
anitil · · focus · HN ↗
JoeAltmaier · · focus · HN ↗
The model (8 different digits representing row in that column) no queen was in the same row or column, by construction. So only the diagonal test remains.