<![CDATA[Permainan Bintang Kejora merupakan permainan yang sama seperti permainan pergeseran angka dalam kotak berbentuk persegi (Puzzle). Jenis permainan seperti ini cenderung mudah untuk diselesaikan. Bentuk wadah bintang menyebabkan arah pergeseran akan menjadi terbatas. Permainan bintang kejora ini cukup rumit dan sukar untuk diselesaikan secara manual. Permainan ini dapat diselesaikan dengan metode heuristik, yaitu dengan menggunakan algoritma hill climbing dan algoritma A*. Sifat algoritma hill climbing adalah mencari kemungkinan-kemungkinan dari calon solusi untuk mendapatkan yang optimal bagi penyelesaian masalah dengan mencari nilai heuristik yang terkecil. Sedangkan algoritma A* membantu menemukan solusi pencarian dalam ruang keadaan dengan mempertimbangkan nilai heuristik terbesar yang dilacak sesuai node yang akan dilewati. Pembuatan perangkat lunak ini dirancang terlebih dahulu dengan menggunakan diagram State Transition Diagram, Use Case Diagram, Activity Diagram, dan Class Diagram. Perangkat lunak ini dapat memberikan penyelesaian yang optimum atas permainan bintang kejora yang nantinya menghasilkan huruf yang sebelumnya diacak menjadi tersusun membentuk sebuah kata dasar. Hasil yang didapatkan berupa langkah-langkah ditemukan solusi serta ditampilkan waktu pencarian yang dibutuhkan dalam menemukan solusi. Pencarian A* lebih cepat menemukan solusi dibandingkan Hill Climbing, karena A* mencari nilai heuristik pada jarak yang terjauh sehingga langsung tepat menuju sasaran. Kata kunci: Hill Climbing, Algoritma A*, Bintang Kejora]]>
