Knight'sTours

Knight’s Tours

Ben Hill,Kevin Tostado

December18,2004

Abstract

In this paper we discuss the knight’s tour,a chess puzzle related to graph theory.We explore the history of the problem,the connection to Hamiltonian paths and circuits,and some techniques for?nding the tours and proving their existence.We also delve into magic knight’s tours,applications to cryptography,and symmetry in knight’s tours.

1

The Knight’s Tour Problem

The knight is the only chess piece that does not move in a straight line.In-stead,the legal move for a knight is two spaces in one direction,then one in a perpendicular direction(Figure1).A knight’s tour is a journey around the chessboard in such a way that the knight lands on each square exactly once.

Figure1:Legal moves for a knight

If you represent a knight’s tour as a graph,the vertices would represent the squares of the board and the edges would represent a knight’s legal moves between squares(Figure2).Therefore,a knight’s tour(a path that traverses all of the squares of the chessboard)is simply a Hamiltonian path.A closed (or reentrant)knight’s tour is one where the?nal move is one legal move away from the starting square;this is represented by a Hamiltonian circuit. History of Knight’s Tours

The earliest surviving knight’s tour is shown in Figure3.It is attributed to al-Adli ar-Rumi who lived in Baghdad in840AD and is known to have written a book on an early form of chess played in the Middle East.

A number of other knight’s tours appeared in medieval chess manuscripts. Most of these tours covered only half the board(4x8)or join two such half-

2

Figure2:Graph representation of an8x8chessboard and knight’s moves boards together.The subject then seems to have been forgotten until around 1722.The?rst thorough scienti?c study of knight’s tours was conducted by Leonhard Euler in1759.Euler also investigated symmetries possible within tours[1].

Methods for Finding Knight’s Tours

Just as Euler was among the?rst to study knight’s tours systematically, he also created one of the?rst methods for?nding them.Euler’s tech-nique(suggested by fellow mathematician L.Bertrand)combines smaller and incomplete tours to form a new tour[1].The best-known and historically most important procedure for?nding knight’s tours was invented by Ger-man mathematician H.C.Warnsdor?in1823,and is known as Warnsdor?’s rule[2].The rule is simple:starting at any square,make a legal move to the square having the fewest successors.A successor is any square one legal move away.In using this method the squares with the fewest successors are visited ?rst,which prevents them from becoming dead-ends later on.It is important to note that Warnsdor?’s rule is heuristic,meaning it is not guaranteed to ?nd a solution.Although Warnsdor?though his rule would?nd a tour on any size rectangular board,exhaustive computer searches have shown that it can fail for boards larger than76x76.A modern day improvement by Arnd Roth breaks ties in choosing successors by selecting the square furthest from

3

Figure3:Oldest surviving knight’s tour(note it is a closed tour)

the center of the board;this method?rst fails on a428x428board.The rea-son for using these heuristics instead of an algorithm guaranteed to work is speed.It is possible to create such an algorithm using backtracking,but for larger boards it quickly becomes too slow to be e?ective(while the heuristics’solution time increases approximately linearly with board size)[3].Interest-ingly enough,the most recent methods for?nding large knight’s tours are somewhat similar to Euler’s approach.These techniques decompose a large board into smaller rectangles for which solutions are already known.These smaller solutions are then joined to form a knight’s tour[4](Figure4).

Figure4:Example of a60x60knight’s tour generated by decomposition

4

Existence of Knight’s Tours

One interesting knight’s tour problem is discovering which boards support a closed tour.Allen Schwenk proposes the following theorem[5],which we will explore in some detail:

Theorem

An m x n chessboard with m≤n has a knight’s tour unless one or more of these three conditions holds:

(i)m and n are both odd;

(ii)m=1,2,or4;or

(iii)m=3and n=4,6,or8.

Proof of(i):Looking at the knight’s moves,we can see that every legal move is from a black square to a white square,or vice-versa.Thus,any closed tour must visit an equal number of white and black squares.But if both m and n are odd,there are an odd number of squares and the knight cannot an equal number of white and black.Consequently,we cannot construct a closed tour on a board of odd size.

