Hvað er lágmarksfjöldi vísbendinga sem Sudoku getur haft?
Síðast uppfært
Gilt Sudoku - Eitt með nákvæmlega einni lausn - Krefst að minnsta kosti 17 gefinna tölustafa. Þetta er sannað stærðfræðilegt niðurstaða. Hverjir púsl með 16 eða færri vísbendingum hafa annaðhvort margar lausnir eða enga alls.
2012 Sönnunin
Árið 2012 birtu Gary McGuire, Bastian Tugemann og Gilles Civario við University College Dublin sönnun fyrir að engin gild 16-vísbendinga Sudoku sé til. Verk þeirra var aðallega reiknilegt: þeir leituðu alls rúms mögulegra 16-vísbendinga gríða og staðfestu að engin framleiddi einkvæðilega lausn. Leitin krafðist um það bil 7 milljón kjarna-stunda af reikningi.
Áður en þetta var víða talið að 17 væri lágmarkið og þúsundir 17-vísbendinga þrauta höfðu verið fundnar tilraunlega. Lið McGuire framleiddi fyrstu ströngu sönnunina að 16 sé ómögulegt.
Hvernig 17-vísbendinga þrautir líta út
17-vísbendingaþrautir eru afar strjála - 17 gefnar tölur í 81 reitum, skilja 64 tóma. Þær eru meðal erfiðustu þrauta að leysa og krefja venjulega háþróaðar tæknir. Að finna gildar 17-vísbendingaþrautir sjálfar krafðist áratuga tölvunarfræðilegs átaks. Frá og með skrifunni, yfir 49,000 í raun öðruvísi 17-vísbendinga Suðoku þrautir eru þekktar.
Hvað þetta þýðir fyrir þrautarhönnun
Birtar þrautir ætlaðar mannlegum leysendum fara sjaldan undir 22 vísbendingar. Expert og Master erfiðleika þrautir nota venjulega 22-27 gefna tölustafi, á meðan Easy þrautir nota 36-45. 17-vísbendinga lágmarkið er fræðileg mörk - Í framkvæmd, leysanleiki með góðri tækni og ánægjuleg leysingarleið skipta miklu meira máli en vísbendingartala ein og sér.