1

For fun I've been attempting to write a Knight's Tour (https://en.wikipedia.org/wiki/Knight%27s_tour) solver in gprolog using Warnsdorf's rule.

I found another SO post asking about efficiency that provided a solution in B-prolog: knight's tour efficient solution.

My problem arises with the following section:

:- table warnsdorff(+,+,+,+,+,-,-,min).
warnsdorff(R, C, X, Y, Visits, NewX, NewY, Score) :-
    possible_knight_moves(R, C, X, Y, Visits, NewX, NewY),
    possible_moves_count(R, C, NewX, NewY, [(NewX, NewY) | Visits], Score).

B-prolog features tabled predicates and gprolog does not. I'm having a great deal of difficulty trying to translate the table section to gprolog. In practice, the function is supposed to return the move from the current position that results in the least number of possible moves from the new position (ties are chosen at random).

Any help would be greatly appreciated. Cheers!

smci
  • 32,567
  • 20
  • 113
  • 146
Knight Artorias
  • 105
  • 1
  • 6
  • 1
    Ask Dr. Google about "knight's tour prolog". There are many solutions. – false Apr 25 '17 at 09:35
  • "for fun" similar questions starting to swarm are making me think this is an asignment (see http://stackoverflow.com/questions/43622353/gprolog-knights-tour-using-warnsdorffs-rule and http://stackoverflow.com/questions/43628413/simulating-knight-movement-using-prolog) – Rafalon Apr 26 '17 at 08:23

1 Answers1

1

Probably, tabling is overkill for this problem. Since the Visits lists already is carried on while solving, just use memberchk/2. I get this solution in SWI-Prolog (where, BTW, tabling is implemented, but fails to solve the puzzle using the original coding you linked to):

?- time(knight(8, 8, 1, 1, [], Path))...
% 19,973 inferences, 0.019 CPU in 0.019 seconds (100% CPU, 1047591 Lips)
[(1,1),(2,3),(1,5),(2,7),(4,8),(6,7),(8,8),(7,6),(6,8),(8,7),(7,5),(8,3),(7,1),(5,2),(3,1),(1,2),(2,4),(1,6),(2,8),(3,6),(1,7),(3,8),(5,7),(7,8),(8,6),(7,4),(8,2),(6,1),(4,2),(2,1),(1,3),(3,2),(5,1),(6,3),(8,4),(7,2),(5,3),(4,1),(2,2),(1,4),(3,3),(2,5),(4,4),(6,5),(4,6),(3,4),(5,5),(4,3),(6,2),(8,1),(7,3),(5,4),(3,5),(4,7),(2,6),(1,8),(3,7),(4,5),(6,4),(5,6),(7,7),(5,8),(6,6),(8,5)]

If you want, I can show you the Warnsdorff rule. I've used setof/3, to get the minimum count, joining possible_knight_moves/7 and possible_moves_count/6.

edit

as required:

warnsdorff(R, C, X, Y, Visits, NewX_, NewY_) :-
    setof((Count, NewX, NewY), (
              possible_knight_moves(R, C, X, Y, Visits, NewX, NewY),
              possible_moves_count(R, C, NewX, NewY, [(NewX, NewY) | Visits], Count)
          ), [(_, NewX_, NewY_)|_]).

For clarity, I've renamed the output variables NewX_, NewY_, but that's irrelevant - it worked with the original naming as well.

CapelliC
  • 59,646
  • 5
  • 47
  • 90
  • I agree, but it does make the code a lot simpler. If you could show your Warnsdorff rule that would be appreciated. I can't quite figure out what you used as the goal in your setoff/3. – Knight Artorias Apr 25 '17 at 08:52
  • Ah that's rather simple. I suppose trying to think in Prolog at 2 in the morning was not the way to go. I'm having strange issues where possible_knight_moves/7 returns 'no' when the not clause (\+memberchk((NewX, NewY), Visits)) is given a NewX and NewY that is already in the list. It gets about 15 iterations in before this occurs. Did you modify any other sections? – Knight Artorias Apr 25 '17 at 18:52
  • Correction: it fails because it can't find another move to make. My previous comment didn't make any sense anyways. – Knight Artorias Apr 25 '17 at 20:09