Proof of(ii):If m=1or2,it is clear by inspection that the board is not wide enough to construct a tour.When m=4,we prove there cannot be a knight’s tour using graph coloring[6].Two di?erent colorings of a4x6board are shown in Figure5.The important thing to notice about the second board is that there are an equal number of red and blue squares,and from a red square you can only get to a blue square.Putting these facts together means that you can only construct a closed tour if the squares in the sequence of moves alternate between red and blue.From the way the knight moves,we also know that in the?rst board the knight always alternates between white and black.Since there is no one-to-one correspondence between white/black and red/blue squares,this is a contradiction and there is no possible closed tour.

Proof of(iii):The proof of part(iii)involves removing vertices from the Hamiltonian cycle that represents the knight’s moves.When k vertices are

5

Figure5:The4x n board does not support a closed knight’s tour removed from the cycle,there can be at most k connected components of the graph.If there are more than k connected components left after removing k vertices,then the original graph did not contain a Hamiltonian cycle.By proceeding in this manner,it is possible to eliminate the3x6and3x8boards (the3x4board was eliminated in part(ii)).In the remainder of the proof, Schwenk goes on to show that it is possible to construct a knight’s tour on all other rectangular boards.The proof is too long to include here,but it is a proof by induction with nine base cases(shown in Figure6).This is similar to the method of constructing knight’s tours by decomposing the board into smaller,known tours.

In a similar problem,Watkins and Hoenigman studied closed tours that exist on the surface of a torus,basically a rectangular board in which the knight is allowed to’wrap around’the board.They found that under this modi?cation,every rectangular board has a tour[7].

Magic Knight’s Tours

In a magic knight’s tour,the squares of the chess board are numbered in the order of the knight’s moves.Each column,row,and diagonal must sum to the same number.The?rst magic knight’s tour(with sum260)was not found until1848by William Beverley.Beverley’s tour,however,was actually

6

Figure6:Constituent knight’s tours for closed tours on an m x n board only what is now called semi-magic,because the diagonals did not also add

to260.The tour also exhibits some interesting properties[8](Figure7).

Figure7:(a)First semi-magic knight’s tour

(b)In each quadrant,the sum of the numbers equals520and each of the

rows and columns adds to130

(c)The sum of the numbers in each2x2section is130

Until very recently,the existence of a fully magic knight’s tour had

yet to be determined.This longstanding open problem has now been set-

tled through the use of exhaustive computer search[9].After nearly62

7

computation-days,the project was completed on August5,2003.Although it found a total of140semimagic knight’s tours,the search showed that no 8x8fully magic knight’s tour is possible[10].

Knight’s Tours and Cryptography

A cryptotour is a puzzle in which the64words or syllables of a verse are printed on the squares of a chessboard and are to be read in the sequence of a knight’s tour.The earliest known examples of a cryptotour were printed in the mid1800s in a French magazine.In the last few years(1870-1874)of Howard Stanton’s chess column in Illustrated London News,he featured16 cryptotours.Published before the invention of crossword puzzles,these were very popular.Most of the cryptotours featured well known verse from such writers as Dante,Shakespeare,and Walter Scott.Figure8gives an example of one of those cryptotours[1].

Figure8:Example of a cryptotour from1870

Knight’s Tours and Symmetry

Using his method for constructing knight’s tours,Euler studied some special types of tours.He constructed symmetric tours,having the property that the

8

numbers in diametrically opposite squares have a constant di?erence of32. This symmetry was visible geometrically in the Hamiltonian graphs of the knight’s moves with the last connected to the?rst,resulting in a geometrical closed tour[1].

Euler also gave the?rst ever examples of tours exhibiting quaternary symmetry.These consist of two tours of cross-shaped boards symmetric by re?ection about the two diagonals,and a10x10tour formed by repeating the same5x5tour in each quarter,rotated90[1].

