Talk:N-queens minimum and knights and bishops: Difference between revisions

← Older edit

Talk:N-queens minimum and knights and bishops (view source)

Revision as of 18:16, 13 May 2022

2,420 bytes added , 2 years ago

→‎Simple solution for bishops: more optimisations

Petelomax

7,795

edits

Revision as of 14:43, 11 May 2022 (view source) Petelomax (talk \| contribs) (→‎Performance note: added summary of Phix algorithm.) ← Older edit		Latest revision as of 18:16, 13 May 2022 (view source) Petelomax (talk \| contribs) (→‎Simple solution for bishops: more optimisations)
(13 intermediate revisions by 3 users not shown)
Line 20: == Performance note == One thing I have found so far is that <code>integer m=1; while not solveable(m) do m+=1 end while</code> is at least five times faster than finding "any solution" and then exhaustively eliminating the existence of anything better. Since it takes my current approach(/that^) around 15 mins (3 mins with cheat below) to solve, I'm currently writing a GUI version so you can at least explore (eg) the 8x8 solutions while it is still cranking on with the 10x10s in the background. <del>If you (cheat) and set m to the right answer to start with it is five times faster again. I might yet go hybrid, as in cheat first, then prove.</del> --[[User:Petelomax\|Pete Lomax]] ([[User talk:Petelomax\|talk]]) 01:03, 24 April 2022 (UTC) :As usual with Nigel's tasks, the difficulty is not so much finding a way to do them but finding a reasonably quick and efficient way. If he's having to resort to sophisticated stuff like the now deprecated Microsoft.SolverFoundation for his own F# solution, then I suppose that's telling you something. Line 32: ::Actually that cheat I mentioned isn't needed or particularly helpful (when paired off with a prove chaser that is), but glad I tried it as it lead to a quite helpful and probably obvious optimisation: if you can't solve a 7x7 board with 6 bishops, no point trying to solve an 8x8 with only 6. There's also "first bishop must be on the main diagonal", and again obviously if there is no answer up to the mid-point, there will not be one after. --[[User:Petelomax\|Pete Lomax]] ([[User talk:Petelomax\|talk]]) 09:36, 24 April 2022 (UTC) :::I am thinking about to use a good strategy of finding the next possible place for a token like [[Spiral_matrix#Phix]].<br> Starting in the middle at the highest number and checking next possible places along the spiral backwards.This should place the next token Q,B,K in a way, that they maximize the attacked places.<br>Hopefully an optimal solution with the lowest count of tokens is found this way faster, to stop search as soon as possible, if number of token exceeds this number. --[[User:Horsth\|Horsth]] ([[User talk:Horsth\|talk]]) 16:46, 26 April 2022 (UTC) ::::I suppose I should summarise my approach. Within an as above mentioned while m++ loop, find all moves which either occupy or attack {1,1}. Then, for each of those moves, keeping within m total moves, scan [from {1,2} forward] for the first unoccupied and unattacked square, again find all suitable moves, and obviously mark solved/save answer/stop if no such squares found, and abandoning m once all moves for {1,1} have been tried. Basically recursive, but I use an explicit stack (or 30) to make it iterative/re-entrant/GUI compatible. Each such recursive call, for the kth of at most m moves, only ever contemplates the moves for just the ''one'' first needed square. --[[User:Petelomax\|Pete Lomax]] ([[User talk:Petelomax\|talk]]) 14:40, 11 May 2022 (UTC) == Simple solution for bishops == 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) ::Applied the suggested optimisations to the Phix entry (many thanks!): ::Confining bishops to middle column drops that to 0s. (Likewise you could confine rooks to the main diagonal.) ::First queen on a 10x10 now limited to 9 places (was 28), first knight for n>=3 now limited to 2 places (was 3). ::Time for all solutions to 10x10 dropped from 12 mins to 3 mins (almost all being 10N examining 21,801,024 positions). --[[User:Petelomax\|Pete Lomax]] ([[User talk:Petelomax\|talk]]) 14:12, 11 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)