Giải sudoku bằng excel

     
Msinh sống đầu

Mình lấy xúc cảm từ site này, bàn về thuật toán thù giải Sudoku. Việc những cao thủ cần sử dụng thiết kế nhằm giải Sudoku bên trên báo đem chi phí vẫn tất cả từ rất lâu. Có lẽ thế nên buộc phải mục Sudoku của báo Thanh niên không hề trao thưởng trọn, cơ mà chỉ “vinch danh” bạn giải đúng. Thuật toán thù giải không phức tạp, tuy vậy giải pháp viết code lại tác động không ít đến vận tốc giải. Bài này nhằm mục tiêu ghi lại quá trình tìm mẫm, thuộc hồ hết Tóm lại đúc rút được từ rất nhiều đoạn code viết dại, đông đảo khoảng thời gian ngắn khù khờ cơ mà không viết có thể chả lúc nào biết. Have funnn.

Bạn đang xem: Giải sudoku bằng excel

Sudoku là gì?
*

Sudoku là một trong những trò giải đố với quy luật pháp đơn giản dễ dàng (mà lại người nào cũng biết):

Một tập hòa hợp 9×9 = 81 ô vuông với các ô hoàn toàn có thể được viết số từ là một đến 9Việc của tín đồ giải là điền các số từ 1 mang đến 9 vào những ô còn thiếu sao choKhông sản phẩm nào bao gồm chữ số lặp lạiKhông cột nào bao gồm chữ số lặp lạiVà ko block 3×3 làm sao bao gồm chữ số lặp lại

Do vậy, cách giải dễ dàng và đơn giản tuyệt nhất, cũng chính là cơ bản thuật toán giải Sudoku là force brute, giỏi backtracking, test trâu bò các số cho đến lúc ra được công dụng thì thôi. Đương nhiên, những người đùa bao gồm kinh nghiệm tay nghề sẽ có mánh khóe để gia công “cuộc sống dễ ợt hơn”. Tuy nhiên nặng nề để dạy mánh cho một cái máy, với mình cũng chưa bao giờ mánh mọe làm sao, buộc phải bản thân đùa trâu trườn xả thân tường.

Cuối thuộc thì, để tìm kiếm được phía đi đúng, nên một câu hỏi đúng. Và câu hỏi đúng trong những trường thích hợp này là:

Làm sao nhằm giải Sudoku nhanh khô hơn?

hay

Làm thế nào nhằm tinh giảm số lần thử trước nhằm tìm được đáp án?

Sudoku gồm bao nhiêu phương pháp thử?

Nếu tính vo thì có khoảng 1.5*10^31 phương pháp điền một ma trận Sudoku. Tuy nhiên, hiệu quả này không đúng mực lắm. Năm 2005, nhì bác bỏ nhiều não Bertram Felgenhauer và Frazer Jarvis sẽ cần sử dụng máy tính xách tay nhằm demo trâu trườn với hiệu quả nhận được là:

6,670,903,752,021,072,936,960 phương án Sudoku

Hay 6.67 ngàn tỷ tỷ phương pháp Sudoku

Với vận tốc giải bằng VBA trên vật dụng của chính mình là khoảng 100,000 phnghiền thử/giây, thì nên cần khoảng:

2.1 tỷ năm, để thử không còn hầu hết thứ

Tốc độ vẫn nkhô giòn hơn nếu sử dụng ngôn từ low-màn chơi nhỏng C++. Đương nhiên, điều đó ko Tức là VBA không làm được: VBA giải được tất cả các bài Sudoku cường độ cạnh tranh Evil nếu viết kheo khéo. Nếu viết không khéo, VBA chỉ hoàn toàn có thể giải được những câu đố gồm độ khó khăn mức độ vừa phải.

Và mình đã demo cả nhì kiểu: viết lẩn thẩn với viết ít ngây ngô.

