Thuật toán giải Sudoku nhanh nhất Python
Để hoàn thành dự án này, bạn cần làm quen với các khái niệm lập trình cơ bản, chẳng hạn như sử dụng mảng hai chiều, cấu trúc điều khiển (câu lệnh if, vòng lặp for, v.v.) và các hàm Show Bạn cũng cần biết Sudoku hoạt động như thế nào. Nếu bạn không quen, đây là một trang web tuyệt vời mà bạn có thể tham khảo – https. //www. học sudoku. com/sudoku-quy. html Dưới đây là một số chủ đề chúng tôi sẽ đề cập trong dự án hôm nay
Mục lục Ý chínhTrước khi tiếp tục, chúng ta hãy xem qua một số khái niệm chính cần thiết cho dự án hôm nay. Đầu tiên là khái niệm quay lui. Chúng ta sẽ sử dụng phương pháp quay lui để giải câu đố Sudoku sau này quay lui là gì?Quay lui là một kỹ thuật lập trình trong đó chúng tôi xây dựng một giải pháp từng bước một. Tại bất kỳ thời điểm nào, nếu chúng tôi nhận ra rằng không thể tìm ra giải pháp hợp lệ cho bước hiện tại, chúng tôi sẽ quay lại bước trước đó và thay đổi giải pháp cho bước đó Trong trường hợp Sudoku, quay lui yêu cầu chúng ta giải từng ô một. Tại bất kỳ thời điểm nào, nếu chúng tôi đến một ô mà chúng tôi không thể giải quyết, chúng tôi sẽ quay lại ô trước đó và thay đổi giải pháp cho ô đó Các bước chi tiết như sau
Nghe có vẻ khó hiểu? . Video được quay bằng bộ giải tại https. //trò chơi bài. io/sudoku/) Trong video quay ở trên, chúng ta bắt đầu bằng cách chèn số 2 vào ô cuối cùng của hàng 1 Tiếp theo, chúng ta chuyển sang hàng 2 và chèn số 1 vào ô đầu tiên Sau đó, chúng tôi chuyển sang ô tiếp theo và cố gắng chèn các số từ 1 đến 9. Thật không may, không có con số nào hoạt động. Khi điều đó xảy ra, chúng ta cần quay lại Chúng tôi quay trở lại ô trước đó và thử số hợp lệ tiếp theo. Vì ô trước có giá trị là 1 nên ta thử tiếp theo là số 2. Số này không thành công nhưng số 3 tiếp theo hoạt động Khi chúng tôi tìm thấy một số hoạt động, chúng tôi sẽ chuyển sang ô tiếp theo một lần nữa. Lần này, số 1 hoạt động cho ô đó Điều này tiếp tục lặp lại cho đến khi chúng tôi giải quyết toàn bộ bảng Sudoku Nghiên cứu kỹ video và đảm bảo bạn hiểu đầy đủ cách hoạt động của tính năng quay lui trước khi tiếp tục. Một trường hợp quay lui khác xảy ra ở 00. 38 Khi bạn đã quen với việc quay lui, hãy chuyển sang đệ quy. Chúng tôi sẽ sử dụng đệ quy và quay lui để giải câu đố Sudoku trong dự án của chúng tôi Đệ quy là gì?Đệ quy là một kỹ thuật mà một hàm gọi chính nó trong quá trình thực thi Điều này rất hữu ích khi giải pháp cho vấn đề lập trình phụ thuộc vào giải pháp cho các trường hợp nhỏ hơn của cùng một vấn đề Giả sử chúng ta có một bảng Sudoku với 10 ô trống Để quyết định xem một số có hợp lệ cho ô trống đầu tiên hay không, chúng ta có thể sử dụng đệ quy để thử giải 9 ô còn lại. Nếu tìm được nghiệm cho 9 ô còn lại thì biết số hiện tại là số chính xác Mặt khác, nếu chúng tôi không thể tìm ra giải pháp cho 9 ô còn lại, chúng tôi sẽ cập nhật ô hiện tại thành số có thể tiếp theo. Nói cách khác, dựa trên kết quả không thành công của 9 ô còn lại, chúng tôi quay lại ô hiện tại để cập nhật giá trị của nó Đây là ý chính về cách chúng ta sẽ sử dụng đệ quy để giải câu đố Sudoku trong dự án này Để biết thêm ví dụ về cách sử dụng đệ quy để giải quyết các vấn đề khác, bạn có thể xem các bài đăng này (tại đây và tại đây) Sẽ dễ hiểu hơn về đệ quy khi chúng ta bắt đầu làm việc với dự án của mình. Hãy làm điều đó ngay bây giờ Hãy làm nóTôi đã chia nhỏ dự án thành 5 bước Bước 1. Tạo và in bảngBước này yêu cầu chúng ta tạo một mảng có tên là myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]2. Mảng này lưu bảng Sudoku sau đây dưới dạng mảng hai chiều Mỗi phần tử trong myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]2 là một mảng lưu trữ một hàng trong bảng Sudoku, trong đó các ô trống được thay thế bằng số 0. Ví dụ, myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]4 lưu hàng đầu tiên. Nói cách khác, myBoard[0] = [0, 4, 0, 7, 0, 0, 1, 3, 0] Sau khi tạo bảng, bạn cần viết mã để in bảng. Hãy thử làm điều này cho mình Kết quả mong đợiBạn sẽ nhận được kết quả sau khi chạy mã của mình [0, 4, 0, 7, 0, 0, 1, 3, 0] [0, 0, 2, 0, 0, 0, 6, 0, 0] [0, 0, 0, 4, 2, 0, 0, 0, 0] [6, 0, 0, 0, 0, 2, 0, 0, 3] [2, 3, 1, 0, 7, 0, 0, 8, 0] [4, 0, 0, 3, 1, 0, 0, 0, 0] [0, 7, 0, 0, 0, 8, 0, 0, 0] [0, 0, 6, 0, 3, 0, 0, 0, 4] [8, 9, 0, 0, 5, 0, 0, 0, 6] Cần giúp đỡ?Đoạn mã sau tạo một mảng hai chiều có ba phần tử. Ba phần tử là các mảng myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]5, myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]6 và myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]7 myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]] Đoạn mã sau in mảng trên for line in myArray: print(line) Hãy thử sửa đổi mã ở trên để hoàn thành Bước Một giải pháp đề xuấtNhấp để xem giải pháp được đề xuất myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]0 Bước 2. Viết hàm kiểm tra xem một số có hợp lệ cho một ô nào đó khôngỞ Bước 2, chúng ta cần viết một hàm có tên là myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]8 có bốn tham số – myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]9, for line in myArray: print(line)0, for line in myArray: print(line)1 và for line in myArray: print(line)2 myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]9 đại diện cho bảng Sudoku trong khi for line in myArray: print(line)0 và for line in myArray: print(line)1 tương ứng với hàng và cột của một ô. Hàm myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]8 kiểm tra xem có thể đặt for line in myArray: print(line)2 vào ô được chỉ định bởi for line in myArray: print(line)0 và for line in myArray: print(line)1 hay không. Nếu có thể, hàm trả về myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]00. Khác, nó trả về myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]01 Chẳng hạn, đối với ô được đánh dấu trong bảng Sudoku ở Bước Một, myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]02 và myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]03 (hãy nhớ rằng for line in myArray: print(line)0 và myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]05 bắt đầu từ chỉ số 0). Nếu myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]06, hàm myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]8 sẽ trả về myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]01 vì myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]09 đã tồn tại trong hàng đó. Ngược lại, nếu myBoard[0] = [0, 4, 0, 7, 0, 0, 1, 3, 0]30, myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]8 sẽ trả về myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]00 Hãy thử mã hóa chức năng này cho mình. Hãy nhớ rằng bạn phải kiểm tra xem có tồn tại for line in myArray: print(line)2 trong hàng, cột và ô vuông 3×3 hiện tại không Kết quả mong đợiSau khi mã hóa chức năng, bạn có thể kiểm tra xem nó có hoạt động chính xác hay không bằng cách chạy các câu lệnh sau myBoard[0] = [0, 4, 0, 7, 0, 0, 1, 3, 0]3 Nếu bạn chạy mã ở trên, bạn sẽ nhận được đầu ra sau myBoard[0] = [0, 4, 0, 7, 0, 0, 1, 3, 0]8 Đối với câu lệnh đầu tiên, 6 đã tồn tại ở hàng 3. Đối với lần thứ hai, 6 tồn tại trong cột 6. Đối với cái thứ ba, 6 tồn tại ở ô 3 × 3 dưới cùng bên phải Do đó, đối với 3 câu lệnh đầu tiên, bạn nhận được kết quả là myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]01 Đối với câu lệnh cuối cùng, bạn nhận được myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]00 vì 6 là một số hợp lệ tại myBoard[0] = [0, 4, 0, 7, 0, 0, 1, 3, 0]36, myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]03 Cần giúp đỡ?Tương đối dễ dàng để kiểm tra xem for line in myArray: print(line)2 có tồn tại trong một hàng và cột nhất định hay không. Khó kiểm tra xem nó có tồn tại trong hình vuông 3×3 hiện tại không Một cách để làm điều đó là tìm ra vị trí của góc trên cùng bên trái của hình vuông. Chẳng hạn, đối với ô được đánh dấu trong ví dụ của chúng tôi, góc trên cùng bên trái của hình vuông nằm ở hàng 6, cột 3 Để lấy hàng của góc trên cùng bên trái, bạn có thể sử dụng công thức myBoard[0] = [0, 4, 0, 7, 0, 0, 1, 3, 0]39. myBoard[0] = [0, 4, 0, 7, 0, 0, 1, 3, 0]80 cho chúng ta phần còn lại khi for line in myArray: print(line)0 chia cho 3. Điều này cho chúng ta biết ô hiện tại cách hàng của góc trên cùng bên trái bao xa Trong ví dụ của chúng tôi, myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]02 cho ô được đánh dấu. myBoard[0] = [0, 4, 0, 7, 0, 0, 1, 3, 0]80 cung cấp cho chúng tôi myBoard[0] = [0, 4, 0, 7, 0, 0, 1, 3, 0]84, cho biết ô được tô sáng nằm dưới góc trên cùng bên trái một hàng myBoard[0] = [0, 4, 0, 7, 0, 0, 1, 3, 0]39 cho chúng ta myArray = [[1, 2, 3], [2, 7, 1], [1, 9, 7]]09, là hàng của góc trên cùng bên trái của hình vuông 3×3 đó Để lấy cột của góc trên cùng bên trái, bạn có thể sử dụng công thức myBoard[0] = [0, 4, 0, 7, 0, 0, 1, 3, 0]87 Điều này mang lại cho chúng tôi 3 cho ô được đánh dấu Từ góc trên cùng bên trái, bạn có thể sử dụng vòng lặp để kiểm tra xem có tồn tại for line in myArray: print(line)2 ở hàng 6, 7 và 8 cho các cột 3, 4, 5 không Dựa trên mô tả ở trên, hãy thử sửa đổi giải pháp cho Bước Bốn để giải quyết toàn bộ bảng Sudoku |