Ensiklopedia Sudoku · Matematik dan pengkomputeran

Matematik Sudoku

Dikemas kini 2026-10-05

Segi empat Latin dengan kotak

Dalam segi empat Latin, setiap simbol muncul sekali dalam setiap baris dan setiap lajur. Sudoku yang telah siap ialah segi empat Latin bersaiz 9 dengan satu syarat tambahan: setiap satu daripada sembilan kotak 3×3 juga mengandungi setiap digit sekali.

Sumber: Wikipedia: Latin square

Berapa banyak grid yang ada

Bertram Felgenhauer dan Frazer Jarvis mengira grid 9×9 yang siap pada 2005: terdapat 6,670,903,752,021,072,936,960 grid, kira-kira 6.67 × 10²¹. Banyak daripadanya sebenarnya grid yang sama dalam samaran. Jika dua grid dikira sebagai satu apabila satu boleh ditukar kepada yang lain dengan melabel semula digit, memutar atau memantulkan grid, atau menyusun semula baris dan lajur dengan cara yang mengekalkan kesahihan grid, yang tinggal ialah 5,472,730,538 grid yang pada asasnya berbeza, angka yang dikira 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

Tiada Sudoku 9×9 standard dengan 16 atau kurang nombor yang diberi mempunyai tepat satu jawapan. Gary McGuire, Bastian Tugemann dan Gilles Civario menunjukkan perkara ini melalui carian komputer menyeluruh dan mengumumkan keputusannya pada Januari 2012. Tujuh belas ialah minimum, bukan jaminan: banyak grid dengan 17 nombor yang diberi masih mempunyai lebih daripada satu jawapan.

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

Sudoku sebagai pewarnaan graf

Lukis satu titik bagi setiap satu daripada 81 sel dan sambungkan dua titik apabila sel-selnya berkongsi baris, lajur atau kotak. Graf Sudoku ini mempunyai 810 sambungan, dan setiap titik mempunyai tepat 20 jiran. Menyelesaikan teka-teki ini bermaksud melanjutkan warna yang ditetapkan oleh nombor yang diberi supaya titik yang bersambung tidak pernah sama warna. Sekurang-kurangnya sembilan warna diperlukan, kerana setiap baris, lajur dan kotak ialah kumpulan sembilan titik yang semuanya bersambung antara satu sama lain, dan mana-mana grid yang siap menunjukkan bahawa sembilan warna sudah mencukupi.

Sumber: Wikipedia: Sudoku graph

Sukar secara umum, pantas untuk 9×9

Bagi grid Sudoku yang boleh membesar tanpa had (n²×n² dengan kotak n×n), menentukan sama ada grid yang separa diisi boleh dilengkapkan ialah masalah NP-lengkap, satu keputusan yang diterbitkan oleh Takayuki Yato dan Takahiro Seta pada 2003. Program komputer yang cekap lazimnya menyelesaikan teka-teki 9×9 biasa dalam sebahagian kecil daripada satu saat, walaupun masa yang diambil bergantung pada program, komputer dan teka-teki itu.

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

Lihat juga

Sumber

Semua artikel →