Судоку (јап. 数独, sūdoku)[1] логичка је загонетка[2][3] у облику квадратне решетке.[4] Решетка је обично формата 9×9, начињена од подрешетки 3×3 поља („региони“). На почетку је уписано неколико бројева у неколико поља. Циљ је да се решетка испуни бројевима од 1 до 9 у свим пољима. Свака колона, сваки ред и сваки потквадрат (регион) мора садржати све бројеве од 1 до 9 који се не смеју понављати. Решавање судокуа (испуњавање решетке) захтева само стрпљење и скромне логичке способности, мада неке загонетке могу бити прилично тешке.

A typical Sudoku puzzle, with nine rows and nine columns that intersect at square spaces. Some of the cells are filled with a number; others are blank cells to be solved.
Пример Судоку загонетке
The previous puzzle, showing its solution.
И њено решење

Судоку настао у Јапану 1986, затим 2005. постаје популаран у Уједињеном Краљевству, а потом и у међународним оквирима постаје игра са најбржим растом популарности. Постоји математичка теорија ове игре заснована на теорији комбинаторике и теорије графова.

Француске новине су представљале варијације судоку загонетки у 19. веку, а загонетка се појављује од 1979. у књигама слагалица под именом Место бројева.[5] Међутим, савремени судоку је почео да добија широку популарност тек 1986. године када га је објавила јапанска компанија за слагалице Николи под именом судоку, што значи „појединачан број“.[6] Први пут се појавио у америчким новинама, а затим у Тајмсу (Лондон), 2004. године, захваљујући напорима Вејна Гулда, који је осмислио компјутерски програм за брзо стварање јединствених загонетки.

Историја

уреди
 
Из новина La France, 6. јула 1895.: Упутства за слагалицу гласе: „Користите бројеве од 1 до 9 девет пута сваки да бисте довршили мрежу на такав начин да хоризонталне, вертикалне и две главне дијагоналне линије дају исти збир“.

Претходници

уреди

Слагалице са бројевима појавиле су се у новинама крајем 19. века, када су француски постављачи слагалица почели да експериментишу са уклањањем бројева из магичних квадрата. Le Siècle, париски дневни лист, објавио је 19. новембра 1892. делимично завршен магични квадрат 9×9 са подквадратима 3×3.[7] То није био судоку јер је садржавао двоцифрене бројеве и захтевао је аритметику, а не логику за решавање, али је имао кључне заједничке карактеристике: сваки ред, колона и подквадрат сабирали су се у исти број.

Дана 6. јула 1895, Le Siècle ривал, La France, усавршио је слагалицу тако да је била скоро еквивалентна модерном судоку и именовала је carré magique diabolique („ђаволички магични квадрат“). То је поједноставило слагалицу магичних квадрата 9×9 тако да сваки ред, колона и изломљене дијагонале садрже само бројеве 1–9, али не означавају подквадрате. Иако нису били обележени, сваки 3×3 подквадрат је заиста садржао бројеве 1–9, а додатно ограничење на прекинуте дијагонале довело је до само једног решења.[8]

Ове недељне загонетке биле су карактеристика француских новина као што је L'Écho de Paris око деценију, али су нестале у време Првог светског рата.[9]

Модерни судоку

уреди

Модерни судоку је највероватније анонимно дизајнирао Хауард Гарнс, 74-годишњи пензионисани архитекта и слободни конструктор слагалица из Конерсвила, Индијана, а први пут објављен 1979. од стране Dell Magazines као Место бројева (најранији познати пример модерног судокуа).[1] Гарнсово име је увек било присутно на листи сарадника у издањима Dell Pencil Puzzles and Word Games која су укључивала Место бројева и увек је било одсутна у издањима која нису.[10] Он је преминуо 1989. пре него што је добио прилику да види своје остварење као светски феномен.[10] Нејасно је да ли је Гарнс био упознат са неким од француских новина наведених изнад.

Слагалицу је у Јапану представио Маки Каџи (鍜治 真起, Kaji Maki), председник компаније Николи слагалица, у новинама Месечни Николиста у априлу 1984.[10] као Sūji wa dokushin ni kagiru (数字は独身に限る), што се може превести као „цифре морају бити појединачне“, или као „цифре су ограничене на једну појаву“ (на јапанском докушин значи „неудата особа“). Име је касније скраћено у Судоку (数独), узимајући само први канџи сложених речи да би се формирала краћа верзија.[10] „Судоку“ је регистровани жиг у Јапану[11] и слагалица се генерално назива Место бројева (ナンバープレース, Nanbāpurēsu)) или, неформалније, скраћење две речи, Num(ber) Pla(ce) (ナンプレ, Nanpure). Године 1986, Николи је увео две иновације: број давања је ограничен на не више од 32, а загонетке су постале „симетричне“ (што значи да су биле распоређене у ротационо симетричним ћелијама). Сада се објављује у главним јапанским часописима, као што је Asahi Shimbun.

Ширење изван Јапана

уреди

