In the past I've posted a few demonstrations of recursion using Flowcode see https://www.flowcode.co.uk/mmforums/vie ... ode#p91525
So - a recursive problem that actually needs a little more work to solve in a reasonable time. I initially thought this would be a 'fun' benchmark....
The Knight's tour is an established programming problem see https://en.wikipedia.org/wiki/Knight%27s_tour - and a recursive solution rapidly gets a 'little' unwieldy. So there is a heuristic (a technique that reduces the number of calls but doesn't always guarantee a solution) known as Warnsdorf's Heuristic. Using this the esp32 can solve a Knight's tour for a 45 x 45 chess board and the Arduino version here happily solves for 10 x 10.
It is slightly odd - for a start position of (0, 0) - the program never backtracks using the heuristic (I experimented with a version that stored all possible moves and also, as here - only a single minimum move)
It is extremely greedy on stack usage - for the esp32 I had to set the stack size to 120000 for a 45 x 45 board
(To increase the stack size - use idf.py menuconfig - component config - main task stack size. I also optimised code for size though this may or may not affect the size of the stack frame)The Arduino takes 315 seconds to recursively solve a 7 x 7 tour - the esp32 does it in 18s (18650ms) The esp32 - has a small 'kludge' - every 1000000 recursive calls it has a 10ms delay to stop wdt issues. Using the heuristic it takes a few ms (on the esp32) even for larger boards.
It also runs in simulation - warning of stack overflow at 13 x 13 (although you can continue...)
It would be good to output the 'search' or completed tour on a display?
Martin