Re: Prolog Knight's Tour

"david.andrew.matthews@xxxxxxxxx" <david.andrew.matthews@xxxxxxxxx> writes:

My sincerest thanks.

That's all? :-) What about a few improvements:

We have:

?- profile(tour(30)).
....
=====================================================================
Total time: 3.84 seconds
=====================================================================
Predicate Box Entries = Calls+Redos Time
=====================================================================
lists:delete/3 404,550 = 404,550+0 41.2%
lists:member/2 814,146 = 406,348+407,798 29.2%
$garbage_collect/1 5 = 5+0 18.1%
delete_from_all/3 899 = 899+0 6.0%
memberchk/2 900 = 900+0 2.1%
....


People caring about efficiency could:

1) make one of the calls to delete/3 depend on a condition that can be
checked -- in O(1) -- with a predicate that's already there,
without changing the program's results

2) WOLOG replace member/2 with memberchk/2 at one (important) place

to obtain a faster version with little effort. People wanting a more
concise solution can replace enumerate/3 with an SWI Prolog built-in
predicate.


With an improved version, I obtain:

?- profile(tour(30)).
....
=====================================================================
Total time: 2.45 seconds
=====================================================================
Predicate Box Entries = Calls+Redos Time
=====================================================================
$garbage_collect/1 5 = 5+0 25.5%
valid_move_/2 1,666,722 = 404,551+1,262,171 17.2%
memberchk/2 404,550 = 404,550+0 15.6%
lists:delete/3 3,248 = 3,248+0 10.0%
delete_from_all/3 402,201 = 899+401,302 10.0%
lists:nth_gen/4 900 = 900+0 9.0%
lists:member/2 406,348 = 1,798+404,550 4.9%
succ/2 404,550 = 404,550+0 3.3%
=/2 411,206 = 411,206+0 2.0%
....

Show what you can.

Best wishes! -- Markus
.