Update: Doug showed me a fast algorithm that does the trick. It doesn't use recursion. For an nxn board, the algorithm counts the possibilities given a knight in each of these regions:
1. The central (n-4)x(n-4) sub-board2. The squares bordering this central sub-board but excluding the four "corners" where the row and column squares intersect3. The edge squares adjacent to the ones in #24. The four "corners" excluded in #2 that are one square diagonal from each of the four corners of the nxn board5. The eight edge squares adjacent to the four corners of the nxn board6. The four corners of the nxn board
Sum these and divide by two (because the two knights are interchangeable) and you can calculate the solution very quickly for any nxn. Mapping this over [1..n] will provide the required output. My takeaway from this is that using the solution to case n-1 in order to solve case n may not be the most efficient way to do things. Sometimes just solving for case n from scratch is faster.
Thanks Doug.
Julian
On Sunday, June 28, 2020, 09:00:53 AM PDT, Julian Ong
I'm currently stuck on the Two Knights problem.
Having placed one knight on the board, in how many places can you put the other? Doug McIlroy