Knight’s tours can also be used to construct https://www.wendangku.net/doc/db5482766.html,ing the four sets of16moves shown in Figure9,it is possible to construct four polygons that together can form a tessellation.Knight’s tour tessellations can even be used to create beautiful3-D patterns such as astersphaira(star spheres)and hexastersphaira(Figure10)[11].

Figure9:Four polygons formed by knight moves and their tessellation of the plane

9

Figure10:Astersphaira(left)and hexastersphaira(right)

References

[1]Jelliss,George.”Introducing Knight’s Tours.”

https://www.wendangku.net/doc/db5482766.html,/gpj/ktn.htm

[2]Trnberg,Gunno.”Warnsdor?’s Rule.”

https://www.wendangku.net/doc/db5482766.html,/u85905224/knight/eWarnsd.htm

[3]Roth,Arnd.”The Problem of the Knight.”http://sun0.mpimf-

heidelberg.mpg.de/people/roth/Mma/Knight.html

[4]Parberry,Ian.”Scalability of a Neural Network for the Knight’s Tour

Problem.”(1997)

[5]Schwenk,Allen J.”Which Rectangular Chessboards Have a Knight’s

Tour?”.Mathematics.64(1991):325-332.

[6]Stewart,Ian.”Mathematical Recreations:Knight’s Tours.”Scienti?c

American.April1997.102-104.

[7]Watkins,John J.and Rebecca L.Hoenigman.”Knight’s Tours on a

Torus.”Mathematics.70(1997):175-184

[8]Collins,Edward D.”A Knight’s Tour.”

https://www.wendangku.net/doc/db5482766.html,/chess/knights-tour.htm

[9]Stertenbrink,Guenter.http://magictour.free.fr

10

[10]Weisstein,Eric W.”There Are No Magic Knight’s Tours on the Chess-

board.”https://www.wendangku.net/doc/db5482766.html,/news/2003-08-06/magictours/ [11]Thomasson,Dan.”The Knight’s Tour.”

https://www.wendangku.net/doc/db5482766.html,/KnightTour.htm

11

恢复中华人民共和国国籍申请表【模板】

W—3表 人员编号______________ 档案编号______________ 恢复中华人民共和国国籍 申请表

申请人____________________申请日期_______年____月____日 受理人____________________受理日期_______年____月____日 外文姓___________________________________________________ 外文名___________________________________________________ 中文姓名__________________国籍____________性别___________ 出生日期________年______月______日出生地_____________ 护照证件种类__________________ 号码_____________________ 有效期至________年______月______日签发机关___________________________ 所持签证种类__________________号码_________________ 签发机关__________ 签证有效期___年___月___日本次入境日期___年___月___日入境口岸_________ 定居确认表号码______________________ 签发日期__________________________ 外国人居留证号码____________ 有效期______年____月____日职业或身份_____ 定居地住址_____________所属公安派出所________________联系电话__________ 申请恢复中国国籍的理由__________________________________________________

说说中国的国籍制度

说说中国的国籍制度 中国自50年代起就废除双重国籍的体制，可是，作者指出，各国 在对待国籍问题上都是采取利己损人的态度，偏偏是中国却是采用利 人而于己无益的政策，这种为渊驱鱼的做法造成有意回归的华人无法 取得中国国籍，对中国是不利的。 孙中山先生曾有“华侨是革命之母”一语，可见中国近代史与海 外华人休戚相关。近年来中国大陆的经济发展更显示这一历史模式的 延续。因此双重、多重国籍这个敏感问题颇有讨论的必要。 按照旧法律名词，中国传统的国籍政策是属血（de sanguinis） 原则，即只问祖籍，不问出生地点。以后者为准的叫做属地（de solis）原则。现行的中国国籍法两者都不是。 1980年9月10日颁布的中华人民共和国国籍法第四条规定：

