Lihat sumber bagi Sudoku

[[Fail:Sudoku-by-L2G-20050714.gif|thumb|right|250px|Permainan ''Sudoku'' (Penyelesaian boleh didapati dengan klik keatas gambar ini)]]

'''Sudoku''' ([[Bahasa Jepun]]: 数独, ''sūdoku''), kadangkala dieja '''Su Doku''', adalah permainan berdasarkan [[logik]] juga dikenali sebagai ''Number Place'' di [[Amerika Syarikat]]. Matlamat permainan [[kanonikal]] ini adalah untuk memasukkan suatu digit bernombor dari 1 ke 9 dalam satu sel grid 9X9 dengan subgrid 3X3 yang dipanggil 'kawasan' bermula dengan beberapa nombor 'diberi' dalam sesetengah sel lain. Setiap sel dan kawasan hanya boleh mempunyai satu kali sahaja suatu nombor digit dari 1 ke 9 sahaja. Menghabiskan permainan ini memerlukan kesabaran dan kemahiran berfikir secara logik. Walaupun ia mula diterbitkan pada tahun 1979, ia mula mendapat nama di Jepun pada tahun 1986 dan pada peringkat antarabangsa pada tahun 2005. Sebab mengapa popularitinya naik dengan begitu lambat masa yang diambil masih menjadi tanda tanya.

== Pengenalan ==
Peristilahan ''Sudoku'' memberi maksud "nombor bersendirian" dalam [[bahasa Jepun]]; dan merupakan hak cipta rasmi [[Nikoli]] Co. Ltd di Jepun. Penerbit Jepun yang lain biasanya merujuk permainan ini dengan gelaran ''Nanpure'' yang menjadi ''Number Place'' di dalam bahasa Inggeris Amerika. Nama ini dikatakan merupakan nama asal. Perkataan ''Sudoku'' disebut tampa apa-apa perubahan dengan pengalihan bahasa daripada Jepun ke Melayu.

Nombor-nombor yang diaplikasikan dalam ''Sudoku'' hanyalah bagi tujuan keselesaan semata-mata dan penggiraan matematik antara nombor-nombor tidak relevan sama sekali. Nombor-nombor ini boleh digantikan dengan bentuk-bentuk seperti bulatan, segi tiga dan segi empat sekalipun, asalkan ketara perbezaannya. Warna juga boleh digunakan. Majalah Sudoku ''Scramblets'' dimiliki [[Penny Press]] dan ''Sudoku Word'' milik [[Knight Features Syndicate]] menggunakan huruf abjad manakala [[Dell Magazines]] yang merupakan asal permainan ini menggunakan nombor bagi ''Number Place'' dalam majalahnya sejak tahun 1979. Dalam rencana ini, nombor digunakan. 

Daya tarikan permainan ini adalah kesenangan peraturannya untuk menghabiskan, tetapi kesusahan daya logik yang diperlukan untuk melakukannya. ''Sudoku'' disyorkan oleh sesetengah guru untuk menaikan kebolehan seseorang dalam pemikiran dan penyelesaian masalah secara logik. Taraf kesusahannya boleh ditentukan untuk para pemainnya. Permainan ini seringkali didatangkan percuma dalam sumber-sumber media seperti surat khabar dan juga boleh dicipta oleh program aplikasi komputer yang khusus bagi tujuan ini. 

Permainan ini telah mula muncul pada peringkat antarabangsa pada awal tahun [[2005]] dan menjadi popular di [[Amerika Syarikat]], [[Australia]], [[India]], [[Britain]] dan [[Israel]] dan tiba di [[Malaysia]] beberapa bulan selepas itu dengan terbitnya ia pada akhbar harian bahasa Inggeris [[The Star]]. [[Malay Mail]] dan [[New Straits Times]] dalam ''pullout''nya '6' juga kini menerbitkan Sudoku pada setiap penghujung minggu.

== Terminologi dan peraturan permainan ==

Permainan seringkali berupa grid 9×9 grid, didalami 3×3 subgrid dipanggil "kawasan" (panggillan lain merupakan "kotak", "petak", dan sebagainya). Sesetengah sel disediakan dengan nombor yang telah diisikan, dipanggil "diberi" (kadangkala "petunjuk") Matlamatnya adalah untuk mengisikan setiap sel dan kawasan sehinggalah nombor 1 sehingga 9 diisi dalam suatu kawasan kesemuanya. Setiap nombor dalam penyelesaian dengan sendirinya hanya timbul sekali dalam tiga "arah". Disebabkan itulah nama asal permainan ini wujud - Nombor Bersendirian.

== Cara penyelesaian ==

Strategi menyelesaikan permainan ini boleh dikira mempunyai kombinasi tiga proses: Pencarian, Tulis Tanda dan Analisa. 
 
[[Fail:Cross-hatching.png|thumb|200px|Kawasan 3×3 di sudut atas-kanan mesti mempunyai satu nombor 5. Dengan melihat pada ufuk dan datar anda boleh mendapati lain-lain nombor 5 dan menghampuskan semua sel kosong di atas-kanan yang tidak boleh ada nombor 5. Ini meninggalkan hanya satu sel yang boleh menerima nombor itu! (diwarnai hijau) ]]

