<![CDATA[Sudoku merupakan teka-teki logika yang secara matematis dapat dimodelkan sebagai permasalahan kombinatorial dalam teori graf. Penelitian ini bertujuan untuk memformulasikan permainan sudoku klasik berukuran 9×9 ke dalam model graf serta menganalisis penyelesaiannya melalui pendekatan pewarnaan graf dan algoritma backtracking. Penelitian ini menggunakan kajian teoretis dengan pendekatan analisis struktural graf dan formulasi algoritmik. Setiap sel pada grid sudoku direpresentasikan sebagai simpul, sedangkan hubungan ketetanggaan berdasarkan baris, kolom, dan subgrid 3×3 direpresentasikan sebagai sisi. Hasil analisis menunjukkan bahwa graf sudoku merupakan graf reguler berderajat 20 dan memiliki bilangan kromatik χ(G)=9. Permasalahan sudoku ekuivalen dengan pewarnaan graf menggunakan sembilan warna tanpa konflik ketetanggaan. Selain itu, analisis kompleksitas menunjukkan bahwa algoritma backtracking memiliki kompleksitas waktu eksponensial dalam kasus terburuk, namun struktur graf sudoku yang memuat banyak klik berukuran maksimum menyebabkan proses pemangkasan (pruning) terjadi lebih awal. Dengan demikian, integrasi analisis struktural graf dan algoritma backtracking memberikan kerangka matematis yang sistematis dalam menjelaskan karakteristik penyelesaian sudoku. ]]>
Copyrights © 2025
