Solving Sudoku with MATLAB

Repost dari : mathworks

Cleve’s Corner: Penyelesaian Sudoku dengan MATLAB

Oleh Cleve Moler Pemecah teka-teki manusia dan program komputer sangat berbeda Sudoku menggunakan teknik-teknik pemecahan. Pesona dengan menyelesaikan Sudoku dengan tangan berasal dari penemuan dan penguasaan segudang halus dan pola kombinasi yang memberikan petunjuk tentang solusi akhir. Tidaklah mudah untuk program komputer untuk menduplikasi manusia ini kemampuan pengenalan pola. Untuk alasan ini, kebanyakan program pemecahan Sudoku mengambil pendekatan yang sangat berbeda, bergantung pada komputer hampir tak terbatas kapasitas untuk melaksanakan brute force trial and error. Itulah pendekatan yang saya gunakan untuk program MATLAB ®.

The Sudoku Challenge

Seperti yang mungkin Anda ketahui, memecahkan Sudoku melibatkan mengisi sebuah 9-by-9 grid sehingga setiap baris, kolom, dan besar 3-by-3 blok berisi semua angka 1 sampai 9. Grid awal diisi dengan beberapa angka, yang dikenal sebagai petunjuk. Berbeda dengan kotak ajaib dan teka-teki angka yang lain, tidak ada aritmatika yang terlibat; unsur-unsur dalam grid Sudoku juga bisa menjadi huruf-huruf alfabet atau simbol-simbol lainnya. Gambar 1 menunjukkan grid awal. Saya terutama seperti simetri pada contoh ini, yang disebabkan oleh Gordon Royle dari University of Western Australia. Gambar 2 menunjukkan solusi.

Gambar 1.Contoh teka-teki, dengan petunjuk diperlihatkan dengan warna biru.Contoh ini terutama telah menyenangkan simetri.

Gambar 2.Teka-teki yang sudah selesai.Digit lain telah disisipkan sehingga setiap baris, kolom, dan besar 3-by-3 blok berisi angka 1 sampai 9

Memecahkan Sudoku dengan Rekursif Backtracking

Program MATLAB kami hanya menggunakan satu pola-lajang-bersama-sama dengan ilmu komputer dasar teknik, rekursif kemunduran. Untuk melihat bagaimana program itu bekerja, kita dapat menggunakan lebih sederhana 4-by-4 grid dengan 2-oleh-2 blok. Teka-teki semacam itu disebut Sudoku Shidoku bukan karena “Shi”adalah Jepang untuk “empat.” Gambar 3 menunjukkan teka-teki Shidoku pertama kami. Angka 4 sampai 6 menunjukkan solusinya. Dalam Gambar 4, yang mungkin entri, atau calon, direpresentasikan sebagai angka kecil. Sebagai contoh, baris kedua berisi sebuah “3” dan kolom pertama berisi “1”, sehingga para kandidat di posisi (2,1) adalah “2” dan “4.” Empat dari sel mengandung hanya satu kandidat. Sel-sel ini adalah lajang. Contoh pertama ini dapat diselesaikan dengan mudah dengan mengisi lajang. Pada Gambar 5, kita telah memasukkan salah satu dari lajang dan menghitung ulang para kandidat. Dalam Gambar 6, kita telah memasukkan lajang yang tersisa ketika mereka muncul untuk melengkapi solusi.

Gambar 3.Sudoku Shidoku adalah pada 4-by-4 grid.

Gambar 4.Kandidat.Calon merah adalah lajang.

Gambar 5.Memasukkan tunggal “3” dan recomputing para kandidat.

Figure 6. Insert the remaining singletons to complete the puzzle.

Teka-teki mudah dapat didefinisikan sebagai salah satu yang dapat diselesaikan dengan hanya memasukkan lajang. Dalam definisi ini, contoh pertama kami adalah mudah, tetapi contoh berikut tidak. Input array untuk teka-teki yang ditunjukkan pada Gambar 7 adalah yang dihasilkan oleh pernyataan MATLAB X = diag (1:4)

