{"id":963,"date":"2026-02-22T15:16:26","date_gmt":"2026-02-22T15:16:26","guid":{"rendered":"https:\/\/shatranj.art\/?page_id=963"},"modified":"2026-02-23T11:10:10","modified_gmt":"2026-02-23T11:10:10","slug":"poster-17","status":"publish","type":"page","link":"https:\/\/shatranj.art\/vi\/exhibit\/poster-17\/","title":{"rendered":"Poster 17"},"content":{"rendered":"
\n\t\t\t\t
\n\t\t\t\t\t
\n\t\t
\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

Chuy\u1ebfn du h\u00e0nh c\u1ee7a Hi\u1ec7p s\u0129<\/b><\/h2>

S\u00e2u s\u1eafc l\u1ecbch s\u1eed:<\/b> H\u00e0nh tr\u00ecnh c\u1ee7a Hi\u1ec7p s\u0129 l\u00e0 m\u1ed9t d\u00e3y s\u1ed1 h\u1ecdc trong \u0111\u00f3 m\u1ed9t hi\u1ec7p s\u0129 \u0111i qua m\u1ecdi \u00f4 tr\u00ean b\u00e0n c\u1edd vua ch\u00ednh x\u00e1c m\u1ed9t l\u1ea7n. \u0110\u00e2y v\u1eeba l\u00e0 m\u1ed9t th\u00e1ch th\u1ee9c chi\u1ebfn l\u01b0\u1ee3c v\u1eeba l\u00e0 m\u1ed9t b\u00e0i to\u00e1n kinh \u0111i\u1ec3n trong to\u00e1n h\u1ecdc gi\u1ea3i tr\u00ed.<\/span><\/p>

\u00a0<\/p>

Ngu\u1ed3n g\u1ed1c:<\/b><\/p>

V\u1ea5n \u0111\u1ec1 n\u00e0y kh\u00f4ng ph\u1ea3i l\u00e0 m\u1ed9t ph\u00e1t hi\u1ec7n hi\u1ec7n \u0111\u1ea1i. C\u00e1c gi\u1ea3i ph\u00e1p s\u1edbm nh\u1ea5t \u0111\u01b0\u1ee3c bi\u1ebft \u0111\u1ebfn c\u00f3 ngu\u1ed3n g\u1ed1c t\u1eeb th\u1ebf k\u1ef7 9, do c\u00e1c b\u1eadc th\u1ea7y t\u1eeb Baghdad nh\u01b0 Al-Adli v\u00e0 As-Suli \u0111\u01b0a ra. H\u01a1n n\u1eefa, trong v\u0103n h\u1ecdc \u1ea4n \u0110\u1ed9 th\u1ebf k\u1ef7 9, nh\u00e0 th\u01a1 Kashmir Rudrata \u0111\u00e3 th\u1ec3 hi\u1ec7n th\u1ea9m m\u1ef9 to\u00e1n h\u1ecdc n\u00e0y trong t\u00e1c ph\u1ea9m Kavyalankara c\u1ee7a m\u00ecnh, n\u01a1i \u00f4ng s\u00e1ng t\u00e1c m\u1ed9t b\u00e0i th\u01a1 tu\u00e2n theo chu\u1ed7i di chuy\u1ec3n c\u1ee7a m\u1ed9t hi\u1ec7p s\u0129.<\/p>

\u00a0<\/p>

V\u0103n h\u1ecdc ph\u01b0\u01a1ng T\u00e2y:<\/b><\/p>

V\u00e0o th\u1ebf k\u1ef7 13, Vua Alfonso X c\u1ee7a Castile \u0111\u00e3 m\u00f4 t\u1ea3 c\u00e1c chi\u1ebfn thu\u1eadt ph\u1ee9c t\u1ea1p d\u1ef1a tr\u00ean chuy\u1ec3n \u0111\u1ed9ng c\u1ee7a hi\u1ec7p s\u0129 trong cu\u1ed1n s\u00e1ch n\u1ed5i ti\u1ebfng c\u1ee7a \u00f4ng, Libro de los Juegos (S\u00e1ch v\u1ec1 C\u00e1c Tr\u00f2 Ch\u01a1i). Tuy nhi\u00ean, n\u1ec1n t\u1ea3ng to\u00e1n h\u1ecdc hi\u1ec7n \u0111\u1ea1i c\u1ee7a v\u1ea5n \u0111\u1ec1 n\u00e0y \u0111\u01b0\u1ee3c \u0111\u1eb7t ra v\u00e0o n\u0103m 1759 b\u1edfi Leonhard Euler, ph\u00e2n t\u00edch c\u1ee7a \u00f4ng hi\u1ec7n \u0111\u01b0\u1ee3c c\u00f4ng nh\u1eadn l\u00e0 m\u1ed9t trong nh\u1eefng n\u1ec1n t\u1ea3ng c\u01a1 b\u1ea3n c\u1ee7a L\u00fd thuy\u1ebft \u0110\u1ed3 th\u1ecb.<\/p>

\u00a0<\/p>

\u0110\u1eb7c \u0111i\u1ec3m:<\/b><\/p>

Chuy\u1ebfn tham quan \u0111\u00f3ng c\u1eeda (c\u00f3 th\u1ec3 tham gia l\u1ea1i):<\/b> N\u1ebfu qu\u00e2n m\u00e3 k\u1ebft th\u00fac tr\u00ean m\u1ed9t \u00f4 c\u00e1ch \u00f4 xu\u1ea5t ph\u00e1t ch\u00ednh x\u00e1c m\u1ed9t n\u01b0\u1edbc \u0111i c\u1ee7a qu\u00e2n m\u00e3, cho ph\u00e9p n\u00f3 ngay l\u1eadp t\u1ee9c b\u1eaft \u0111\u1ea7u l\u1ea1i h\u00e0nh tr\u00ecnh.<\/p>

\u00a0<\/p>

Tour m\u1edf c\u1eeda:<\/b><\/p>

N\u1ebfu con ng\u1ef1a di chuy\u1ec3n qua m\u1ecdi \u00f4 nh\u01b0ng k\u1ebft th\u00fac \u1edf m\u1ed9t \u00f4 m\u00e0 t\u1eeb \u0111\u00f3 n\u00f3 kh\u00f4ng th\u1ec3 quay l\u1ea1i \u0111i\u1ec3m xu\u1ea5t ph\u00e1t trong m\u1ed9t n\u01b0\u1edbc \u0111i duy nh\u1ea5t.<\/span><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

V\u1ea5n \u0111\u1ec1 8 N\u1eef ho\u00e0ng: Dijkstra v\u00e0 s\u1ef1 ra \u0111\u1eddi c\u1ee7a l\u1eadp tr\u00ecnh c\u00f3 c\u1ea5u tr\u00fac<\/b><\/h2>

V\u1ea5n \u0111\u1ec1 n\u00e0y \u0111\u01b0\u1ee3c Max Bezzel \u0111\u01b0a ra v\u00e0o n\u0103m 1848 v\u00e0 thu h\u00fat s\u1ef1 ch\u00fa \u00fd c\u1ee7a nh\u1eefng thi\u00ean t\u00e0i nh\u01b0 Carl Friedrich Gauss. V\u00e0o th\u1eadp ni\u00ean 1970, v\u1ea5n \u0111\u1ec1 n\u00e0y \u0111\u00e3 \u0111\u01b0\u1ee3c Edsger W. Dijkstra, m\u1ed9t trong nh\u1eefng ng\u01b0\u1eddi s\u00e1ng l\u1eadp c\u1ee7a khoa h\u1ecdc m\u00e1y t\u00ednh hi\u1ec7n \u0111\u1ea1i, bi\u1ebfn th\u00e0nh m\u1ed9t \u201ctuy\u00ean ng\u00f4n l\u1eadp tr\u00ecnh\u201d.<\/p>

M\u1ed1i quan h\u1ec7 gi\u1eefa Dijkstra v\u00e0 DFS<\/b><\/h3>

Trong t\u00e1c ph\u1ea9m kinh \u0111i\u1ec3n c\u1ee7a m\u00ecnh, <\/span>Ghi ch\u00fa v\u1ec1 l\u1eadp tr\u00ecnh c\u00f3 c\u1ea5u tr\u00fac<\/span><\/i> (1972), Dijkstra \u0111\u00e3 s\u1eed d\u1ee5ng b\u00e0i to\u00e1n 8 N\u1eef ho\u00e0ng \u0111\u1ec3 minh h\u1ecda c\u00e1ch m\u1ed9t thu\u1eadt to\u00e1n c\u00f3 th\u1ec3 \u0111\u01b0\u1ee3c x\u00e2y d\u1ef1ng m\u1ed9t c\u00e1ch c\u00f3 h\u1ec7 th\u1ed1ng th\u00f4ng qua qu\u00e1 tr\u00ecnh m\u00e0 \u00f4ng g\u1ecdi l\u00e0 \u201ctinh ch\u1ec9nh t\u1eebng b\u01b0\u1edbc\u201d.\u201d<\/span><\/p>

  • DFS v\u00e0 Backtracking: Dijkstra \u0111\u00e3 \u0111\u1ecbnh ngh\u0129a ph\u01b0\u01a1ng ph\u00e1p \u0111\u1eb7t m\u1ed9t qu\u00e2n h\u1eadu v\u00e0o m\u1ed9t h\u00e0ng v\u00e0 di chuy\u1ec3n xu\u1ed1ng h\u00e0ng ti\u1ebfp theo (T\u00ecm ki\u1ebfm theo chi\u1ec1u s\u00e2u \u2013 DFS) v\u00e0 quay l\u1ea1i b\u01b0\u1edbc tr\u01b0\u1edbc \u0111\u00f3 \u0111\u1ec3 th\u1eed m\u1ed9t kh\u1ea3 n\u0103ng kh\u00e1c khi g\u1eb7p ng\u00f5 c\u1ee5t (Backtracking) l\u00e0 v\u00ed d\u1ee5 thu\u1ea7n t\u00fay nh\u1ea5t c\u1ee7a l\u1eadp tr\u00ecnh c\u00f3 c\u1ea5u tr\u00fac.<\/li><\/ul>

    S\u1ee9c m\u1ea1nh c\u1ee7a vi\u1ec7c quay l\u1ea1i:<\/b><\/p>

    Theo Dijkstra, ph\u01b0\u01a1ng ph\u00e1p n\u00e0y \u0111\u00e1nh d\u1ea5u c\u1ed9t m\u1ed1c quan tr\u1ecdng \u0111\u1ea7u ti\u00ean trong vi\u1ec7c ho\u00e0n thi\u1ec7n qu\u00e1 tr\u00ecnh \u201cth\u1eed v\u00e0 sai\u201d th\u00e0nh m\u1ed9t chu\u1ed7i logic ho\u00e0n h\u1ea3o m\u00e0 m\u1ed9t...<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t

    V\u1ea5n \u0111\u1ec1 L\u00faa m\u00ec v\u00e0 B\u00e0n c\u1edd: T\u0103ng tr\u01b0\u1edfng theo c\u1ea5p s\u1ed1 nh\u00e2n<\/b><\/h3>

    Th\u1ea7n tho\u1ea1i v\u00e0 Ngu\u1ed3n g\u1ed1c:<\/b><\/p>

    Theo c\u00e2u chuy\u1ec7n, khi nh\u00e0 ph\u00e1t minh c\u1edd vua, Sissa bin Dahir, tr\u00ecnh b\u00e0y tr\u00f2 ch\u01a1i cho Vua \u1ea4n \u0110\u1ed9, v\u1ecb vua \u0111\u00e3 h\u1ecfi \u00f4ng mu\u1ed1n nh\u1eadn ph\u1ea7n th\u01b0\u1edfng g\u00ec. Sissa \u0111\u01b0a ra m\u1ed9t y\u00eau c\u1ea7u d\u01b0\u1eddng nh\u01b0 khi\u00eam t\u1ed1n: \u201cT\u00f4i mu\u1ed1n m\u1ed9t h\u1ea1t l\u00faa m\u00ec cho \u00f4 \u0111\u1ea7u ti\u00ean c\u1ee7a b\u00e0n c\u1edd, hai h\u1ea1t cho \u00f4 th\u1ee9 hai, b\u1ed1n h\u1ea1t cho \u00f4 th\u1ee9 ba, v\u00e0 cho m\u1ed7i \u00f4 ti\u1ebfp theo, g\u1ea5p \u0111\u00f4i s\u1ed1 l\u01b0\u1ee3ng c\u1ee7a \u00f4 tr\u01b0\u1edbc \u0111\u00f3.\u201d Vua ban \u0111\u1ea7u \u0111\u00e3 t\u1eeb ch\u1ed1i y\u00eau c\u1ea7u n\u00e0y, cho r\u1eb1ng \u0111\u00f3 ch\u1ec9 l\u00e0 \u201cm\u1ed9t n\u1eafm l\u00faa m\u00ec\u201d; tuy nhi\u00ean, khi b\u1eaft \u0111\u1ea7u t\u00ednh to\u00e1n, r\u00f5 r\u00e0ng l\u00e0 c\u1ea3 kho b\u1ea1c c\u1ee7a vua l\u1eabn to\u00e0n b\u1ed9 kho l\u00faa m\u00ec tr\u00ean th\u1ebf gi\u1edbi c\u0169ng kh\u00f4ng \u0111\u1ee7 \u0111\u1ec3 \u0111\u00e1p \u1ee9ng y\u00eau c\u1ea7u n\u00e0y.<\/p>

    Ghi ch\u00e9p l\u1ecbch s\u1eed: Ibn Khallikan (1256)<\/b><\/p>

    Ghi ch\u00e9p v\u0103n b\u1ea3n \u0111\u1ea7u ti\u00ean \u0111\u01b0\u1ee3c bi\u1ebft \u0111\u1ebfn v\u1ec1 c\u00e2u chuy\u1ec7n n\u1ed5i ti\u1ebfng n\u00e0y \u0111\u01b0\u1ee3c ghi l\u1ea1i v\u00e0o n\u0103m 1256 b\u1edfi nh\u00e0 s\u1eed h\u1ecdc v\u00e0 nh\u00e0 bi\u00ean ni\u00ean s\u1eed n\u1ed5i ti\u1ebfng Ibn Khallikan. Ibn Khallikan \u0111\u00e3 \u0111\u01b0a s\u1ef1 ki\u1ec7n n\u00e0y v\u00e0o t\u00e1c ph\u1ea9m c\u1ee7a m\u00ecnh kh\u00f4ng ch\u1ec9 nh\u01b0 m\u1ed9t c\u00e2u chuy\u1ec7n, m\u00e0 c\u00f2n nh\u01b0 m\u1ed9t minh ch\u1ee9ng cho c\u00e1ch to\u00e1n h\u1ecdc m\u1edf r\u1ed9ng gi\u1edbi h\u1ea1n c\u1ee7a tr\u00ed t\u01b0\u1edfng t\u01b0\u1ee3ng.<\/p>

    Th\u1ef1c t\u1ea1i to\u00e1n h\u1ecdc:<\/b><\/p>

    Y\u00eau c\u1ea7u n\u00e0y \u0111\u1ed1i v\u1edbi 64 \u00f4 tr\u00ean b\u00e0n c\u1edd vua l\u00e0 v\u00ed d\u1ee5 \u0111i\u1ec3n h\u00ecnh nh\u1ea5t c\u1ee7a c\u1ea5p s\u1ed1 nh\u00e2n (t\u0103ng tr\u01b0\u1edfng theo c\u1ea5p s\u1ed1 nh\u00e2n). S\u1ed1 ti\u1ec1n tr\u00ean m\u1ed7i \u00f4 \u0111\u01b0\u1ee3c t\u00ednh to\u00e1n b\u1eb1ng c\u00f4ng th\u1ee9c 2n tr\u1eeb 1<\/sup><\/strong> . Ph\u01b0\u01a1ng tr\u00ecnh t\u00ednh t\u1ed5ng l\u01b0\u1ee3ng l\u00faa m\u00ec \u0111\u01b0\u1ee3c tr\u00ecnh b\u00e0y nh\u01b0 sau:<\/span><\/p>

    \u00a0<\/p>

    S =<\/span>


    63<\/span>
    \u2211<\/span>
    i<\/i>=0<\/span>
    <\/span><\/p>

    2i<\/i><\/sup> = 264<\/sup> \u2212 1<\/span><\/p><\/div>

    Con s\u1ed1 kh\u1ed5ng l\u1ed3 \u0111\u01b0\u1ee3c t\u00ednh to\u00e1n t\u1eeb ph\u00e9p t\u00ednh n\u00e0y l\u00e0:<\/p>

    18,446,744,073,709,551,615<\/b><\/p>

    T\u1ea1i sao \u0111i\u1ec1u \u0111\u00f3 l\u1ea1i quan tr\u1ecdng \u0111\u1ebfn v\u1eady?<\/b><\/p>

    • Quy m\u00f4 t\u0103ng tr\u01b0\u1edfng:<\/b> Con s\u1ed1 n\u00e0y t\u01b0\u01a1ng \u0111\u01b0\u01a1ng v\u1edbi kho\u1ea3ng 2.000 l\u1ea7n s\u1ea3n l\u01b0\u1ee3ng l\u00faa m\u00ec h\u00e0ng n\u0103m hi\u1ec7n t\u1ea1i c\u1ee7a to\u00e0n th\u1ebf gi\u1edbi.\u00a0<\/span><\/li><\/ul>

      B\u00e0i h\u1ecdc chi\u1ebfn l\u01b0\u1ee3c:<\/b> V\u1ea5n \u0111\u1ec1 n\u00e0y l\u00e0 m\u1ed9t b\u00e0i h\u1ecdc c\u1ed5 x\u01b0a v\u1ec1 tr\u00ed tu\u1ec7, d\u1ea1y cho c\u00e1c nh\u00e0 l\u00e3nh \u0111\u1ea1o v\u00e0 chi\u1ebfn l\u01b0\u1ee3c gia r\u1eb1ng nh\u1eefng thay \u0111\u1ed5i nh\u1ecf (\u201ct\u0103ng g\u1ea5p \u0111\u00f4i\u201d) c\u00f3 th\u1ec3 bi\u1ebfn th\u00e0nh nh\u1eefng l\u1ef1c l\u01b0\u1ee3ng kh\u00f4ng th\u1ec3 ki\u1ec3m so\u00e1t theo th\u1eddi gian.<\/span><\/p><\/div><\/div>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"

      The Knight’s Tour Historical Depth: The Knight’s Tour is a mathematical sequence in which a knight visits every single square on a chessboard exactly once. It is both a strategic challenge and a classic problem in recreational mathematics. \u00a0 Origins: This problem is far from a modern discovery. The earliest known solutions date back to […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":743,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-963","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/shatranj.art\/vi\/wp-json\/wp\/v2\/pages\/963","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/shatranj.art\/vi\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/shatranj.art\/vi\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/shatranj.art\/vi\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/shatranj.art\/vi\/wp-json\/wp\/v2\/comments?post=963"}],"version-history":[{"count":22,"href":"https:\/\/shatranj.art\/vi\/wp-json\/wp\/v2\/pages\/963\/revisions"}],"predecessor-version":[{"id":1443,"href":"https:\/\/shatranj.art\/vi\/wp-json\/wp\/v2\/pages\/963\/revisions\/1443"}],"up":[{"embeddable":true,"href":"https:\/\/shatranj.art\/vi\/wp-json\/wp\/v2\/pages\/743"}],"wp:attachment":[{"href":"https:\/\/shatranj.art\/vi\/wp-json\/wp\/v2\/media?parent=963"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}