Године 1997, судија из Хонгконга Вејн Гулд видео је делимично завршену слагалицу у јапанској књижари. Током шест година, развио је компјутерски програм за брзу израду јединствених загонетки.[5] Знајући да британске новине имају дугу историју објављивања укрштених речи и других загонетки, промовисао је судоку у Тајмсу у Британији, који је почео са овјављивањем 12. новембра 2004 (назвавши га Су Доку). Прво писмо Тајмсу у вези са Су Докуом објављено је следећег дана, 13. новембра, од Ијана Пејна из Брентфорда, жалећи се да је због слагалице пропустио стајалиште на метроу.[12] Судоку загонетке су се брзо прошириле на друге новине као редовна тема.[5][13]

Брзи успон судокуа у Британији од релативне опскурности до насловне стране у националним новинама привукао је коментаре у медијима и пародије (као када се Г2 одељак Гардијана рекламирао као први новински додатак са судоку мрежом на свакој страници).[14] Препознајући различите психолошке привлачности лаких и тешких загонетки, Тајмс је 20. јуна 2005. представио обе, једна поред друге. Од јула 2005. Канал 4 је укључивао свакодневну судоку игру у своју телетекст услугу. Дана 2. августа, ББЦ-јев програмски водич Радио Тајмс је приказао недељни Супер судоку са мрежом 16×16.

У Сједињеним Државама, прве новине које су објавиле судоку слагалицу Вејна Гулда биле су The Conway Daily Sun (Њу Хемпшир), 2004. године.[15]

Године 2006, Судоку веб страница је објавила песму судоку поштовања писца Петера Левија,[16] али је брзо морала да уклони MP3 датотеку због густог саобраћаја. Британски и аустралијски радио преузели су песму, која ће бити приказана у британском судоку документарцу. Јапанска амбасада је такође номиновала песму за награду, а Леви је преговарао са Сонијем у Јапану да песму објави као сингл.[17]

Судоку софтвер је веома популаран на рачунарима, веб локацијама и мобилним телефонима. Долази са многим дистрибуцијама Линукса. Софтвер је такође објављен на конзолама за видео игре, као што су Нинтендо ДС, PlayStation Portable, Game Boy Advance, Xbox Live Arcade, Nook читач е-књига, Kindle Fire tablet, неколико iPod модела и iPhone. Многи Nokia телефони су такође имали судоку. Заправо, само две недеље након што је Apple Inc. дебитовао у онлајн App Store у оквиру iTunes Store 11. јула 2008. године, скоро 30 различитих Судоку игара је већ било у њој, креираних од стране разних програмера софтвера, посебно за iPhone и iPod Touch. Једна од најпопуларнијих видео игара са судокуом је Brain Age: Train Your Brain in Minutes a Day!. Критички и комерцијално добро прихваћен, изазвао је посебне похвале за имплементацију судокуа[18][19][20] и продат је у више од 8 милиона примерака широм света.[21] Због њене популарности, Нинтендо је направио другу Brain Age игру под називом Brain Age2, која има преко 100 нових судоку загонетки и других активности.

У јуну 2008. године, аустралијско суђење са поротом у вези са дрогом које је коштало преко милион аустралских долара је прекинуто када је откривено да је пет од дванаест поротника играло судоку уместо да слуша доказе.[22]

Варијанте

уреди
Нономино или судоку слагалица, као што се види у The Sunday Telegraph
И њено решење (црвени бројеви)

Варијације величина мреже или облика региона

уреди

Иако је мрежа 9×9 са 3×3 регионима далеко најчешћа, постоје многе друге варијације. Примери слагалица могу бити 4×4 мреже са 2×2 региона; 5×5 мреже са пентомино регионима су објављене под именом Логи-5; Светско првенство у слагалицама је представило мрежу 6×6 са 2×3 региона и 7×7 мрежу са шест хептомино региона и неповезаним регионом. Могуће су и веће мреже, или различити неправилни облици (под разним називима као што су Сугуру, Тектоник, Џигсо судоку итд.). Тајмс нуди „Додека судоку“ мрежу величине 12×12 са 12 области од 4×3 квадрата. Дел магазин редовно објављује слагалице 16×16 „Изазови места бројева“ (користећи бројеве 1–16 или слова А-П). Николи нуди гиганте величине 25×25 „Sudoku the Giant“. Слагалица величине 100×100 названа Судоку-зила је објављена 2010. године.[23]

Референце

