Menyelesaikan Sudoku dengan Python

Permainan Sudoku puzzle sangatlah populer dimainkan oleh orang saat ini, bahkan media cetak nasional setiap minggu memberikan puzzle ini kepada para pembacanya. Terkadang mudah menyelesaikannya kuis ini namun terkadang pula susah. Pada tulisan ini akan membantu pembaca untuk menyelesaikan puzzle ini.

Permainan Sudoku puzzle sangatlah populer dimainkan oleh orang saat ini, bahkan media cetak nasional setiap minggu memberikan puzzle ini kepada para pembacanya. Terkadang mudah menyelesaikannya kuis ini namun terkadang pula susah. Pada tulisan ini akan membantu pembaca untuk menyelesaikan puzzle ini.

Sudoku Puzzle

Misalkan kita memiliki Sudoku puzzle seperti pada gambar berikut ini:

Struktur Data

Dari puzzle tersebut kita buat sebuah struktur data matriks 9 x 9. Angka 0 mewakili isian kosong pada puzzle.

sudoku = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
]

Fungi Cek Baris, Kolom dan 3×3

Fungsi yang akan dibuat selanjutnya adalah untuk mengecek bilangan yang kira-kira cocok diletakkan pada kolom yang kosong. Prosesnya mengecek di setiap baris, kolom dan kotak 3 x 3.

def cek(y,x,n):
    global sudoku
    
    #cek baris
    for i in range(0,9):
        if (sudoku[y][i]) == n :
            return False
    
    # cek kolom
    for i in range(0,9):
        if (sudoku[i][x]) == n :
            return False
    
    # cek kotak 3x3
    x0 = (x//3)*3
    y0 = (y//3)*3
    for i in range(0,3):
        for j in range(0,3):
            if (sudoku[y0+i][x0+j]) == n :
                return False
    return True

Fungsi Selesai

Fungsi ini digunakan untuk melalukan penyelesaian dengan memanfaatkan fungsi cek. Setiap kotak yang kosong akan diperiksa kira-kira angka berapa antara 1-9 yang akan diletakkan. Jika angka tersebut memberikan nilai True dari fungsi cek maka akan tersebut diletakkan di kotak teserbut.

Pada fungsi ini dilakukan proses rekrusif dan backtracking. Algoritma backtracking dijalankan jika solusi tidak ditemukan maka fungsi akan mengembalikan nilainya kembali menjadi 0 dan mengulangi lagi pencarian yang tepat.

def selesai():
    global sudoku
    for y in range(9):
        for x in range(9):
            if (sudoku[y][x]) == 0 :
                for n in range(1,10):
                    if(cek(y,x,n)):
                        sudoku[y][x] = n
                        selesai()
                        sudoku[y][x] = 0
                return
    print(np.matrix(sudoku))

Solusi Sudoku Puzzle

Berikut ini adalah penyelesaian dari sudoku puzzle diatas.

[[5 3 4 6 7 8 9 1 2]
 [6 7 2 1 9 5 3 4 8]
 [1 9 8 3 4 2 5 6 7]
 [8 5 9 7 6 1 4 2 3]
 [4 2 6 8 5 3 7 9 1]
 [7 1 3 9 2 4 8 5 6]
 [9 6 1 5 3 7 2 8 4]
 [2 8 7 4 1 9 6 3 5]
 [3 4 5 2 8 6 1 7 9]]


Kode Lengkap

Berikut ini kode lengkap dari program diatas.

import numpy as np
sudoku = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
]


print("SUDOKU PUZZLE")
print(np.matrix(sudoku))

def cek(y,x,n):
    global sudoku
    
    #cek baris
    for i in range(0,9):
        if (sudoku[y][i]) == n :
            return False
    
    # cek kolom
    for i in range(0,9):
        if (sudoku[i][x]) == n :
            return False
    
    # cek kotak 3x3
    x0 = (x//3)*3
    y0 = (y//3)*3
    for i in range(0,3):
        for j in range(0,3):
            if (sudoku[y0+i][x0+j]) == n :
                return False
    return True

def selesai():
    global sudoku
    for y in range(9):
        for x in range(9):
            if (sudoku[y][x]) == 0 :
                for n in range(1,10):
                    if(cek(y,x,n)):
                        sudoku[y][x] = n
                        selesai()
                        sudoku[y][x] = 0
                return
    print(np.matrix(sudoku))


print("SUDOKU SOLUTION")
selesai()

Selamat mencoba, jika ada pertanyaan silahkan tulis di bagian komentar.

Be the first to comment

Leave a Reply

Your email address will not be published.


*