Sudoku Solver With Backtracking (Part 1 – Illustration)

Sudoku, this simple numerical puzzle is really fun to solve, for me, at least. Ada beberapa rumus yang bisa dipakai untuk menyelesaikan sudoku dengan cepat (logic-based), seperti yang disediakan di www.sudokusolver.co.uk (written in javascript, and surprisingly fast). Ada cara lain untuk memecahkan sudoku tanpa menggunakan rumus-rumus logika tersebut, yaitu dengan menggunakan metode brute-force, alias mencoba semua kemungkinan hingga dicapai hasilnya, yaitu solusi dari puzzle tersebut.

Suatu hari, alkisah ada seorang programmer yang sedang dilanda kebosanan karena coding itu-itu saja (well, let’s admit it, that was me), membaca artikel tentang recursive. Tiba-tiba terlintas di benak, “this can be applied in sudoku”. Sekalian belajar recursive, kupikir, why don’t I try it?

And after hours of coding and testing, jadilah program iseng-iseng yang kuberi nama SudokuSolver (belum bisa mikirin nama yang lebih keren). The code was still ‘raw’ and the readability is very bad, with many loop and recursion. Dan aku pikir speednya masih bisa ditingkatkan dengan optimisasi code dan loop count nya. Oh, and the program is written in C# by the way.

Langsung buka-buka google. Aku baru ngeh kalo algoritma yang sudah aku buat ternyata disebut ‘backtracking’ (maklum agak ndeso).

Idenya adalah mengecek probability value dari tiap-tiap cell yang kosong dengan mengaplikasikan rule standar sudoku, that is, tidak boleh ada angka yang sama dalam satu row, satu column, dan satu zone. Jika hanya ada 1 kemungkinan value untuk mengisi cell kosong tersebut, maka value tersebut adalah solusi untuk cell tersebut.

Program mengecek empty cell satu per satu, dan mengaplikasikan rule tersebut. Puzzle belum tentu bisa selesai dalam 1 kali sweep. Program akan terus melakukan sweep ulang sampai semua cell terisi.

Yang jadi permasalahan di sini adalah, ada kemungkinan pada suatu saat program tidak dapat mengisi 1 cell pun dalam 1 sweep. Yang disebabkan oleh semua cell kosong pada saat itu memiliki lebih dari 1 kemungkinan solusi. Misalkan cell x bisa memiliki value a atau b. Untuk memastikan agar semua kemungkinan dicoba, maka program harus mencoba (guessing) mengisi cell x dengan value a atau b. Supaya gampang dipahami, kondisi ini aku sebut branch. Pada suatu saat iterasi juga dapat berhenti ketika tidak ada lagi value yang mungkin untuk suatu cell, kondisi ini aku sebut deadend.

Ketika iterasi di branch a berujung deadend (no solution), maka dapat disimpulkan bahwa branch a salah, maka program harus kembali ke kondisi di mana ada pilihan branch a dan b (backtracking), kemudian mengambil langkah b dan melanjutkan iterasi. Terus begitu hingga ditemukan solusinya. Selama puzzle yang diberikan valid (i.e. solvable), program akan memberikan solusi.

This post will be updated with some pictures, if I feel like it. The upcoming post will be the program itself in action, and maybe the 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