Sudoku Solver With Backtracking (Part 2 – The Program)

Ehm, the program itself. The program runs well, tapi menurutku masih bisa di-improve (tapi agak males aja, for now, yang penting jalan). Around 1 second for the so-called AI escargot, not so bad.

The AI escargot

Pertama-tama, info spek dari platform testingnya dulu aja:

Hardware:

  • Laptop HP Compaq CQ42 258VX
  • Intel Core i5 450M Processor @2.4GHz
  • 2GB DDR3 RAM

Software

  • Win 7 Ultimate
  • MonoDevelop (.net, C# side)

Ok, now the test results, let’s start from the easiest from all tests first. Sedikit googling dengan keyword ‘easy sudoku’ dan didapat puzzle yang kelihatannya mudah:

Easy one

Solved in 18ms, looks fast enough

Ok, that one was solved in 18ms, the fastest solution so far can be generated with my program. Kelihatannya cukup cepat. Tapi ketika dibandingkan dengan sudoku solver by logic, ternyata bisa diselesaikan dalam 17ms. Not much difference, though, membuktikan penyelesaian sudoku dengan logic bisa lebih cepat (javascript-code factor aside) for some cases, bisa dicek lebih jauh di pembahasan selanjutnya. Terlihat pada output program jumlah backtracking yang dilakukan adalah 0 kali, artinya program tidak perlu melakukan guessing, dan solusi yang dihasilkan bersifat unik (tidak ada kemungkinan lain). Kalo bingung apa itu backtracking bisa dicek di post sebelumnya.

Moving to the harder one, the AI escargot. AI escargot pernah menyandang predikat puzzle sudoku yang tersulit untuk dipecahkan, and it’s indeed hard (to solve manually, that is). And not to mention it’s visually appealing too (IMHO).

The AI escargot

914ms, not so bad

Solusi dihasilkan dalam 914ms dengan 262 kali backtracking (guessing/branching). Well, that’s fast, compared to me at least. Sudoku solver by logic menyelesaikan puzzle ini dalam kisaran 1.9 detik dengan 44 kali guessing (a lot less compared to my program). Perlu diingat juga bahwa program yang dibuat ini lebih bersifat brute-force, sehingga tidak mengimplementasikan logika untuk melakukan guessing secara efektif, yang berujung pada kurangnya efisiensi pada saat guessing (butuh 262 kali) dibandingkan dengan sudoku solver by logic. Tapi program ini bisa berjalan lebih cepat karena running di platform .net, yang meskipun tidak native masih lebih native dari javascript yang running di browser (CMIIW, and btw the browser is Google Chrome, one with faster javascript engine).

Pada pembahasan tes pertama di atas, dilakukan googling untuk mendapatkan puzzle yang ‘mudah’. Ada satu puzzle yang menarik perhatianku, karena sekilas kelihatannya tidak terlalu ‘mudah’. Clue-nya cukup sedikit, tetapi waktu dicoba di sudoku solver by logic, hasilnya didapat dalam 48ms dengan 0 guessing. And, I tested it with my program, expecting a quick result. The result was, how should I describe it, ‘jaw-dropping’, maybe?

‘Easy’ sudoku

Err, more than 2 minutes

Puzzle di atas memiliki ‘pattern’ yang membuatnya bisa diselesaikan dengan cepat dengan menggunakan rumus logika (for the logic that can be used, check out www.sudokusolver.co.uk). Penyelesaian dengan brute-force akan mengecek tiap kemungkinan, tanpa mengecek logis atau tidaknya kemungkinan tersebut.That leads to many unnecessary branches and loops, but ensures that the puzzle is solved. Di contoh ini mulai kelihatan kecepatan metode brute force-backtracking jauh lebih lambat dibandingkan metode logika. Dengan program ini hasil didapat dalam 143 detik dengan 50282 kali backtracking (yes, 50282 unnecessary loops).

Untuk puzzle yang terakhir, didapat dari Wikipedia, bersumber dari forum-forum sudoku-enthusiasts. And I randomly picked one:

The ‘golden nugget’

5.3 seconds, not bad, but not so fast

Dengan menggunakan program ini, hasil didapat dalam 5.3 detik dengan 1581 backtracking. Dengan sudoku solver by logic, hasil didapat dalam 51.5 detik dengan 234 guessing. Puzzle di atas memiliki sedikit, atau bahkan tidak memiliki ‘pattern’ yang dapat diselesaikan dengan rumus-rumus penyelesaian sudoku yang sudah diketahui. Puzzle semacam ini bisa disebut ‘logically unsolvable’, karena untuk menyelesaikan puzzle ini kita terpaksa menggunakan metode trial-and-error (like brute force). So, the program I made got an upper hand here, being run on .net platform rather than on browser like javascript.

Mungkin kelihatannya tidak adil membandingkan program yang running di atas .net dengan program javascript. Perbandingan ini hanya perbandingan kasar untuk melihat perbedaan kerja antara program yang menggunakan logic dengan program yang pure brute-force. Dan program yang dibuat juga tidak ditujukan untuk aplikasi yang serius, I made it out of curiosity when learning recursion implementation, and for killing time, himatsubushi.

That’s it, thanks for reading. Please tell me what you think. Kalau ada waktu untuk ngerapiin code-nya mungkin suatu saat nanti code-nya akan di-publish juga.

Source Code

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s