=== Pencarian ===
Pencarian dilakukan pada permulaan permainan dan kerap kalinya pada waktu penyelesaian. Carian mungkin terpaksa dilakukan diantara banyak kali ketika analisa. Pencarian terdiri daripada dua teknik mudah:

* '''Silang-hapus:''' pencarian secara mengufuk atau menjajar untuk mengenalpasti garisan sesuatu kawasan yang mempunyai sesuatu nombor untuk dihapuskan. Proses ini diteruskan dengan mengufuk (atau menjajar). Untuk penghabisan yang lebih cepat, nombor dicari dalam urutan kekerapannya. Adalah penting untuk melakukan ini dengan sistematik, dengan menandakan nombor-nombor yang patut 1–9.

* '''Mengira 1–9 dalam kawasan, mengufuk dan menjajar untuk mengenalpasti nombor yang tiada.''' Mengira berdasarkan nombor terakhir yang dijumpai menjanjikan penyelesaikan yang lebih cepat. Ia juga menjadi nyata (biasanya dalam permainan yang lebih sukar) yang nilai angka yang patut dalam satu sel boleh dikira dengan mengira ke belakang— iaitu, mencari di dalam satu kawasan, secara menjajar dan mengufuk untuk nilai angka yang ''tidak boleh'' dinampakkan apa yang tinggal. 

