Ensiklopedia Sudoku · Matematika dan komputasi

Matematika Sudoku

Diperbarui 2026-10-05

Persegi Latin dengan kotak

Dalam persegi Latin, setiap simbol muncul satu kali di setiap baris dan setiap kolom. Sudoku yang sudah terisi lengkap merupakan persegi Latin berukuran 9 dengan satu syarat tambahan: masing-masing dari sembilan kotak 3×3 juga memuat setiap digit satu kali.

Sumber: Wikipedia: Latin square

Berapa banyak kisi yang ada

Bertram Felgenhauer dan Frazer Jarvis menghitung kisi 9×9 yang terisi lengkap pada 2005: jumlahnya 6.670.903.752.021.072.936.960, sekitar 6,67 × 10²¹. Banyak di antaranya merupakan kisi yang sama dalam bentuk berbeda. Jika dua kisi dihitung sebagai satu ketika salah satunya dapat diubah menjadi yang lain dengan mengganti label digit, memutar atau mencerminkan, atau menyusun ulang baris dan kolom dengan cara yang menjaga keabsahan kisi, tersisa 5.472.730.538 kisi yang berbeda secara esensial, angka yang dihitung oleh Ed Russell dan Frazer Jarvis.

Sumber: Felgenhauer and Jarvis, Enumerating possible Sudoku grids (2005), OEIS A107739: number of Sudoku grids, Wikipedia: Mathematics of Sudoku

Minimum 17 petunjuk

Tidak ada Sudoku standar 9×9 dengan 16 angka awal atau kurang yang memiliki tepat satu jawaban. Gary McGuire, Bastian Tugemann, dan Gilles Civario menunjukkan hal ini melalui pencarian komputer menyeluruh dan mengumumkan hasilnya pada Januari 2012. Tujuh belas merupakan jumlah minimum, bukan jaminan: banyak kisi dengan 17 angka awal masih memiliki lebih dari satu jawaban.

Sumber: McGuire, Tugemann and Civario, There is no 16-Clue Sudoku (arXiv 1201.0749)

Sudoku sebagai pewarnaan graf

Gambar satu titik untuk masing-masing dari 81 sel dan hubungkan dua titik setiap kali sel-selnya berada dalam baris, kolom, atau kotak yang sama. Graf Sudoku ini memiliki 810 hubungan, dan setiap titik memiliki tepat 20 tetangga. Menyelesaikan teka-teki berarti memperluas pewarnaan yang sudah ditetapkan oleh angka awal sehingga titik-titik yang terhubung tidak pernah memiliki warna yang sama. Diperlukan setidaknya sembilan warna, karena setiap baris, kolom, dan kotak merupakan kelompok sembilan titik yang semuanya saling terhubung, dan kisi mana pun yang terisi lengkap menunjukkan bahwa sembilan warna sudah cukup.

Sumber: Wikipedia: Sudoku graph

Sulit secara umum, cepat untuk 9×9

Untuk kisi Sudoku yang ukurannya dapat bertambah tanpa batas (n²×n² dengan kotak n×n), menentukan apakah kisi yang terisi sebagian dapat dilengkapi merupakan masalah NP-complete, hasil yang diterbitkan Takayuki Yato dan Takahiro Seta pada 2003. Program komputer yang efisien biasanya menyelesaikan teka-teki 9×9 biasa dalam waktu kurang dari satu detik, meskipun waktunya bergantung pada program, komputer, dan teka-tekinya.

Sumber: Wikipedia: Mathematics of Sudoku, Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle

Lihat juga

Sumber

Semua artikel →