Sakkfeladványra mozdulhatnak rá a világ legjobb programozói

Sakkfeladványra mozdulhatnak rá a világ legjobb programozói

 

Az először 1848-ban felvetett nyolckirálynő-probléma ismerősen csenghet a sakkfeladványokban járatosak számára, nemsokára azonban jó pár programozó is megismerheti, a University of St Andrews skót egyetem informatikusai ugyanis egymillió dollárt ajánlottak fel annak, akinek a programja képes megoldani a feladványt – írja a Daily Mail.

A nyolckirálynő-probléma egy olyan sakkfeladvány, melyben nyolc vezért kell úgy elhelyezni egy 8x8-as sakktáblán, hogy azok a sakk szabályai szerint ne üssék egymást, azaz ne legyen két bábu azonos sorban, oszlopban, vagy átlóban. A probléma első megoldását Franz Nauck adta 1850-ben, azóta pedig sok matematikus foglalkozott már vele, illetve általánosított változatával, az n királynő problémával, melynél számú vezért kell elhelyezni egy nxn-es táblán.

Az eredeti problémának összesen 92 megoldása van – vagy 12, ha csak azokat vesszük, melyek elforgatással nem egymásba vihetők – , a 8 vezért ugyanakkor

négymilliárd-négyszázhuszonhatmillió-százhatvanötezer-háromszázhatvannyolcféle

módon lehet letenni a 8x8-as táblára, így a számítógépes programoknak meglehetősen nehéz dolga van vele. Ezt ugyan különféle módszerekkel lehet csökkenteni, azonban az királynő problémánál a vezérek és a tábla növelésével annyival megnőnek a lehetőségek, hogy a St Andrew informatikusai szerint egy 1000x1000-es tábla esetében már képtelen feldolgozni őket a számítógép.

Éppen ezért döntöttek úgy, hogy egymillió dollárt ajánlanak fel annak, aki olyan programot ír, ami gyorsan képes megoldani a feladványt, ugyanis úgy vélik, hogy egy ilyen program más, eddig megoldhatatlannak hitt problémáknál is tudna segíteni. Képes lenne például megállapítani, hogy melyik az a legnagyobb csoport a Facebook ismerőseink közül, akik nem ismerik egymást, de emellett például fel lehetne törni vele az online tranzakcióinkat biztonságban tartó programokat is.

Eddig még soha senkinek nem sikerült akár közel kerülnie ahhoz, hogy egy ilyen programot csináljon.

– mondta Dr. Peter Nightingale az egyetemi csoport egyik tagja, aki szerint egyelőre azon az állásponton vannak, hogy ez nem is lehetséges.

A feladványt egyébként önök is megkísérelhetik megoldani ezen a linken, ha pedig az összes megoldásra kíváncsiak, akkor ide kattintsanak.

 

Can you solve the Queens Puzzle? Computer coders that can crack the chess-based game could earn themselves a $1 million prize (but experts warn it could take 1,000 years)

  • The 1850 puzzle challenges a player to place eight queens on a standard board
  • No pieces should be able to attack one other moving diagonally or horizontally
  • The game has since been expanded to theoretically larger and larger boards  
  • Experts believe any computer that can crack it would be extremely valuable
  • It could accomplish nearly impossible tasks like defeating online security 

 

prize of $1 million (£776,478) could be taken home by anyone who can build an app to solve a supposedly 'simple' chess puzzle.

Computer scientists at the University of St Andrews are challenging coders to crack the maths behind the solution to grab the cash prize.

They believe a programme capable of achieving this would be so powerful it could accomplish nearly impossible tasks, including defeating online security measures.

Their latest research suggests that it could take the software thousands of years to complete the calculations, however.

Scroll down for video 

 

an you solve the Queens Puzzle? This game, programmed by Ronald Daenzer and provided viaMurderous Maths, gives you a helping hand

Professor Ian Gent and his colleagues became interested in the Queens Puzzle after a friend challenged Professor Gent to solve it on Facebook.

Although the problem has been solved by humans, once the chess board involved increases to a large size no computer software can solve it.

The team concluded that the rewards to be reaped by such a programme would be immense, not least in financial terms, with firms rushing to use it to offer technological solutions to many modern problems.

The $1 million prize money itself is being offered by the Clay Mathematics Institute in Peterborough, New Hampshire.

The reason these problems are so difficult for computer programmes is that there are so many options to consider - it can take years.

They use a process called backtracking, an algorithm where every possible option is considered and then backed away from until the correct solution is found.

THE QUEENS PUZZLE

Devised in 1850, the Queens Puzzle originally challenged a player to place eight queens on a standard eight by eight square chessboard so that no two queens could attack each other.

This means putting one queen in each row, so that no two queens are in the same column, and no two queens in the same diagonal.

There is more than one potential solution.

The game has since been expanded as way of exploring complex mathematical computations.

The St Andrew's team found that when the chess board reached 1000 squares by 1000, computer programmes could no longer cope with the vast number of options.

This means that they sank into a potentially eternal struggle akin to the fictional super computer Deep Thought in Douglas Adams' Hitchhiker's Guide to the Galaxy.

Professor Gent said: 'If you could write a computer programme that could solve the problem really fast, you could adapt it to solve many of the most important problems that affect us all daily.

'This includes trivial challenges like working out the largest group of your Facebook friends who don't know each other.

 

 

 

Read previous post:
Leszkó ezüst Csehországban

All.pgn http://www.chess.cz/www/mladez/reprezentace/me-unie.html

September 2017 FIDE Rating List

FIDE Top 100 Players More than just the 15 Elo that he earned. Maxime Vachier-Lagrave scored his greatest tournament victory...

Gaál Zsóka világbajnoki ezüstérmes!

  Felkészítői Istvándi Lajos nemzetközi mester (TVSE), munkáját segítette Kosztolánczi Gyula FIDE-mester, Varga Zoltán nemzetközi nagymester (GM) (Honvéd) és Kustár...

FIDE World Cup 2017 Live Games PGN RESULTS

FIDE World Cup 2017 (Tbilisi GEO) Sun 3rd Sep 2017 - Wed 27th Sep 2017 - Official  FIDE World Cup...

In 1950, Alan Turing Created a Chess Computer Program That Prefigured A.I

Close