Karena tidak ada lajang dalam teka-teki ini (Gambar 8), kita akan menggunakan rekursif mundur kembali. Kami memilih salah satu dari sel-sel kosong dan ragu memasukkan salah satu kandidat.Kami telah memilih untuk mempertimbangkan sel-sel dalam urutan tersirat oleh MATLAB satu dimensi subscripting, X (:), dan coba para kandidat di urutan numerik. Jadi kami menyisipkan “3” dalam sel (2,1), menciptakan sebuah teka-teki baru (Gambar 9). Kami kemudian memanggil program rekursif.

Gambar 8.Kandidat.Tidak ada lajang

Gambar 9.Ragu-ragu memasukkan “3” untuk membuat teka-teki baru.Kemudian mundur. Teka-teki baru adalah mudah; hasil ditunjukkan pada Gambar 10. Namun, solusi ini tergantung pada pilihan-pilihan yang kami buat sebelum panggilan rekursif. Pilihan lain dapat menghasilkan solusi yang berbeda. Diagonal sederhana ini kondisi awal, ada dua kemungkinan solusi, yang terjadi menjadi matriks transposes satu sama lain. Karena solusinya tidak unik, grid pada Gambar 7 adalah bukan teka-teki yang valid.

Gambar 10.Solusi yang dihasilkan.Solusi ini tidak unik; yang transpos adalah solusi lain.

Keberadaan dan Keunikan

Sebagai matematikawan, kita berusaha untuk membuktikan bahwa solusi untuk masalah ada, dan bahwa itu adalah unik. Dengan Sudoku, baik keberadaan maupun keunikan dengan mudah dapat ditentukan dari awal petunjuk. Sebagai contoh, dengan teka-teki yang ditunjukkan pada Gambar 1, jika kita ingin menyisipkan “1”, “5,” atau “7” di (1,1) sel, baris, kolom, dan blok kondisi akan puas tetapi teka-teki yang dihasilkan tidak akan ada solusi. Akan sangat mengesalkan jika seperti teka-teki itu muncul di koran Anda. Backtracking menghasilkan konfigurasi yang mustahil. Mengakhiri program kami rekursi ketika bertemu dengan sebuah sel yang tidak memiliki calon. Teka-teki semacam itu tidak memiliki solusi. Keunikan adalah properti sukar dipahami. Kebanyakan permainan Sudoku deskripsi tidak menentukan bahwa harus ada hanya satu solusi. Lagi, itu akan membuat frustrasi untuk menemukan solusi yang berbeda dari yang diberikan. Beberapa teka-teki-program menghasilkan MATLAB Tengah jangan centang keunikan. Satu-satunya cara yang saya tahu untuk memeriksa secara mendalam keunikan adalah menghitung semua kemungkinan solusi.

Yang Sudoku Algoritma Penyelesaian Program MATLAB kami hanya melibatkan empat langkah: 1. Isi semua lajang. 2. Keluar jika sel tidak memiliki calon. 3. Mengisi nilai tentatif untuk sel kosong. 4. Panggil program rekursif. Kunci fungsi internal kandidat. Masing-masing sel kosong diawali dengan z = 1:9menggunakan nilai numerik yang terkait di baris, kolom, dan blok elemen nol z. Para nonzeros yang tetap adalah kandidat. Sebagai contoh, perhatikan (1,1) sel dalam Gambar 1. Kita mulai dengan z = 1 2 3 4 5 6 7 8 9 Nilai pada baris pertama perubahan z untuk z = 1 0 0 0 5 6 7 8 9 Kemudian perubahan kolom pertama z untuk z = 1 0 0 0 5 0 7 0 9 The (1,1) blok tidak membuat perubahan selanjutnya, sehingga calon sel ini C (1,1) = [1 5 7 9]

Sebuah Sulit Teka-teki Teka-teki yang ditunjukkan pada Gambar 1 adalah sebenarnya sangat sulit untuk menyelesaikan, baik dengan tangan atau dengan komputer. Angka 11 dan 12 adalah gambaran dari perhitungan.Pada awalnya, tidak ada lajang, maka langkah rekursif pertama terjadi segera. Kami mencoba “1” di (1,1) sel. Gambar 11 menunjukkan bagaimana kolom pertama kemudian diisi oleh langkah 22. Tapi kami masih jauh dari solusi. Setelah 3.114 langkah, rekursi menempatkan sebuah “5” di (1,1) sel, dan setelah 8.172 langkah, ia mencoba sebuah “7.”

