Polecamy
nauki ścisłe | 2016-02-24
Druga polska edycja fenomenalnego podręcznika biologii opracowanego przez zespół słynnych biologów amerykańskich.
człowiek | 2016-01-18
Przedstawiamy Państwu informator o Międzywydziałowych Indywidualnych Studiach Matematyczno - Przyrodniczych (MISMaP).
nauki ścisłe | 2015-11-26
Ciccarelli i White, znakomici dydaktycy i profesorowie psychologii, napisali najnowocześniejszy i najbardziej wszechstronny podręcznik wprowadzający do tej dyscypliny na świecie! To od paru lat najpopularniejszy podręcznik psychologii w Stanach Zjednoczonych.
Aktualności
technika | 2015-10-01
Świat idzie ciągle do przodu. To co wczoraj było nowością, już dziś wygląda inaczej i wymaga ulepszenia, modernizacji. Prym wiodą nowinki technologiczne, rozwiązania systemowe na miarę XXI wieku, jednym słowem innowacyjność nabrała większego znaczenia. Środowisko biznesowe coraz bardziej uświadamia sobie, że aby prowadzić działalność, przedsiębiorstwo i prowadzić je do sukcesu – trzeba być na bieżąco z tym co się dzieje w branży oraz z tym jakie ułatwienia oferuje nam rynek. W ten trend wpisują się już trzecie Międzynarodowe Targi Innowacji i Nowych Technologii INNO-TECH EXPO, które odbędą się od 15 do 16 października 2015 roku w Targach Kielce.
wszechświat | 2015-09-29
CDP.pl z przyjemnością informuje, że jest już dostępny audiobook „Marsjanin”, na podstawie bestsellerowej powieści Andy’ego Weira pod tym samym tytułem. CDP.pl jest producentem i wyłącznym dystrybutorem audiobooka w Polsce. Firma współpracuje przy projekcie ze studiem Fish Ladder & Platige Image i Juice, które zrealizowało trailer pt. "Our Greatest Adventure" wprowadzający widzów w tematykę zbliżającej się premiery filmu „Marsjanin” z Mattem Damonem w roli głównej.
wszechświat | 2015-09-29
Przeszło 100 lat temu udowodniono, że światło wywiera ciśnienie na powierzchnię, którą oświetla. W XX w. inżynierowie musieli brać ten czynnik pod uwagę, projektując trajektorie sond kosmicznych. Jednak  dopiero teraz, w XXI w., naukowcy zaczynają dostrzegać, jak wielkie możliwości otwiera przed nami zjawisko ciśnienia światła i jak można wykorzystać je w podboju kosmosu.
nauki ścisłe | 2015-09-25
Matematyka jest naprawdę ciekawa i można przekonać o tym również uczniów. Wystarczy wykorzystać nowoczesne oprogramowanie – dowodzi dr Katarzyna Winkowska-Nowak, wykładowca Uniwersytetu SWPS, prezes Warszawskiego Centrum GeoGebry i organizator Ogólnopolskich Konferencji GeoGebry.
człowiek | 2015-09-25
71,5% Polaków czuje się niewyspanym w ciągu dnia, 49,3% ma problemy z zaśnięciem, a mimo to wciąż sądzimy, że bezsenność nas nie dotyczy. 48,8%  badanych śpi na wersalkach czy sofach rozkładanych, mimo że 61,4% z nich przyznaje, że wygodne łóżko jest fundamentalnym czynnikiem decydującym o jakości snu.
technika | 2015-09-21
W poniedziałek 21 września ogłoszono wyniki Konkursu Prac Młodych Naukowców Unii Europejskiej – European Union Contest for Young Scientists (EUCYS).   Polskę reprezentowały w tym roku cztery projekty - wszystkie zostały nagrodzone!
«78910
11
1213141516»
Aktualne numery
02/2017
01/2017
Kalendarium
Marzec
24
W 1882 r. Robert Koch ogłosił w Berlinie wyodrębnienie bakterii (prątka) odpowiedzialnej za gruźlicę.
Warto przeczytać
Zmyl trop to użyteczna, ale i pełna powabu oraz przekonująca, kieszonkowa esencja wszystkiego, co chcielibyście wiedzieć o obronie przed inwigilacją.

WSPÓŁPRACUJEMY
Logowanie

Nazwa użytkownika

Hasło

Autor: Piotr Wołowik | dodano: 2012-05-28
Sudoku - cyfry w celibacie

Miliony ludzi na całym świecie straciły głowę dla tej magicznej gry. Rozwiązywanie łamigłówek sudoku nie wymaga wielkiego umysłowego wysiłku, zapewnia za to doskonałą zabawę. W Japonii, Wielkiej Brytanii czy USA wielu ludzi nie wyobraża sobie dnia bez tej logicznej krzyżówki. Niektórzy skarżą się na całkowite uzależnienie: Nie uwierzycie. Zapomniałem pójść do pracy (...) nie odebrałem dzieci ze szkoły. Miałem wyłączoną komórkę, więc nauczycielka nie mogła się do mnie dodzwonić. Wolę nie wracać do domu – zwierzają się na internetowych forach maniaków sudoku.