父母双方或一方为中国公民，本人出生在中国，具有中国国籍。 第五条规定：父母双方或一方为中国公民，本人出生在外国，具有中 国国籍，但父母双方或一方为中国公民并定居在外国，本人出生即具 有外国国籍的，不具有中国国籍。 各国法律规定不同 “具有外国籍”的意思并不明确。以加拿大、美国为例，中国公 民的小孩一出生就“自动”有当地国籍，是法律明文规定的，但是如 果退出当地国籍后，能不能凭父母之中一方的中国国籍取得中国籍？ 答案按中国国籍法第七条：中国人的近亲属，愿意遵守中国宪法和法 律的，可以申请加入中国国籍。 换言之，在加拿大、美国出生的中国小孩，幼时被小同学另眼相 看，但要做中国人，需要申请，批准与否，并无明确规定。

在德国出 生的中国小孩则没有这个麻烦，因为他们不自动具有德国国籍。一个 人是不是中国人竟然要看当地法律，法律一改，情况即起变化，实在 十分有意思。一个国家的国籍法的效果，实际以外国立法机关的意志 为转移，不能不谓奇特。 其实最主要的关键是中国国籍法第三条：中华人民共和国不承认 中国公民具有双重国籍。 以及第九条：定居外国的中国公民，自愿加入或取得外国国籍的 ，即自动丧失中国国籍。 其精神和大部分国家的国籍法对双重国籍的态度截然 相反。大多 数国家不承认自己公民因外国国籍而丧失本国籍，例如法国人不论以 何种方式取得外国国籍，法国仍视之为本国公民，其义务、权利丝毫 无增无损。特别是在任何情况之下，不能引渡到法国之外受审、服刑

恢复中国国籍相关规定

中华人民共和国籍法 １９８０年９月１０日第五届全国人民代表大会第三次会议通过１９８０年９月１０日全国人民代表大会常务委员会委员长令第八号公布施行 第一条中华人民共和国国籍的取得、丧失和恢复，都适用本法。 第二条中华人民共和国是统一的多民族的国家，各民族的人都具有中国国籍。 第三条中华人民共和国不承认中国公民具有双重国籍。 第四条父母双方或一方为中国公民，本人出生在中国，具有中国国籍。 第五条父母双方或一方为中国公民，本人出生在外国，具有中国国籍；但父母双方或一方为中国公民并定居在外国，本人出生时即具有外国国籍的，不具有中国国籍。 第六条父母无国籍或国籍不明，定居在中国，本人出生在中国，具有中国国籍。 第七条外国人或无国籍人，愿意遵守中国宪法和法律，并具有下列条件之一的，可以经申请批准加入中国国籍： 一、中国人的近亲属； 二、定居在中国的； 三、有其它正当理由。 第八条申请加入中国国籍获得批准的，即取得中国国籍；被批准加入中国国籍的，不得再保留外国国籍。 第九条定居外国的中国公民，自愿加入或取得外国国籍的，即自动丧失中国国籍。 第十条中国公民具有下列条件之一的，可以经申请批准退出中国国籍： 一、外国人的近亲属； 二、定居在外国的； 三、有其它正当理由。 第十一条申请退出中国国籍获得批准的，即丧失中国国籍。 第十二条国家工作人员和现役军人，不得退出中国国籍。

第十三条曾有过中国国籍的外国人，具有正当理由，可以申请恢复中国国籍；被批准恢复中国国籍的，不得再保留外国国籍。 第十四条中国国籍的取得、丧失和恢复，除第九条规定的以外，必须办理申请手续。未满十八周岁的人，可由其父母或其他法定代理人代为办理申请。 第十五条受理国籍申请的机关，在国内为当地市、县公安局，在国外为中国外交代表机关和领事机关。 第十六条加入、退出和恢复中国国籍的申请，由中华人民共和国公安部审批。经批准的，由公安部发给证书。 第十七条本法公布前，已经取得中国国籍的或已经丧失中国国籍的，继续有效。 第十八条本法自公布之日起施行。 申请恢复中国国籍须知 来源：公安部时间：2008年05月13日 一、申请条件 曾有过中国国籍的外国人，具有正当理由，可以申请恢复中国国籍；被批准恢复中国国籍的，不得再保留外国国籍。 二、受理、审批机关 受理恢复国籍申请的机关，在国内为当地市、县公安局；在国外为中国外交代表机关和领事机关。恢复中国国籍的申请，由中华人民共和国公安部审批；公安部授权各驻外使领馆审批外籍华人恢复中国国籍申请。 三、申请手续 （一）填写《恢复中华人民共和国国籍申请表》。 （二）提交要求恢复中国国籍的书面申请。