Gambar 11.Situasi setelah hanya 22 langkah-langkah menuju solusi Gambar 1.Nilai berwarna cyan bersifat sementara pilihan yang dibuat oleh kemunduran, dan nilai-nilai berwarna hijau adalah lajang tersirat oleh orang-orang pilihan.The “1” adalah pilihan yang salah untuk (1,1) sel.Klik pada gambar untuk melihat tampilan yang diperbesar.

Gambar 12.

Setelah 14.781 langkah, kita tampaknya dekat dengan solusi, tetapi tidak mungkin untuk melanjutkan karena tidak ada calon untuk sel (1,9).The “7” adalah pilihan yang salah untuk (1,1) sel.Klik pada gambar untuk melihat tampilan yang diperbesar. Gambar 12 menunjukkan situasi setelah 14.781 langkah. Kita tampaknya dekat dengan solusi karena 73 dari 81 sel nilai-nilai yang telah ditetapkan. Tapi baris pertama dan kolom terakhir, diambil bersama-sama, mengandung semua angka dari 1 sampai 9, jadi tidak ada nilai-nilai yang berangkat ke (1,9) sel di sudut kanan atas. Daftar calon sel ini kosong, dan rekursi berakhir.Akhirnya, setelah 19.229 langkah, kami mencoba sebuah “9” dalam sel pertama. Ini “9” adalah ide yang baik karena kurang dari 200 langkah kemudian, setelah 19.422 langkah, program mencapai solusi yang ditunjukkan pada Gambar 2. Ini adalah langkah-langkah lebih banyak daripada kebanyakan puzzle membutuhkan.

Memecahkan Sudoku Menggunakan Rekursif Backtracking

 function X = sudoku(X)
% SUDOKU  Solve Sudoku using recursive backtracking.
%   sudoku(X), expects a 9-by-9 array X.
 % Fill in all “singletons”.
 % C is a cell array of candidate vectors for each cell.
 % s is the first cell, if any, with one candidate.
 % e is the first cell, if any, with no candidates.
 [C,s,e] = candidates(X);
 while ~isempty(s) && isempty(e)
    X(s) = C{s};
    [C,s,e] = candidates(X);
 end
 % Return for impossible puzzles.
 if ~isempty(e)
    return
 end
 % Recursive backtracking.
 if any(X(:) == 0)
    Y = X;
    z = find(X(:) == 0,1);    % The first unfilled cell.
    for r = [C{z}]            % Iterate over candidates.
       X = Y;
       X(z) = r;              % Insert a tentative value.
       X = sudoku(X);         % Recursive call.
       if all(X(:) > 0)       % Found a solution.
          return
       end
     end
   end
% ------------------------------
   function [C,s,e] = candidates(X)
      C = cell(9,9);
      tri = @(k) 3*ceil(k/3-1) + (1:3);
      for j = 1:9
         for i = 1:9
            if X(i,j)==0
               z = 1:9;
               z(nonzeros(X(i,:))) = 0;
               z(nonzeros(X(:,j))) = 0;
               z(nonzeros(X(tri(i),tri(j)))) = 0;
               C{i,j} = nonzeros(z)’;
            end
         end
      end
 L = cellfun(@length,C);   % Number of candidates.
 s = find(X==0 & L==1,1);
 e = find(X==0 & L==0,1);
 end % candidates
end % sudoku

The Origins of Sudoku Kebanyakan orang menganggap bahwa Sudoku berasal dari Jepang. Sebenarnya, ini adalah penemuan Amerika. Pertama kali muncul, dengan nama Number Place, di Dell Puzzle Magazine pada tahun 1979. Pada 1984, sebuah penerbit Jepang, Nikoli, mengambil teka-teki ke Jepang dan memberikan nama Sudoku, yang merupakan singkatan huruf kanji untuk “harus nomor satu, menikah.” The Times London mulai menerbitkan teka-teki pada tahun 2004, dan itu tidak lama sebelum menyebar ke Amerika Serikat dan di seluruh dunia.