На чте­ние: 0.2 mintue

Ученые из Сент-​Эндрюсского уни­вер­си­те­та (Великобритания) пред­ло­жи­ли мил­ли­он дол­ла­ров за раз­гад­ку ста­рин­ной шах­мат­ной зада­чи. Об этом сооб­ща­ет­ся на сай­те университета.

Так назы­ва­е­мая «Задача о вось­ми фер­зях» (Eight queens puzzle) была сфор­му­ли­ро­ва­на в сере­дине девят­на­дца­то­го века. Ее суть заклю­ча­ет­ся в том, что­бы рас­ста­вить на шах­мат­ной дос­ке восемь фер­зей таким обра­зом, что­бы ни один из них не попа­дал под удар дру­го­го. Подразумевается, что ферзь бьет все клет­ки, рас­по­ло­жен­ные по вер­ти­ка­лям, гори­зон­та­лям и обе­им диагоналям.

Решение для стан­дарт­ной дос­ки в 64 клет­ки было най­де­но еще в 1850 году. С уве­ли­че­ни­ем раз­ме­ров поля и коли­че­ства фигур зада­ча услож­ня­ет­ся. Исследователи обна­ру­жи­ли, что если раз­мер дос­ки уве­ли­чить до 1000 на 1000 кле­ток, ком­пью­тер­ные про­грам­мы начи­на­ют зависать.

По мне­нию про­фес­со­ра Яна Гента (Ian Gent), тот, кто суме­ет создать алго­ритм быст­ро­го реше­ния этой зада­чи, смо­жет адап­ти­ро­вать свою про­грам­му для дру­гих про­блем, в том чис­ле и дешиф­ров­ки кодов в интернете.

Источник: 42.tut.by

Televid
Author: Televid