уреди
  1. ^ а б Grossman, Lev (11. 3. 2013). „The Answer Men”. Time. New York. Архивирано из оригинала 1. 3. 2013. г. Приступљено 4. 3. 2013. Шаблон:Registration required
  2. ^ Arnoldy, Ben. „Sudoku Strategies”. The Christian Science Monitor. 
  3. ^ Schaschek, Sarah (22. 3. 2006). „Sudoku champ's surprise victory”. The Prague Post. Архивирано из оригинала 13. 8. 2006. г. Приступљено 18. 2. 2009. 
  4. ^ Lawler, E. L. (1985). The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization . West Sussex: John Wiley & Sons. ISBN 0-471-90413-9. 
  5. ^ а б в Smith, David (15. 5. 2005). „So you thought Sudoku came from the Land of the Rising Sun ...”. The Observer. Приступљено 13. 6. 2008. „The puzzle gripping the nation actually began at a small New York magazine 
  6. ^ Hayes, Brian (2006). „Unwed Numbers”. American Scientist. 94 (1): 12—15. doi:10.1511/2006.57.3475. 
  7. ^ Boyer, Christian (мај 2006). „Supplément de l'article "Les ancêtres français du sudoku" (PDF). Pour la Science (на језику: француски): 1—6. Архивирано из оригинала (PDF) 10. 12. 2006. г. Приступљено 3. 8. 2009. 
  8. ^ Boyer, Christian (2007). „Sudoku's French ancestors” (на језику: француски). (personal webpage). Архивирано из оригинала 10. 10. 2007. г. Приступљено 3. 8. 2009. 
  9. ^ Malvern, Jack (3. 6. 2006). „Les fiendish French beat us to Su Doku”. Times Online. London. Приступљено 16. 9. 2006. 
  10. ^ а б в г Pegg, Ed Jr. (15. 9. 2005). „Ed Pegg Jr.'s Math Games: Sudoku Variations”. MAA Online. The Mathematical Association of America. Приступљено 3. 10. 2006. 
  11. ^ „Reg. No. 5056856”. Japanese Trademark 5056856. Japan Platform for Trademark Information. Приступљено 3. 10. 2018. 
  12. ^ „The Times & The Sunday Times”. www.thetimes.co.uk (на језику: енглески). Приступљено 2023-02-08. 
  13. ^ Devlin, Keith (28—29. 1. 2012). „The Numbers Game (book review of Taking Sudoku Seriously by Jason Rosenhouse et al.)”. The Wall Street Journal. Weekend Edition. стр. C5. 
  14. ^ „G2, home of the discerning Sudoku addict”. The Guardian. London. 13. 5. 2005. Приступљено 16. 9. 2006. 
  15. ^ „Correction attached to "Inside Japan's Puzzle Palace". The New York Times. 21. 3. 2007. 
  16. ^ „Sudoku the song, by Peter Levy”. Sudoku.org.uk. 17. 8. 2006. Приступљено 5. 10. 2008. 
  17. ^ „Hit Song Has the Numbers”. The Herald Sun. 17. 8. 2006. Приступљено 5. 10. 2008. 
  18. ^ „Brain Age: Train Your Brain in Minutes a Day!”. Gamerankings.com. Архивирано из оригинала 09. 05. 2008. г. Приступљено 28. 04. 2023. 
  19. ^ „Brain Age: ... Review”. Gamespot.com. 
  20. ^ Harris, Craig (2006-04-18). „Brain Age: Train Your Brain in Minutes a Day”. IGN (на језику: енглески). Приступљено 2023-02-08. 
  21. ^ Thorsen, Tor (26. 10. 2006). „Nintendo posts $456.6 million profit”. GameSpot. Приступљено 29. 3. 2013. 
  22. ^ Knox, Malcolm (11. 6. 2008). „The game's up: jurors playing Sudoku abort trial”. The Sydney Morning Herald. Приступљено 11. 6. 2008. 
  23. ^ Eisenhauer, William (2010). Sudoku-zilla. CreateSpace. стр. 220. ISBN 978-1-4515-1049-2. 

Литература

уреди
  • Delahaye, Jean-Paul, "The Science Behind Sudoku", Scientific American magazine, June 2006.
  • Provan, J. Scott, "Sudoku: Strategy Versus Structure", American Mathematical Monthly, October 2009. Published also as a University of North Carolina technical report UNC/STOR/08/04, 2008.
  • „Backtracking - Set 7 (Sudoku)”. GeeksforGeeks (на језику: енглески). GeeksforGeeks. Архивирано из оригинала 2016-08-28. г. Приступљено 24. 12. 2016. 
  • Norvig, Peter. „Solving Every Sudoku Puzzle”. Peter Norvig (personal website) (на језику: енглески). Приступљено 24. 12. 2016. 
  • Simonis, Helmut (2005). „Sudoku as a Constraint Problem” (на језику: енглески). Cork Constraint Computation Centre at University College Cork: Helmut Simonis. CiteSeerX 10.1.1.88.2964 . „paper presented at the Eleventh International Conference on Principles and Practice of Constraint Programming 
  • Multiple Authors. „Java Constraint Programming solver” (Java). JaCoP (на језику: енглески). Krzysztof Kuchcinski & Radoslaw Szymanek. Приступљено 8. 12. 2016. 
  • Rhollor. „Sudokusolver” (C++). GitHub (на језику: енглески). Rhollor. Приступљено 8. 12. 2016. 
  • „Sudoku - Rosetta Code”. rosettacode.org. Приступљено 2021-11-30. 
  • Norvig, Peter. „Solving Every Sudoku Puzzle”. Peter Norvig (personal website) (на језику: енглески). Приступљено 24. 12. 2016. 
  • Hanson, Robert M. (16. 8. 2022). „Exact Cover Matrix” (на језику: енглески). 

Спољашње везе

уреди