Reguły zabawy są proste, a do rozwiązania wystarczy odrobina zapału, trochę cierpliwości i coś do pisania. Niektórzy nauczyciele zalecają krzyżówki sudoku jako ćwiczenie rozwijające umiejętność logicznego wnioskowania, co tym samym może mieć wpływ na rozwój ilorazu inteligencji ich podopiecznych.

Samotność cyfr

Typowa układanka sudoku to kwadrat 9x9 z wydzielonymi dodatkowo 9 kwadratowymi sektorami o wymiarach 3x3. Zabawa polega na takim wypełnieniu pustych pól cyframi od 1 do 9, aby w każdym rzędzie, w każdej kolumnie i w każdym sektorze znalazło się dokładnie po jednej z cyfr od 1 do 9 (i żadna się nie powtarzała). Stąd zresztą wzięła się nazwa tej liczbowej krzyżówki: sudoku jest skrótem od Suji wa dokushin ni kagiru, co w wolnym tłumaczeniu znaczy: „Liczby muszą trwać w celibacie”.

Dla ułatwienia niektóre cyfry są ujawnione na początku zabawy. Ile? Zwykle nie więcej niż 30. Im mniej, tym zabawa trudniejsza, choć na poziom skomplikowania wpływa również ich wzajemne ułożenie.

Kiedy rozwiążemy wszystkie sudoku?

Sudoku jest odmianą matematycznych obiektów zwanych kwadratami łacińskimi (ang. latin squares) lub magicznymi. Liczby od 1 do n są w nich tak uporządkowane, że w każdym wierszu i kolumnie każda liczba występuje tylko raz. Po raz pierwszy kwadraty te zostały wprowadzone do świata matematyki przez Leonarda Eulera w 1783 roku.

To, co spędza sen z powiek najzagorzalszym maniakom sudoku, to pytanie: Co będę robił, kiedy już je wszystkie rozwiążę? Spieszymy uspokoić, że przypadek taki nikomu nie grozi. O ile można skonstruować jedynie dwa kwadraty magiczne o wymiarach 2×2, to kwadratów 3×3 jest już 12, a wraz ze wzrostem rozmiaru liczba możliwości rośnie w tempie astronomicznym. Dla kwadratu łacińskiego o wymiarze 9×9 (odpowiednik popularnego rozmiaru sudoku) możliwa liczba dostępnych uporządkowań jest ogromna. Krzyżówka sudoku nakłada jednak pewne ograniczenie na ten kwadrat.

Należy uwzględnić, że w układance japońskiego typu ograniczeniem jest jeszcze wymóg, aby każdy z wewnętrznych 9-elementowych kwadracików-regionów zawierał również niepowtarzalną permutację liczb od 1 do 9. Sprawia to, że zamiast 5524751496156892842531225600 liczba możliwych rozwiązań redukuje się do „zaledwie” 6670903752021072936960. Liczba ta, mimo że mniejsza od poprzedniej o parę rzędów wielkości, i tak jest wielkością astronomiczną. Określa ona liczbę wszystkich rozwiązań krzyżówek sudoku, jakie istnieją dla wymiarów 9 wierszy na 9 kolumn.

Jest to ogromny zbiór. Gdyby cała ludzkość (6 mld razem z niemowlętami i starcami) zajmowała się wyłącznie rozwiązywaniem sudoku i gdyby każdy przez całe życie rozwiązywał te łamigłówki w stałym tempie jednej na minutę, zajęłoby nam to – bagatelka – ponad 2 mln lat! Można więc mieć pewność, że nigdy nie zabraknie nowych łamigłówek nawet dla najbardziej nałogowego ich zwolennika.

Rozwiązywanie sudoku z punktu widzenia matematycznego należy do klasy tak zwanych problemów obliczeniowych NP-zupełnych. Są to zagadnienia, które nie mają precyzyjnie zdefiniowanego algorytmu rozwiązywania. Charakteryzują się tym, że poprawność ich rozwiązania łatwo sprawdzić, ale sposób znalezienia rozwiązania przez komputerowe algorytmy obliczeniowe rośnie w sposób wykładniczy wraz ze wzrostem zakresu elementów, wśród których poszukiwane jest optymalne rozwiązanie.

Klasycznym przykładem tego typu jest problem komiwojażera, który wyrusza w trasę i musi odwiedzić kilkanaście punktów wyszczególnionych w planie miasta, tak aby rozwieść sprzedawane produkty. Problem, przed jakim staje, to wybór najkrótszej drogi (np. z uwagi na koszt paliwa). Problemy NP-zupełne stanowią klasę zagadnień o wielkim znaczeniu naukowym i prace nad poszukiwaniem rozwiązań ich optymalizujących mają wielkie znaczenie praktyczne – oprócz możliwości ich wykorzystania do rozwiązywania łamigłówek sudoku.