Anonymous user
Knight's tour: Difference between revisions
Undo revision 310918 by Dmcbane (talk)
Line 2,677:
Link to live demo: http://dc25.github.io/knightsTourElm/
=={{header|Erlang}}==
Again I use backtracking. It seemed easier this time.
<lang Erlang>
-module( knights_tour ).
-export( [display/1, solve/1, task/0] ).
display( Moves ) ->
%% The knigh walks the moves {Position, Step_nr} order.
%% Top left corner is {$a, 8}, Bottom right is {$h, 1}.
io:fwrite( "Moves:" ),
lists:foldl( fun display_moves/2, erlang:length(Moves), lists:keysort(2, Moves) ),
io:nl(),
[display_row(Y, Moves) || Y <- lists:seq(8, 1, -1)].
solve( First_square ) ->
try
bt_loop( 1, next_moves(First_square), [{First_square, 1}] )
catch
_:{ok, Moves} -> Moves
end.
task() ->
io:fwrite( "Starting {a, 1}~n" ),
Moves = solve( {$a, 1} ),
display( Moves ).
bt( N, Move, Moves ) -> bt_reject( is_not_allowed_knight_move(Move, Moves), N, Move, [{Move, N} | Moves] ).
bt_accept( true, _N, _Move, Moves ) -> erlang:throw( {ok, Moves} );
bt_accept( false, N, Move, Moves ) -> bt_loop( N, next_moves(Move), Moves ).
bt_loop( N, New_moves, Moves ) -> [bt( N+1, X, Moves ) || X <- New_moves].
bt_reject( true, _N, _Move, _Moves ) -> backtrack;
bt_reject( false, N, Move, Moves ) -> bt_accept( is_all_knights(Moves), N, Move, Moves ).
display_moves( {{X, Y}, 1}, Max ) ->
io:fwrite(" ~p. N~c~p", [1, X, Y]),
Max;
display_moves( {{X, Y}, Max}, Max ) ->
io:fwrite(" N~c~p~n", [X, Y]),
Max;
display_moves( {{X, Y}, Step_nr}, Max ) when Step_nr rem 8 =:= 0 ->
io:fwrite(" N~c~p~n~p. N~c~p", [X, Y, Step_nr, X, Y]),
Max;
display_moves( {{X, Y}, Step_nr}, Max ) ->
io:fwrite(" N~c~p ~p. N~c~p", [X, Y, Step_nr, X, Y]),
Max.
display_row( Row, Moves ) ->
[io:fwrite(" ~2b", [proplists:get_value({X, Row}, Moves)]) || X <- [$a, $b, $c, $d, $e, $f, $g, $h]],
io:nl().
is_all_knights( Moves ) when erlang:length(Moves) =:= 64 -> true;
is_all_knights( _Moves ) -> false.
is_asymetric( Start_column, Start_row, Stop_column, Stop_row ) ->
erlang:abs( Start_column - Stop_column ) =/= erlang:abs( Start_row - Stop_row ).
is_not_allowed_knight_move( Move, Moves ) ->
no_such_move =/= proplists:get_value( Move, Moves, no_such_move ).
next_moves( {Column, Row} ) ->
[{X, Y} || X <- next_moves_column(Column), Y <- next_moves_row(Row), is_asymetric(Column, Row, X, Y)].
next_moves_column( $a ) -> [$b, $c];
next_moves_column( $b ) -> [$a, $c, $d];
next_moves_column( $g ) -> [$e, $f, $h];
next_moves_column( $h ) -> [$g, $f];
next_moves_column( C ) -> [C - 2, C - 1, C + 1, C + 2].
next_moves_row( 1 ) -> [2, 3];
next_moves_row( 2 ) -> [1, 3, 4];
next_moves_row( 7 ) -> [5, 6, 8];
next_moves_row( 8 ) -> [6, 7];
next_moves_row( N ) -> [N - 2, N - 1, N + 1, N + 2].
</lang>
{{out}}
<pre>
17> knights_tour:task().
Starting {a, 1}
Moves: 1. Na1 Nb3 2. Nb3 Na5 3. Na5 Nb7 4. Nb7 Nc5 5. Nc5 Na4 6. Na4 Nb2 7. Nb2 Nc4
8. Nc4 Na3 9. Na3 Nb1 10. Nb1 Nc3 11. Nc3 Na2 12. Na2 Nb4 13. Nb4 Na6 14. Na6 Nb8 15. Nb8 Nc6
16. Nc6 Na7 17. Na7 Nb5 18. Nb5 Nc7 19. Nc7 Na8 20. Na8 Nb6 21. Nb6 Nc8 22. Nc8 Nd6 23. Nd6 Ne4
24. Ne4 Nd2 25. Nd2 Nf1 26. Nf1 Ne3 27. Ne3 Nc2 28. Nc2 Nd4 29. Nd4 Ne2 30. Ne2 Nc1 31. Nc1 Nd3
32. Nd3 Ne1 33. Ne1 Ng2 34. Ng2 Nf4 35. Nf4 Nd5 36. Nd5 Ne7 37. Ne7 Ng8 38. Ng8 Nh6 39. Nh6 Nf5
40. Nf5 Nh4 41. Nh4 Ng6 42. Ng6 Nh8 43. Nh8 Nf7 44. Nf7 Nd8 45. Nd8 Ne6 46. Ne6 Nf8 47. Nf8 Nd7
48. Nd7 Ne5 49. Ne5 Ng4 50. Ng4 Nh2 51. Nh2 Nf3 52. Nf3 Ng1 53. Ng1 Nh3 54. Nh3 Ng5 55. Ng5 Nh7
56. Nh7 Nf6 57. Nf6 Ne8 58. Ne8 Ng7 59. Ng7 Nh5 60. Nh5 Ng3 61. Ng3 Nh1 62. Nh1 Nf2 63. Nf2 Nd1
20 15 22 45 58 47 38 43
17 4 19 48 37 44 59 56
14 21 16 23 46 57 42 39
3 18 5 36 49 40 55 60
6 13 8 29 24 35 50 41
9 2 11 32 27 52 61 54
12 7 28 25 30 63 34 51
1 10 31 64 33 26 53 62
</pre>
=={{header|ERRE}}==
| |||