Viết ngu: bài xích dễ dàng giải trong vòng 5s, bài nặng nề giải trong một vài giờ.Viết ít ngu: bài xích dễ giải trong không đến 1s, bài bác thú vật giải trong khoảng 5 phút ít.

Vậy điều gì tạo nên sự khác hoàn toàn quá rộng về tính năng tính toán?

Câu trả lời là: bí quyết nhưng mà VBA, giỏi đầy đủ ngôn ngữ không giống, gọi các lịch trình bé (subroutine) vào tính toán.

Thu gọn tập hợp những cực hiếm phải thử

Đây là bước đầu tiên cùng quan trọng đặc biệt duy nhất vào quy trình giải. Đôi cùng với mỗi ô, không cần thiết đề xuất test tất cả các số từ một mang lại 9, chỉ cần thử các số đáp ứng nhu cầu lao lý ko tái diễn đối với loại, cột, và bloông chồng.

lấy ví dụ như minh họa:


*

Các ô màu sắc xám là những ô đựng câu đố, những ô màu trắng là các ô chứa những cực hiếm thử. ví dụ như, ô đầu tiên rất có thể đựng một trong số giá trị 2, 5, 8, 9 mà lại bảo vệ đúng hình thức đối với cái 1, cột 1, cùng blochồng trước tiên.

Đối cùng với tập cực hiếm test này, bạn cũng có thể tính được số phnghiền demo buổi tối nhiều đề xuất thực hiện:

4*3*2*3*1*3*3*..*2*2*4 = 8,217,078,173,112,730,000 phnghiền thử

Hay 8.2 tỷ tỷ phnghiền thử. Thực tế thì cùng với câu đố dễ hoàn toàn có thể kiếm tìm gia được giải đáp trong vài ba ngàn lần demo.

Thuật toán

Tổng quan lại quá trình buộc phải thực hiện:

Cách 1: Kiểm tra coi câu đố tất cả đầy đủ tối thiểu 17 quý giá lúc đầu. Để một đề bài Sudoku có một phương án giải độc nhất, cần phải gồm ít nhất 17 ô được điền sẵn.

Bước 2: Điền vào các ô trống các giá trị thử, như sinh hoạt bên trên.

Xem thêm: Trọn Bộ 32 Tập Đại Thánh Vương 32 Tập, Đại Thánh Vương

Bước 3: Bắt đầu giải, demo theo lắp thêm trường đoản cú tự trái quý phái phải, từ trên xuống dưới.

Thử quý giá thứ nhất của ô đầu tiênNếu quý giá này phù hợp, nhảy cho tới test ô tiếp sau.Nếu quý giá bất hợp lý và phải chăng, nhảy tới quý hiếm tiếp theo sau thuộc ô.Nếu thử cho giá trị ở đầu cuối của ô cơ mà vẫn không hợp lý và phải chăng, xóa cực hiếm test trên ô đó, nhảy đầm tới cực hiếm tiếp theo làm việc ô trước đó.

Bước 4: Dừng khi tìm được giá trị phù hợp trên ô cuối cùng.

Lần demo đồ vật nhất

Đây là file chứa đoạn code được viết theo style đơn giản, dễ nhìn, dễ đọc. Độc giả rất có thể down về nhằm nghịch.

Hướng dẫn:

New Puzzle: xóa câu đố với giải thuật bây chừ,k hi mong muốn nhập câu đố bắt đầu.Chechồng Puzzle: đánh giá coi câu đố rất có thể giải được ko, sau thời điểm nhập một câu đố.Fill Values: điền cách thực hiện demo.Clear Solution: xóa câu trả lời hiện nay.Solve: bắt đầu giải.

Xem thêm: Easyanticheat Là Gì ? #1: Easy Anti Cheat Là Gì

Visualization: “On” nếu như muốn quan tiền tiếp giáp thuật toán thù quản lý và vận hành. Lưu ý: vẫn có tác dụng lừ đừ tốc độ giải.

Chuyên mục: Tin Tức