国籍状况申明书

国籍状况申明书 声请人姓名：_____________性别：_____出生日期：________________ 中国护照号码（如有）：________________________________________ 中国身份证号码（如有）：_____________________________________ 当地联系电话：______________________________________________ 当地住址:__________________________________________________ 《中华人民共和国国籍法》第三条规定，中华人民共和国不承认中国公民具有双重国籍；第九条规定，定居外国的中国公民，自愿加入或取得外国国籍的，即自动丧失中国国籍。 《中华人民共和国护照法》第十三条规定，申请人有下列情形之一的，护照签发机关不予签发护照：（一）不具有中华人民共和国国籍的；（二）无法证明身份的；（三）在申请过程中弄虚作假的；第十七条规定，弄虚作假骗取护照的，由护照签发机关收缴护照或者宣布护照作废；构成犯罪的，依法追究刑事责任。 如申请人为16周岁以上，请申请人在以下声明处签字： 我清楚知悉上述条款，声明本人至今为止没有自愿加入或取得除中国外的其他国家国籍。以上声明如有不实，本人将承担由此引起的一切法律责任和后果。 其他需声明事项：_______________________________________ 声明人签字：___________________日期：__________________ 如申请人为16周岁以下，请监护人在以下声明处签字： 我(系申请人的□父亲□母亲□其他法定监护人）清楚知悉上述条款，声明申请人至今为止没有自愿加入或取得除中国外的其他国家国籍。以上声明如有不实，本人将承担由此引起的一切法律责任和后果。 其他需声明事项：_______________________________________ 声明人签字：___________________日期：__________________

第三十三条 凡具有中华人民共和国国籍的人都是中华人民共和国公民

第三十三条凡具有中华人民共和国国籍的人都是中华人民共和国公民。 中华人民共和国公民在法律面前一律平等。 第三十五条中华人民共和国公民有言论、出版、集会、结社、游行、示威的自由。 第三十六条中华人民共和国公民有宗教信仰自由。 第三十七条中华人民共和国公民的人身自由不受侵犯。 第三十九条中华人民共和国公民的住宅不受侵犯。禁止非法搜查或者非法侵入公民的住宅。 第四十六条中华人民共和国公民有受教育的权利和义务。 第五十条中华人民共和国保护华侨的正当的权利和利益，保护归侨和侨眷的合法的权利和利益。 第六十二条全国人民代表大会行使下列职权： (一)修改宪法； (二)监督宪法的实施； (三)制定和修改刑事、民事、国家机构的和其他的基本法律； (四)选举中华人民共和国主席、副主席； (五)根据中华人民共和国主席的提名，决定国务院总理的人选；根据国务院总理的提名，决定国务院副总理、国务委员、各部部长、各委员会主任、审计长、秘书长的人选； (六)选举中央军事委员会主席；根据中央军事委员会主席的提名，决定中央军事委员会其他组成人员的人选； (七)选举最高人民法院院长； (八)选举最高人民检察院检察长； (九)审查和批准国民经济和社会发展计划和计划执行情况的报告； (十)审查和批准国家的预算和预算执行情况的报告； (十一)改变或者撤销全国人民代表大会常务委员会不适当的决定； (十二)批准省、自治区和直辖市的建置； (十三)决定特别行政区的设立及其制度； (十四)决定战争和和平的问题； (十五)应当由最高国家权力机关行使的其他职权。 第七十九条中华人民共和国主席、副主席由全国人民代表大会选举。