Rumusan masalah: Hitung jumlah jalur dalam grid nxn dari sudut kiri atas ke sudut kanan bawah sehingga jalur tersebut mengunjungi setiap kotak tepat satu kali. Misalnya, dalam grid 7£7, terdapat 111712 jalur seperti itu.
Algoritma dan optimasi: Kita mulai dengan algoritma backtracking langsung, dan kemudian mengoptimalkannya langkah demi langkah menggunakan observasi tentang bagaimana pencarian dapat dipangkas.
Ini adalah bagian yang saya tidak mengerti:
Optimasi 1: Dalam solusi apa pun, pertama-tama kita bergerak satu langkah ke bawah atau ke kanan. Selalu ada dua jalur yang simetris terhadap diagonal grid setelah langkah pertama. Oleh karena itu, kita dapat memutuskan bahwa pertama-tama kita selalu bergerak satu langkah ke bawah (atau ke kanan), dan akhirnya mengalikan jumlah solusi dengan dua.
Saya memahami bahwa akan ada solusi simetris sehingga kita cukup mencari setengahnya dan mengalikan angkanya dengan 2. Namun bagaimana kita menerapkannya?
Apa arti kalimat ini?:
Oleh karena itu, kita dapat memutuskan bahwa kita selalu bergerak ke bawah (atau ke kanan) terlebih dahulu.
Apakah ini berarti pergerakan pertama akan selalu ke bawah (atau ke kanan)? Pada dasarnya mengatur langkah pertama untuk rekursi dasar? Atau apakah itu berarti melakukan hal itu untuk setiap langkah rekursif? Atau apakah itu berarti sesuatu yang sama sekali berbeda. Saya mengalami banyak masalah dalam pemahaman. Mohon jelaskan secara detail.
