[Haskell-beginners] CSES programming problems at https://cses.fi/problemset/ [Two Knights]

[Julian Ong]

 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 <julian_ong at yahoo.com> wrote:  
 
 There are 8 possibilities and then you can filter them by column and row values depending on the region of the board you’re interested in.

Julian

On Jun 28, 2020, at 8:26 AM, Doug McIlroy <doug at cs.dartmouth.edu> wrote:


> 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
  
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20200630/b3fa6da9/attachment.html>