Para pemain yang berpengalaman mencari "kontingensi" apabila mengira — iaitu, mencari sehingga satu lokasi nombor di dalam garisan mengufuk atau menjajar ataupun satu kawasan dengan dua atau tiga sel. Apabila kesemua sel itu berada pada garisan ufuk atau dataran yang sama ''dan'' kawasan, mereka boleh digunakan bagi tujuan hampusan semasa silang-hampus dan mengira. ([http://www.puzzle.jp/keys/sudoku_mid01-e.html Contoh di Puzzle Japan]). Yang paling sukar sekali mungkin memakan ramai kontingensi untuk dikenalpasti, mungkin pada pelbagai arah ataupun arah yang bersilangan garisannya, dan sejurus memaksa para pemain menggunakan tulis tanda seperti yang diterangkan dibawah. Permainan yang boleh diselesaikan dengan pencarian semata-mata tampa memerlukan kontingensi digelar "senang". Permainan yang lebih sukar secara definasinya tidaklah termasuk yang memerlukan kontingensi untuk diselesaikan.

[[Fail:Sudoku dot notation.png|186px|right|Diagram menunjukan penggunaan titik untuk menerangkan sel dalam satu permainan Sudoku.]]

=== Tulis tanda ===
Pencarian berhenti apabila tiada nombor-nombor lain boleh dijumpai. Dari ketika ini, adalah perlu sedikit analisis berdasarkan logik digunakan. Ramai mendapati bahawa adalah senang untuk menghalakan analisa ini dengan membuat tanda nombor-nombor yang berpotensi dalam sel-sel yang tidak bernombor. Terdapat dua cara menulis tanda: noktah dan subskrip. 

* Noktah pula adalah paten titik dengan titik di sudut bahagian tangan kiri menandakan 1 dan titik di sudut bahagian tangan kanan menandakan 9. Cara ini boleh digunakan pada permainan yang asal. Ketelitian diperlukan apabila membuat noktah kerana noktah yang disalah letak atau kesan kotoran lain boleh menyebabkan kecelaruan dan mungkin tidak senang dipadamkan dengan tidak menambah minyak kedalam api! Menggunakan pensil dengan cara ini disyorkan.
* Noktah subskrip adalah apabila nombor-nombor yang difikirkan berpotensi ditulis dalam sel kosong. Keburukan cara ini adalah kebanyakan sel-sel cetakan surat khabar terlalu kecil untuk tujuan ini. Jika para pemain menggunakan cara ini, biasanya satu salinan yang digandakan saiznya dihasilkan atau menggunakan pensel yang halus seperti mekanik. 

Cara teknik alternatif yang sesetengah mendapati lebih senang adalah menandakan sel yang "tidak mungkin" menjadi. Maka satu sel akan bermula kosong dan apabila lebihan "ketidak mungkinan" diketahui ia semakin diisi. Apabila hanya satu nilai angka tiada, itulah nilai angka yang sepatutnya.

=== Analisa ===
Dua cara mendekati analisa adalah "penghampusan nombor" dan "bagaimana-jika". 

* Dalam penghampusan nombor, kemajuan didasarkan penghampusan nombor-nombor yang difikirkan sesuai daripada satu atau lebih sel untuk meninggalkan satu pilihan. Selepas setiap jawapan dicapai, satu lagi pencarian boleh dilakukan —biasanya untuk melihat kesan nombor yang terakhir lalu. Terdapat beberapa taktik penghampusan, semuanya berdasarkan peraturan-perturan mudah diatas, yang mempunyai kepentingan dan kegunaan tertentu, termasuk:
*# '''Pemberian satu set ''n'' sel dalam mana-mana satu blok, secara mendatar atau mengufuk hanya boleh menerima nombor lain ''n''.''' Inilah asas bagi teknik "calon bagi penghampusan yang tidak tercapai" yang dibincangkan dibawah.
*# '''Setiap nombor yang dipertimbangkan, 1–9, mestilah pada akhirnya menjadi satu bentuk tersendiri yang konsisten.''' Inilah asas bagi teknik analisa yang bertaraf tinggi yang memerlukan kepekaan terhadap kemungkinan bagi satu nombor yang diberikan. Hanya sesetengah kemungkinan seperti ''"closed circuit"'' atau ''"n×n grid"'' wujud (yang dipanggil dengan nama-nama aneh seperti ''X-Wing'' atau ''Swordfish'' disamping yang lain). Jika bentuk-bentuk ini boleh dikenalpasti, penghampusan kemungkinan-kemungkinan yang dikenalpasti berada pada jangkaan luar grid kadangkala boleh dicapai. 

* Salah satu daripada taktik penghampusan adalah "penghampusan tidak terhingga". Sel-sel yang mempunyai set nombor yang sama dikatakan bertemu apabila kuantiti nombor-nombor cadangan adalah sama dengan jumlah sel-sel yang mempunyai mereka; secara terasnya, ini adalah kontingensi yang muncul secara semulajadi. Sebagai contoh, sel-sel dikatakan sama dalam satu garisan mengufuk, mendatar, atau kawasan (skop) jika dua sel ada pasangan dua nombor yang sama seperti p,q atau pasangan tiga nombor yang sama p,q,r dan tiada lagi yang lain. Letakan nombor dalam skop yang satu lagi akan menyebabkan penyelesaikan bagi sel-sel yang satu lagi tidak mungkin; maka, nombor cadangan (p,q,r) yang muncul dalam sel-sel yang tidak sama 

Salah satu taktik penyingkiran biasa adalah "pemadaman calon tak sepadan - unmatched candidate deletion". Sel boleh dianggap sepadan sekiranya bilangan nombor bagi setiap sel adalah sama dengan bilangan sel-sel yang mengandunginya; ini adalah kontigensi tidak sengaja - coincident contigencies. Contohnya, sel-sel dianggap sepadan dalam satu barisan, lajur, atau kawasan sekiranya:
- 2 sel mengandungi 2 nombor calon yang sepadan (p,q) bagi setiap satu sel dan tidak nombor lain, atau 
- 3 sel mengandungi 3 nombor calon yang sepadan (p,q,r) bagi setiap satu sel dan tidak nombor lain.
<!---
"Cells with identical sets of candidate numbers are said to be matched if the quantity of candidate numbers in each is equal to the number of cells containing them; essentially, these are perfectly coincident contingencies.  For example, cells are said to be matched within a particular row, column, or region (scope) if two cells contain the same pair of candidate numbers (p,q) and no others, or if three cells contain the same triplet of candidate numbers (p,q,r) and no others."

The placement of these numbers anywhere else in the matching scope would make a solution for the matched cells impossible; thus, the candidate numbers (p,q,r) appearing in unmatched cells in the row, column or region scope can be deleted. This principle also works with candidate number subsets—if three cells have candidates (p,q,r), (p,q), and (q,r) or even just (p,r), (q,r), and (p,q), all of the set (p,q,r) elsewhere in the scope can be deleted. The principle is true for all quantities of candidate numbers.

*A second related principle is also true — if the number of cells (in a row, column or region scope) where a set of candidate numbers only appear is equal to the quantity of candidate numbers, the cells and numbers are matched and only those numbers can appear in matched cells. Other candidates in the matched cells can be eliminated. For example, if (p,q) can only appear in 2 cells (within a specific row, column, region scope), other candidates in the 2 cells can be eliminated. 
:The first principle is based on cells where only matched numbers appear. The second is based on numbers that appear only in matched cells. The validity of either principle is demonstrated by posing the question 'Would entering the eliminated number prevent completion of the other necessary placements?' Advanced techniques carry these concepts further to include multiple rows, columns, and blocks. (See "X-wing" and "Swordfish" above.)

*In the what-if approach, a cell with only two candidate numbers is selected, and a guess is made. The steps above are repeated unless a duplication is found or a cell is left with no possible candidate, in which case the alternative candidate is the solution. In logical terms, this is known as [[reductio ad absurdum]]. ''Nishio'' is a limited form of this approach: for each candidate for a cell, the question is posed: will entering a particular number prevent completion of the other placements of that number? If the answer is yes, then that candidate can be eliminated. The what-if approach requires a pencil and [[eraser]]. This approach may be frowned on by logical purists as [[trial and error]] (and most published puzzles are built to ensure that it will never be necessary to resort to this tactic,) but it can arrive at solutions fairly rapidly. 

Ideally one needs to find a combination of techniques which avoids some of the drawbacks of the above elements. The counting of regions, rows, and columns can feel boring. Writing candidate numbers into empty cells can be time-consuming. The what-if approach can be confusing unless you are well organised. The proverbial [[Holy Grail]] is to find a technique which minimises counting, marking up, and rubbing out.

===Penyelesaian menggunakan komputer===
For [[programmer|computer programmers]], coding the search for cell values based elimination,  contingencies and multiple contingencies (required for harder ''Sudoku'') is relatively straightforward. These programs emulate the human logic to solve a puzzle without resorting to guesses.  Given the self-imposed constraints of most ''Sudoku'' publishers, this method generally succeeds. 

It is also fairly simple to build a [[backtracking]] search. Typically this involves assigning a value (say, 1, or the nearest available number to 1) to the first available cell (say, the top left hand corner) and then moves on to assign the next available value (say, 2) to the next available cell. This continues until a conflict occurs, in which case the next alternative value is used for the last cell changed. If a cell cannot be filled, the program backs up one level (from that cell) and tries the next value at the higher level (hence the name [[backtracking]]).  Although far from computationally efficient, this "[[Brute-force search|brute force]]" method will find a solution, given sufficient computation time. A standard 9×9 puzzle can typically be "solved" in under two seconds using most any programming language.  A more efficient program could keep track of potential values for cells, eliminating impossible values until only one value remains for a cell, then filling that cell in and using that information for more eliminations, and so on until the puzzle is solved. 

Another alternative uses finite domain [[constraint programming]]. A constraint program specifies the constraints of the puzzle (the fact that every number in each row, each column, and each 3×3 region must be unique, and the provided "givens"); a finite domain solver applies the constraints successively to narrow down the solution space until a solution is found. Backtracking may be applied when alternate values cannot otherwise be excluded.

A highly efficient way of solving such constraint problems is the [[Dancing Links]] Algorithm, by [[Donald Knuth]]. This method can be directly applied to solving ''Sudoku'' problems, counting all possible solutions for most puzzles in milliseconds. This is the method now preferred by many ''Sudoku'' programmers, mainly by virtue of its speed.  A very fast solver is usually required for most trial-and-error puzzle-creation algorithms.
--->

== Taraf kesukaran ==

Permainan yang disiarkan seringkali diberi taraf dari segi kesukarannya. Agak memeranjatkan, nilai yang diberikan hanya mempunyai sedikit atau tiada kaitan dengan kesukaran permainan tersebut. Permainan dengan jumlah penyelesaian minima diberikan mungkin mudah diselesaikan, dan permainan yang melebihi nombor purata penyelesaian mungkin amat sukar diselesaikan. Ianya berdasarkan kaitan nombor dan bukannya jumlah nombor yang diberikan.

Penyelesaian berkomputer boleh mengangar kesukaran bagi manusia menyelesaikannya, berdasarkan kerumitan teknik menyelesaikan yang diperlukan. Anggaran ini membenarkan penerbit menyesuaikan permainan ''Sudoku'' kepada hadiran dengan pengalaman menyelesaikan yang pelbagai. Sesetengah versi di talian menawarkan beberapa tahap kesukaran.
<!---
==Cara-cara Suduko dibuat==
It is possible to set starting grids with more than one solution and to set grids with no solution, but such are not considered proper ''Sudoku'' puzzles; like most other pure-logic puzzles, a unique solution is expected.

Building a ''Sudoku'' puzzle by hand can be performed efficiently by pre-determining the locations of the givens and assigning them values only as needed to make deductive progress.  Such an undefined given can be assumed to not hold any particular value as long as it is given a different value before construction is completed; the solver will be able to make the same deductions stemming from such assumptions, as at that point the given is very much defined as something else.  This technique gives the constructor greater control over the flow of puzzle solving, leading the solver along the same path the compiler used in building the puzzle.  (This technique is adaptable to composing puzzles other than ''Sudoku'' as well.)  Great caution is required, however, as failing to recognize where a number can be logically deduced at any point in construction—regardless of how tortuous that logic may be—can result in an unsolvable puzzle when defining a future given contradicts what has already been built.  Building a ''Sudoku'' with symmetrical givens is a simple matter of placing the undefined givens in a symmetrical pattern to begin with.

It is commonly believed that [[Dell Magazines|Dell]] ''Number Place'' puzzles are computer-generated; they typically have over 30 givens placed in an apparently random scatter, some of which can possibly be deduced from other givens. They also have no authoring credits — that is, the name of the constructor is not printed with any puzzle. [[Wei-Hwa Huang]] claims that he was commissioned by Dell to write a Number Place puzzle generator in the winter of 2000; prior to that, he was told, the puzzles were hand-made. The puzzle generator was written with [[Visual C Plus Plus|Visual C++]], and although it had options to generate a more Japanese-style puzzle, with [[symmetry]] [[constraints]] and fewer numbers, Dell opted not to use those features, at least not until their recent publication of ''Sudoku''-only magazines.

[[Nikoli]] ''Sudoku'' are hand-constructed, with the author being credited beside each puzzle; the givens are always found in a symmetrical pattern.  Dell ''Number Place Challenger'' (see Variants below) puzzles also list author credits. The ''Sudoku'' puzzles printed in most UK newspapers are apparently computer-generated but employ symmetrical givens; ''[[The Guardian]]'' licenses and publishes Nikoli-constructed ''Sudoku'' puzzles, though it does not include authoring credits. The Guardian famously claimed that because they were hand-constructed, their puzzles would contain "imperceptible [[witticism]]s" that would be very unlikely in computer-generated ''Sudoku''.  The challenge to ''Sudoku'' programmers is teaching a program how to build ''clever'' puzzles, such that they may be indistinguishable from those constructed by humans; Wayne Gould required six years of tweaking his popular program before he believed he achieved that level.

==Kelainan==
[[Image:Nonominosudoku.JPG|thumb|200px|A nonomino ''Sudoku'' puzzle]]

Sungguhpun grid 9×9 dengan 3×3 kawasan merupakan bentuk yang paling lazim dijumpai, namun sudoku juga ada pelbagai variasi: sample puzzles can be 4×4 grids with 2×2 regions; 5×5 grids with [[pentomino]] regions have been published under the name ''Logi-5''; the [[World Puzzle Championship]] has previously featured a 6×6 grid with 2×3 regions and a 7×7 grid with six [[heptomino]] regions and a disjoint region; Daily SuDoku features new 4×4, 6×6, and simpler 9×9 grids every day as ''Daily SuDoku for Kids''. [http://www.dailysudoku.co.uk/sudoku/index.shtml]  Even the 9×9 grid is not always standard, with [[Ebb]] regularly publishing some of those with [[nonomino]] regions; the 2005 [[U.S. Puzzle Championship]] had a ''Sudoku'' with [[parallelogram]] regions that wrapped around the outer border of the puzzle, as if the grid were [[torus|toroidal]].  Larger grids are also possible, with Daily SuDoku's 12×12-grid ''Monster SuDoku'' [http://www.dailysudoku.co.uk/sudoku/index.shtml], Dell regularly publishing 16×16 ''Number Place Challenger'' puzzles, and Nikoli proffering 25×25 ''Sudoku the Giant'' [[Behemoth|behemoths]].

Another common variant is for additional restrictions to be enforced on the placement of numbers beyond the usual row, column, and region requirements.  Often the restriction takes the form of an extra "dimension"; the most common is for the numbers in the main diagonals of the grid to also be required to be unique.  The aforementioned ''Number Place Challenger'' puzzles are all of this variant, as are the ''Sudoku X'' puzzles in the ''[[Daily Mail]]'', which use 6×6 grids.  The ''Daily Mail'' also features ''Super Sudoku X'' in its ''Weekend'' magazine: an 8×8 grid in which rows, columns, main diagonals, 2×4 blocks and 4×2 blocks contain each number once.  Another dimension in use is digits with the same relative location within their respective regions; such puzzles are usually printed in colour, with each disjoint group sharing one colour for clarity.

Other kinds of extra restrictions can be mathematical in nature, such as requiring the numbers in delineated segments of the grid to have specific sums or products (an example of the former being ''[[Killer Su Doku]]'' in ''[[The Times]]''), demarcating all places arithmetically adjacent digits appear orthogonally adjacent in the grid, providing the parity of all cells, requiring the [[Lo Shu Square]] to appear in the solution, and so on.  Some such variants forsake standard givens entirely.

Puzzles constructed from multiple ''Sudoku'' grids are commonly seen.  Five 9×9 grids which overlap at the corner regions in the shape of a [[quincunx]] is known in Japan as ''Gattai 5'' (five merged) ''Sudoku''. In ''[[The Times]]'' and ''[[The Sydney Morning Herald]]'' this form of puzzle is known as ''Samurai SuDoku''.  [http://sudoku.top-notch.co.uk/gattai5.asp]  Puzzles with twenty or more overlapping grids are not uncommon in some Japanese publications.  Often, no givens are to be found in overlapping regions.  Sequential grids, as opposed to overlapping, are also published, with values in specific locations in grids needing to be transferred to others.

Alphabetical variations, which use letters rather than numbers, have also emerged; of course, there is no functional difference in the puzzle unless the letters spell something.  Recent variants have just that, often in the form of a word reading along a main diagonal once solved; determining the word in advance can be viewed as a solving aid.  The ''Code Doku'' [http://www.mathrec.org/sudoku] devised by Steve Schaefer has an entire sentence embedded into the puzzle; the ''Super Wordoku'' [http://sudoku.top-notch.co.uk/superwordoku.asp] from Top Notch embeds two 9-letter words, one on each diagonal.  It is debatable whether these are true ''Sudoku'' puzzles: although they purportedly have a single <i>linguistically</i> valid solution, they cannot necessarily be solved entirely by logic, requiring the solver to determine the embedded words.  Top Notch claim this as a feature designed to defeat solving programs.

Here are some of the more notable unique variations:

* A three-dimensional ''Sudoku'' puzzle was invented by [[Dion Church]] and published in the [[Daily Telegraph]] in [[May 2005]].
* The 2005 U.S. Puzzle Championship includes a variant called ''Digital Number Place'': rather than givens, most cells contain a partial given—a segment of a number, with the numbers drawn as if part of a [[seven-segment display]].
* [[Wei-Hwa Huang]] created a meta-''Sudoku'', where the object is to finish drawing the 5×5 grid's pentomino-region borders so as to leave a uniquely solvable puzzle with no identically-shaped regions.

==Matematik ''Sudoku''==

The general problem of solving ''Sudoku'' puzzles on ''n''<sup>2</sup> x ''n''<sup>2</sup> boards of ''n'' x ''n'' blocks is known to be [[NP-complete]] [http://www.phil.uu.nl/~oostrom/cki20/02-03/japansepuzzles/ASP.pdf]. This gives some indication of why ''Sudoku'' is difficult to solve, although on boards of finite size the problem is finite and can be solved by a [[deterministic finite automaton]] that knows the entire [[game tree]].

Solving ''Sudoku'' puzzles can be expressed as a [[graph coloring|graph colouring]] problem. The aim of the puzzle in its standard form is to construct a proper 9-colouring of a particular graph, given a partial 9-colouring. The graph in question has 81 vertices, one vertex for each cell of the grid. The vertices can be labelled with the ordered pairs
<math>(x,\, y)</math>, where x and y are integers between 1 and 9. In this case, two distinct vertices labelled by <math>(x,\, y)</math> and <math>(x',\, y')</math> are joined by an edge if and only if:
* '''X = X' ''' 
* <math> y = y'\,</math>  or,
* <math> \lceil x/3 \rceil = \lceil x'/3 \rceil</math> and <math> \lceil y/3 \rceil = \lceil y'/3 \rceil</math>
The puzzle is then completed by assigning an integer between 1 and 9 to each vertex, in such a way that vertices that are joined by an edge do not have the same integer assigned to them.

A valid ''Sudoku'' solution grid is also a [[Latin square]]. There are significantly fewer valid ''Sudoku'' solution grids than Latin squares because ''Sudoku'' imposes the additional regional constraint.  Nonetheless, the number of valid ''Sudoku'' solution grids for the standard 9×9 grid was calculated by Bertram Felgenhauer in 2005 to be 6,670,903,752,021,072,936,960 [http://www.shef.ac.uk/~pm1afj/sudoku/] {{OEIS|id=A107739}}. This number is equal to 9! × 72<sup>2</sup> × 2<sup>7</sup> × 27,704,267,971, the last factor of which is [[prime number|prime]]. The result was derived through logic and [[brute force]] [[computation]]. The derivation of this result was considerably simplified by analysis provided by Frazer Jarvis and the figure has been confirmed independently by Ed Russell. Russell and Jarvis also showed that when symmetries were taken into account, there were 5,472,730,538 solutions [http://www.shef.ac.uk/~pm1afj/sudoku/sudgroup.html] {{OEIS|id=A109741}}. The number of valid ''Sudoku'' solution grids for the 16×16 derivation is not known.

The maximum number of givens that can be provided while still not rendering the solution unique is four short of a full grid; if two instances of two numbers each are missing and the cells they are to occupy form the corners of an orthogonal rectangle, and exactly two of these cells are within one region, there are two ways the numbers can be assigned.  Since this applies to Latin squares in general, most variants of ''Sudoku'' have the same maximum.  The inverse problem—the fewest givens that render a solution unique—is [[unsolved problems in mathematics|unsolved]], although the lowest number yet found for the standard variation without a symmetry constraint is 17, a number of which have been found by Japanese puzzle enthusiasts [http://www2.ic-net.or.jp/~takaken/auto/guest/bbs46.html] [http://www.csse.uwa.edu.au/~gordon/sudokumin.php], and 18 with the givens in rotationally symmetric cells.

For more results and conjectures, see the [[Mathematics_of_Sudoku|Mathematics of Sudoku]] page.

==Sejarah==

The puzzle was designed by Howard Garns, a retired architect and freelance puzzle constructor, and first published in 1979.  Although likely inspired by the [[Latin square]] invention of [[Leonhard Euler]], Garns added a third dimension (the regional restriction) to the mathematical construct and (unlike Euler) presented the creation as a puzzle, providing a partially-completed grid and requiring the solver to fill in the rest.  The puzzle was first published in [[New York]] by the specialist puzzle publisher [[Dell Magazines]] in its magazine ''Dell Pencil Puzzles and Word Games'', under the title ''Number Place'' (which we can only assume Garns named it).

The puzzle was introduced in Japan by [[Nikoli]] in the paper ''Monthly Nikolist'' in April [[1984]] as ''Suuji wa dokushin ni kagiru'' (数字は独身に限る), which can be translated as "the numbers must be single" or "the numbers must occur only once" (独身 literally means "single; celibate; unmarried"). The puzzle was named by Kaji Maki (鍜治 真起), the president of Nikoli. At a later date, the name was abbreviated to ''Sudoku'' (数独, pronounced ''SUE-dough-coo''; sū = number, doku = single); it is a common practice in Japanese to take only the first [[kanji]] of compound words to form a shorter version. In 1986, Nikoli introduced two innovations which guaranteed the popularity of the puzzle: the number of givens was restricted to no more than 32 and puzzles became "symmetrical" (meaning the givens were distributed in rotationally symmetric cells). It is now published in mainstream Japanese periodicals, such as the ''[[Asahi Shimbun]]''. Within Japan, Nikoli still holds the trademark for the name ''Sudoku''; other publications in Japan use alternative names.

In [[1989]], [[Loadstar]]/[[Softdisk|Softdisk Publishing]] published ''DigitHunt'' on the [[Commodore_64|Commodore 64]], which was apparently the first home computer version of ''Sudoku''.  At least [http://www.coregames.com/DPS3.htm one publisher] still uses that title.

Yoshimitsu Kanai published his computerized puzzle generator under the name ''Single Number'' (the English translation of 'sūdoku') for the [[Apple Macintosh]] [http://www.mathsisfun.net/SingleNumber.sit] in  [[1995]] in Japanese and English, and in [[1996]] for the [[Palm (PDA)]] [http://www.mathsisfun.net/SingleNumber.prc].

Bringing the process full-circle, [[Dell Magazines]], which publishes the original ''Number Place'' puzzle, now also publishes two ''Sudoku'' magazines: <i>Original Sudoku</i> and <i>Extreme Sudoku</i>.  Additionally, [[Kappa Publishing Group|Kappa]] reprints Nikoli ''Sudoku'' in ''[[GAMES Magazine]]'' under the name ''Squared Away''; the ''[[New York Post]]'', ''[[USA Today]]'', ''[[The Boston Globe]]'', ''[[Washington Post]]'', and ''[[San Francisco Chronicle]]'' now also publish the puzzle.  It is also often included in puzzle anthologies, such as ''The Giant 1001 Puzzle Book'' (under the title ''Nine Numbers'').

Within the context of puzzle history, parallels are often cited to [[Rubik's Cube]], another [[:Category:logic puzzles|logic puzzle]] popular in the [[1980s]].  ''Sudoku'' has been called the "[http://www.conceptispuzzles.com/articles/sudoku/ Rubik's cube of the 21st century]".

===Popularasi dalam media massa===

In [[1997]], retired Hong Kong judge [[Wayne Gould]], 59, a [[New Zealand]]er, was enticed by seeing a partly completed puzzle in a Japanese bookshop. He went on to develop a computer program to produce puzzles quickly; this took over six years.  Knowing that [[United Kingdom|British]] [[newspaper]]s have a long history of publishing [[crossword]]s and other puzzles, he promoted ''Sudoku'' to ''The Times'' in Britain, which launched it on [[12 November]] [[2004]] (calling it ''Su Doku''). The puzzles by Pappocom, Gould's software house, have been printed daily in the ''Times'' ever since. 

Three days later ''The Daily Mail'' began to publish the puzzle under the name "Codenumber". ''The Daily Telegraph'' introduced its first ''Sudoku'' by its puzzle compiler Michael Mepham on [[19 January]] [[2005]] and other Telegraph Group newspapers took it up very quickly. Nationwide News Pty Ltd began publishing the puzzle in ''The Daily Telegraph'' of [[Sydney]] on [[20 May]] [[2005]]; five puzzles with solutions were printed that day. The immense surge in popularity of ''Sudoku'' in British newspapers and internationally has led to it being dubbed in the world media in 2005 variously as "the [[Rubik's cube]] of the 21st century" or the "fastest growing puzzle in the world".

There is no doubt that it was not until ''The Daily Telegraph'' introduced the puzzle on a daily basis on [[23 February]] [[2005]] with the full front-page treatment advertising the fact, that the other UK national newspapers began to take real interest. The ''Telegraph'' continued to splash the puzzle on its front page, realizing that it was gaining sales simply by its presence. Until then the ''Times'' had kept very quiet about the huge daily interest that its daily ''Sudoku'' competition had aroused. That newspaper already had plans for taking advantage of their market lead, and a first ''Sudoku'' book was already on the stocks before any of the other national papers had realised just how popular ''Sudoku'' might be.

By April and May 2005 the puzzle had become popular in these publications and it was rapidly introduced to several other national British newspapers including ''[[The Independent]]'', ''[[The Guardian]]'', ''[[The Sun]]'' (where it was labelled ''Sun Doku''), and ''[[The Daily Mirror]]''. As the name ''Sudoku'' became well-known in Britain, the ''Daily Mail'' adopted it in place of its earlier name "Codenumber". Newspapers competed to promote their ''Sudoku'' puzzles, with ''The Times'' and the ''Daily Mail'' each claiming to have been the first to feature ''Sudoku'', and ''The Guardian'' claiming (though perhaps ironically) that its hand-made puzzles, licensed from [[Nikoli]], offered a superior experience (complete with "almost imperceptible witticisms") to the computer-generated grids found in other papers.

The rapid rise of ''Sudoku'' from relative obscurity in Britain to a front-page feature in national newspapers attracted commentary in the media (see ''References'' below) and parody (such as when ''The Guardian'''s ''G2'' section advertised itself as the first newspaper supplement with a ''Sudoku'' grid on every page [http://www.guardian.co.uk/g2/story/0,,1482817,00.html]). ''Sudoku'' became particularly prominent in newspapers soon after the [[United Kingdom general election, 2005|2005 general election]] leading some commentators to suggest that it was filling the gaps previously occupied by election coverage. A simpler explanation is that the puzzle attracts and retains readers—''Sudoku'' players report an increasing sense of satisfaction as a puzzle approaches completion. Recognizing the different psychological appeals of easy and difficult puzzles [[The Times]] introduced both side by side on [[20 June]] [[2005]]. From July 2005 [[Channel 4]] included a daily ''Sudoku'' game in their [[Teletext]] service (at page 142). On 2nd August 2005 the BBC's programme guide [[Radio Times]] started to feature a weekly Super Sudoku.

As a one-off, the world's first live TV ''Sudoku'' show, ''Sudoku Live'', was broadcast on [[1 July]] [[2005]] on [[Sky One]]. It was presented by [[Carol Vorderman]]. Nine teams of nine players (with one [[celebrity]] in each team) representing geographical regions competed to solve a puzzle. Each player had a hand-held device for entering numbers corresponding to answers for four cells. Conferring was permitted although the lack of acquaintance of the players with each other inhibited an analytical discussion. The audience at home was in a separate interactive competition.
A Sky One [http://www.skyone.co.uk/programme/pgefeature.aspx?pid=48&fid=129 publicity stunt] to promote the programme with the world's largest ''Sudoku'' puzzle went awry when the 275 foot (84 m) square puzzle was found to have 1,905 correct solutions.  The puzzle was carved into a hillside in [[Chipping Sodbury]], near [[Bristol]], [[England]], in view of the [[M4 motorway]].

[[CBS]] has run several stories concerning Sudoku, including on the [[Early Show]] in [[Summer 2005]], and on the [[CBS Evening News]] that autumn, on October 26th.
--->
== Lihat juga ==
* [[Matematik Sudoku]]
* [[Senarai akhbar yang menonjolkan Sudoku]]
* [[Senarai jenis teka-teki Nikoli]]

== Rujukan ==
<!-- NB: References are *not* the same thing as external links; they are resources used to write, or useful in verifying, the article's content -->
* [http://www.nikoli.co.jp/puzzles/1/index_text-e.htm Rules and history from the Nikoli website] {{Webarchive|url=https://web.archive.org/web/20060613025508/http://nikoli.co.jp/puzzles/1/index_text-e.htm |date=2006-06-13 }}
* [http://www.puzzle.jp/keys/sudoku_keys-e.html Keys to Solution at Puzzle Japan]
* [http://www.pro.or.jp/~fuji/sudoku/makesudoku/sudoku01.html.en Let's Make Sudoku!] – Explains step-by-step how to make ''Sudoku'' puzzles by hand.
* [https://web.archive.org/web/20051003205240/http://www.maa.org/editorial/mathgames/mathgames_09_05_05.html Sudoku Variations article at MAA Online]; also includes the history of the puzzle's invention
* [http://www.phil.uu.nl/~oostrom/cki20/02-03/japansepuzzles/ASP.pdf Complexity and Completeness of Finding Another Solution and its Application to Puzzles] {{Webarchive|url=https://web.archive.org/web/20060716101717/http://www.phil.uu.nl/%7Eoostrom/cki20/02-03/japansepuzzles/ASP.pdf |date=2006-07-16 }} Mathematical reference proving NP-completeness.
* [http://www.shef.ac.uk/~pm1afj/sudoku/ Frazer Jarvis's Sudoku page] {{Webarchive|url=https://web.archive.org/web/20060220090906/http://www.shef.ac.uk/~pm1afj/sudoku/ |date=2006-02-20 }} Contains programs, data, an article with Bertram Felgenhauer detailing the enumeration of ''Sudoku'' grids, and the results of Ed Russell.
* [http://www.sudoku.org.uk/PDF/Solving_Sudoku.pdf A step-by-step guide to Sudoku by Michael Mepham.]
* Commentary on the sudden popularity of ''Sudoku'' in Britain:
** [http://news.bbc.co.uk/1/hi/magazine/4469719.stm The puzzling popularity of Su Doku] ([[BBC News]], [[22 April]] [[2005]])
** [http://observer.guardian.co.uk/uk_news/story/0,6903,1484328,00.html So you thought Sudoku came from the Land of the Rising Sun…] (''[[The Observer]]'', [[15 May]] [[2005]])
** [http://www.economist.com/displaystory.cfm?story_id=3992476 Do you sudoku?] (''[[The Economist]]'', [[19 May]] [[2005]])

== Pautan luar ==
*{{curlie|Games/Puzzles/Brain_Teasers/Sudoku|Sudoku}} –Senarai pautan Sudoku aktif
*[http://news.bbc.co.uk/2/hi/asia-pacific/6745433.stm 'Father of Sudoku' puzzles next move] ([[BBC]])
*Platform untuk bersaing di [https://www.livesudoku.com/ sudoku] di peringkat antarabangsa

[[Kategori:Teka-teki logik]]
[[Kategori:Segi empat sama Latin]]