Talk:N-queens minimum and knights and bishops: Difference between revisions
Talk:N-queens minimum and knights and bishops (view source)
Revision as of 18:16, 13 May 2022
, 2 years ago→Simple solution for bishops: more optimisations
m (→Performance note: <del>'d my cheat remark) |
(→Simple solution for bishops: more optimisations) |
||
| (10 intermediate revisions by 3 users not shown) | |||
Line 98:
: Any ideas on how the performance of the Wren solution could be improved? I've tried a number of things but (apart from improving the diagonal checking) no joy so far. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 17:11, 25 April 2022 (UTC)
::My suggestion would be to save i,j at <code>allAttacked = false</code>, then test <code>if that square or attacks it</code>. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 15:37, 11 May 2022 (UTC)
:: *I've added Go now. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 18:16, 25 April 2022 (UTC)
::: As I'm sure you noticed, I've improved that. Feel free to make the needed tweaks and merge/replace original. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 15:14, 12 May 2022 (UTC)
:::: Hi Pete. Many thanks for doing that which is working great. It's a little faster on my machine (core i7) at 32.6 seconds for 9 bishops and 128 seconds for 10. I'll incorporate the changes into the original Go version and also into the Wren version when I have more time.
::::Do you think it's worth even bothering with bishops when we know from general reasoning that the answer will be 'n' for an 'n x n' board and its trivial to construct an example?
:::::Well, yeah, of course it is, though I'll grant you not very exciting. Simply only ever place bishops in the middle column, either by testing for that or even better yet changing the column loop. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 00:39, 13 May 2022 (UTC)
::::Incidentally, I'm working on a GLPK wrapper for Wren as I'd like to have something in the LP/MIP solver area which can at least solve 'small' problems relatively quickly. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 17:45, 12 May 2022 (UTC)
::Found a cheeky little trick (aka a circumstantial optimisation) which made the tricky 10N only examine 8,163,658 positions, and the total time dropped to 1 min 20s, plus I resurrected cheat mode since that now drops it to 8.3s all in up to 10x0. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 18:16, 13 May 2022 (UTC)
==Some Observations==
Line 234 ⟶ 245:
</pre>
So I conclude that this task for knights is feasible without a solver, in fact it beats the solver. The code for the above is ,as yet, far from optimal, so I expect better timings. I stop at 9 because I run out of memory, but solving that is just programming.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 14:27, 8 May 2022 (UTC)
: I have replaced the solver with F# code and timings for knights up to 10. I am a little disappointed with 4minutes and 45seconds for 10 as that doesn't beat the solver(YET!). Otherwise 1/4 second for 8 is good enough.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 10:19, 12 May 2022 (UTC)
:: You're now also up against a Go entry that manages 10 knights in 49s on a ten year old box. 😜 --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 15:23, 12 May 2022 (UTC)
| |||