Knight's tour: Difference between revisions
Content added Content deleted
Line 8,436: | Line 8,436: | ||
d6->f5->e3->c4->e5->c6->d4->f3 |
d6->f5->e3->c4->e5->c6->d4->f3 |
||
</pre> |
</pre> |
||
=={{header|m4}}== |
|||
Warnsdorff’s rule, with random tie-breaks. The program keeps trying |
|||
until it finds a solution. Running time can vary a lot. |
|||
<lang m4>divert(-1) |
|||
---------------------------------------------------------------------- |
|||
This is free and unencumbered software released into the public |
|||
domain. |
|||
Anyone is free to copy, modify, publish, use, compile, sell, or |
|||
distribute this software, either in source code form or as a compiled |
|||
binary, for any purpose, commercial or non-commercial, and by any |
|||
means. |
|||
In jurisdictions that recognize copyright laws, the author or authors |
|||
of this software dedicate any and all copyright interest in the |
|||
software to the public domain. We make this dedication for the benefit |
|||
of the public at large and to the detriment of our heirs and |
|||
successors. We intend this dedication to be an overt act of |
|||
relinquishment in perpetuity of all present and future rights to this |
|||
software under copyright law. |
|||
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
|||
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF |
|||
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. |
|||
IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR |
|||
OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, |
|||
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR |
|||
OTHER DEALINGS IN THE SOFTWARE. |
|||
For more information, please refer to <http://unlicense.org/> |
|||
---------------------------------------------------------------------- |
|||
Find a Knight's tour, via Warnsdorff's rule. |
|||
For very old or 'Heirloom' m4, you may need to increase the sizes of |
|||
internal structures, with, say, |
|||
m4 -S 1000 -B 100000 knights_tour.m4 |
|||
But I would use one of OpenBSD m4, GNU m4, etc., instead. |
|||
---------------------------------------------------------------------- |
|||
dnl Get a random number from 0 to one less than $1. |
|||
dnl (Note that this is not a very good RNG. Also it writes a file.) |
|||
define(`randnum', |
|||
`syscmd(`echo $RANDOM > __random_number__')eval(include(__random_number__) % ( $1 ))') |
|||
dnl The left deconstructors for strings. |
|||
define(`string_car',`substr($1,0,1)') |
|||
define(`string_cdr',`substr($1,1)') |
|||
dnl Algebraic notation to 'i0j0', with i the ranks and j the files. Bad |
|||
dnl algebraic notation gets tranformed to '99999999'. |
|||
define(`alg2ij', |
|||
`ifelse($1,`a1',`1010',$1,`a2',`2010',$1,`a3',`3010',$1,`a4',`4010', |
|||
$1,`a5',`5010',$1,`a6',`6010',$1,`a7',`7010',$1,`a8',`8010', |
|||
$1,`b1',`1020',$1,`b2',`2020',$1,`b3',`3020',$1,`b4',`4020', |
|||
$1,`b5',`5020',$1,`b6',`6020',$1,`b7',`7020',$1,`b8',`8020', |
|||
$1,`c1',`1030',$1,`c2',`2030',$1,`c3',`3030',$1,`c4',`4030', |
|||
$1,`c5',`5030',$1,`c6',`6030',$1,`c7',`7030',$1,`c8',`8030', |
|||
$1,`d1',`1040',$1,`d2',`2040',$1,`d3',`3040',$1,`d4',`4040', |
|||
$1,`d5',`5040',$1,`d6',`6040',$1,`d7',`7040',$1,`d8',`8040', |
|||
$1,`e1',`1050',$1,`e2',`2050',$1,`e3',`3050',$1,`e4',`4050', |
|||
$1,`e5',`5050',$1,`e6',`6050',$1,`e7',`7050',$1,`e8',`8050', |
|||
$1,`f1',`1060',$1,`f2',`2060',$1,`f3',`3060',$1,`f4',`4060', |
|||
$1,`f5',`5060',$1,`f6',`6060',$1,`f7',`7060',$1,`f8',`8060', |
|||
$1,`g1',`1070',$1,`g2',`2070',$1,`g3',`3070',$1,`g4',`4070', |
|||
$1,`g5',`5070',$1,`g6',`6070',$1,`g7',`7070',$1,`g8',`8070', |
|||
$1,`h1',`1080',$1,`h2',`2080',$1,`h3',`3080',$1,`h4',`4080', |
|||
$1,`h5',`5080',$1,`h6',`6080',$1,`h7',`7080',$1,`h8',`8080', |
|||
`99999999')') |
|||
dnl The reverse of alg2ij. Bad 'i0j0' get transformed to 'z0'. |
|||
define(`ij2alg', |
|||
`ifelse($1,`1010',`a1',$1,`2010',`a2',$1,`3010',`a3',$1,`4010',`a4', |
|||
$1,`5010',`a5',$1,`6010',`a6',$1,`7010',`a7',$1,`8010',`a8', |
|||
$1,`1020',`b1',$1,`2020',`b2',$1,`3020',`b3',$1,`4020',`b4', |
|||
$1,`5020',`b5',$1,`6020',`b6',$1,`7020',`b7',$1,`8020',`b8', |
|||
$1,`1030',`c1',$1,`2030',`c2',$1,`3030',`c3',$1,`4030',`c4', |
|||
$1,`5030',`c5',$1,`6030',`c6',$1,`7030',`c7',$1,`8030',`c8', |
|||
$1,`1040',`d1',$1,`2040',`d2',$1,`3040',`d3',$1,`4040',`d4', |
|||
$1,`5040',`d5',$1,`6040',`d6',$1,`7040',`d7',$1,`8040',`d8', |
|||
$1,`1050',`e1',$1,`2050',`e2',$1,`3050',`e3',$1,`4050',`e4', |
|||
$1,`5050',`e5',$1,`6050',`e6',$1,`7050',`e7',$1,`8050',`e8', |
|||
$1,`1060',`f1',$1,`2060',`f2',$1,`3060',`f3',$1,`4060',`f4', |
|||
$1,`5060',`f5',$1,`6060',`f6',$1,`7060',`f7',$1,`8060',`f8', |
|||
$1,`1070',`g1',$1,`2070',`g2',$1,`3070',`g3',$1,`4070',`g4', |
|||
$1,`5070',`g5',$1,`6070',`g6',$1,`7070',`g7',$1,`8070',`g8', |
|||
$1,`1080',`h1',$1,`2080',`h2',$1,`3080',`h3',$1,`4080',`h4', |
|||
$1,`5080',`h5',$1,`6080',`h6',$1,`7080',`h7',$1,`8080',`h8', |
|||
`z0')') |
|||
dnl Move a knight from one square to another by an ij-vector. Both input |
|||
dnl and output are algebraic notation. If the move is illegal, it comes |
|||
dnl out as 'z0'. |
|||
define(`move_by',`ij2alg(eval(alg2ij($3) + 1000 * ( $1 ) + 10 * ( $2 )))') |
|||
dnl For example, a1d3c5 -> 3 |
|||
define(`path_length',`eval(len($1) / 2)') |
|||
dnl The left deconstructors for paths. |
|||
define(`path_car',`substr($1,0,2)') |
|||
define(`path_cdr',`substr($1,2)') |
|||
dnl The right deconstructors for paths. |
|||
define(`path_last',`substr($1,eval(len($1) - 2))') |
|||
define(`path_drop_last',`substr($1,0,eval(len($1) - 2))') |
|||
dnl Extract the nth position from the path. |
|||
define(`path_nth', |
|||
`ifelse($2,0,`path_car($1)',`path_nth(path_cdr($1),eval(( $2 ) - 1))')') |
|||
define(`random_position',`path_nth($1,randnum(path_length($1)))') |
|||
dnl For example, a1d3c5 -> c5d3a1 |
|||
define(`path_reverse',`ifelse($1,`',`',`$0(path_cdr($1))`'path_car($1)')') dnl FIXME: IS THIS NEEDED? FIXME FIXME FIXME |
|||
dnl Is the position $1 contained in the path $2? |
|||
define(`path_contains',`ifelse(index($2,$1),-1,0,1)') |
|||
dnl Find all moves from position $1 that are not already in |
|||
dnl the path $2. |
|||
define(`possible_moves', |
|||
`ifelse(path_contains(move_by(1,2,$1),$2`'z0),`0',move_by(1,2,$1))`'dnl |
|||
ifelse(path_contains(move_by(2,1,$1),$2`'z0),`0',move_by(2,1,$1))`'dnl |
|||
ifelse(path_contains(move_by(1,-2,$1),$2`'z0),`0',move_by(1,-2,$1))`'dnl |
|||
ifelse(path_contains(move_by(2,-1,$1),$2`'z0),`0',move_by(2,-1,$1))`'dnl |
|||
ifelse(path_contains(move_by(-1,2,$1),$2`'z0),`0',move_by(-1,2,$1))`'dnl |
|||
ifelse(path_contains(move_by(-2,1,$1),$2`'z0),`0',move_by(-2,1,$1))`'dnl |
|||
ifelse(path_contains(move_by(-1,-2,$1),$2`'z0),`0',move_by(-1,-2,$1))`'dnl |
|||
ifelse(path_contains(move_by(-2,-1,$1),$2`'z0),`0',move_by(-2,-1,$1))') |
|||
dnl Count how many moves can follow each move in $1. |
|||
define(`follows_counts', |
|||
`ifelse($1,`',`', |
|||
`path_length(possible_moves(path_car($1),$2))`'follows_counts(path_cdr($1),$2)')') |
|||
dnl Find the smallest positive digit, or zero. |
|||
define(`min_positive', |
|||
`ifelse($1,`',0, |
|||
`pushdef(`min1',min_positive(string_cdr($1)))`'dnl |
|||
pushdef(`val1',string_car($1))`'dnl |
|||
ifelse(min1,0,val1, |
|||
val1,0,min1, |
|||
eval(val1 < min1),1,val1,min1)`'dnl |
|||
popdef(`min1',`val1')')') |
|||
dnl Change everything to zero that is not the minimum positive. |
|||
define(`apply_warnsdorff',`_$0(min_positive($1),$1)') |
|||
define(`_apply_warnsdorff', |
|||
`ifelse($2,`',`',`ifelse(string_car($2),$1,$1,0)`'$0($1,string_cdr($2))')') |
|||
dnl Find potential next moves that satisfy Warnsdorff's rule. |
|||
define(`warnsdorff_moves', |
|||
`pushdef(`moves',`possible_moves($1,$2)')`'dnl |
|||
pushdef(`selections',`apply_warnsdorff(follows_counts(moves))')`'dnl |
|||
_$0(moves,selections)`'dnl |
|||
popdef(`moves',`selections')') |
|||
define(`_warnsdorff_moves', |
|||
`ifelse($1,`',`', |
|||
`ifelse(string_car($2),0,`$0(path_cdr($1),string_cdr($2))', |
|||
`path_car($1)`'$0(path_cdr($1),string_cdr($2))')')') |
|||
dnl Find possible next moves for the given path. |
|||
define(`next_moves', |
|||
`ifelse(path_length($1),63,`possible_moves(path_last($1),$1)', |
|||
`warnsdorff_moves(path_last($1),$1)')') |
|||
define(`find_tour', |
|||
`ifelse($2,`',`find_tour($1,$1)', |
|||
path_length($2),64,$2, |
|||
`pushdef(`moves',next_moves($2))`'dnl |
|||
ifelse(moves,`',`find_tour($1)', |
|||
`find_tour($1,$2`'random_position(next_moves($2)))')`'dnl |
|||
popdef(`moves')')') |
|||
divert`'dnl |
|||
dnl |
|||
find_tour(a1) |
|||
find_tour(c5) |
|||
find_tour(h8)</lang> |
|||
{{out}} |
|||
This is just a sample. Outputs are random. |
|||
$ m4 knights_tour.m4 |
|||
<pre>a1c2a3b1d2f1h2g4h6g8e7c8a7b5c7a8b6a4b2d1f2h1g3h5g7e8f6h7f8d7b8a6b4a2c1e2g1h3g5f7h8g6h4g2e1d3c5b7d8e6f4d5c3e4d6f5e3c4a5b3d4c6e5f3 |
|||
c5b7d8f7h8g6h4g2e1c2a1b3c1a2b4a6b8d7f8h7g5h3g1e2g3h1f2d1b2a4b6a8c7e8g7h5f6g8h6g4h2f1d2b1a3b5a7c8e7d5c3e4d6f5e3c4a5c6d4e6f4d3e5f3 |
|||
h8g6f8h7g5h3g1e2c1a2b4a6b8d7b6a8c7e8g7h5g3h1f2d1b2a4c5b7a5b3a1c2e1g2h4f3h2f1d2b1a3b5a7c8e7g8h6f7d8e6f4d3e5g4f6d5c3e4d6c4e3f5d4c6</pre> |
|||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |