Knight's tour: Difference between revisions
Content added Content deleted
m (Updated to Elm 0.19.1) |
|||
Line 2,677: | Line 2,677: | ||
Link to live demo: http://dc25.github.io/knightsTourElm/ |
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}}== |
=={{header|ERRE}}== |