Chiến lược chơi Sudoku

Có nhiều cách giải Sudoku. Ta sẽ dùng cách sau đây, đó là tìm kiếm đệ quy quay lui truyền thống bằng cách hướng đối tượng. Gọi mỗi ô vuông trong bảng Sudoku là một "spot". Ta muốn tìm kiếm lời giải bằng cách đệ quy quay lui, gán giá trị cho các ô để tìm một tổ hợp giá trị thỏa mãn.

Khi gán một giá trị cho một ô (spot), cần đảm bảo giá trị đó khi đó không xung đột với hàng, cột, hoặc hình vuông chứa ô đó. Ta cần kiểm tra ngay tính hợp lệ của các giá trị gán cho một ô, thay vì gán đại các giá trị bất kì từ 1 đến 9 rồi ở các bước đệ quy sau mới phát hiện ra sự bất hợp lệ. Giả sử rằng toàn bộ bảng vuông ban đầu hợp lệ, từ đó ta cũng chỉ gán các giá trị hợp lệ cho các ô.

Có 81 ô trong bảng Sudoku. Bạn có thể gán trị cho các ô theo thứ tự tùy ý. Tuy nhiên, trong lời giải của chúng ta, đầu tiên hãy sắp thứ tự các ô theo chiều tăng dần của kích thước của tập các giá trị có thể gán cho nó. Tìm kiếm đệ quy theo thứ tự đó, gán cho các ô có ít lựa chọn nhất trước. Trong quá trình tìm kiếm, đừng sắp xếp lại thứ tự các ô. Sắp xếp một lần và giữ nguyên thứ tự là đủ tốt. Việc sắp thứ tự chỉ là gần tối ưu, nhưng nó dễ làm và hiệu quả.

Ta đặt một ngưỡng tối đa là 100. Nếu quá trình tìm kiếm đã phát hiện được 100 đáp số hoặc nhiều hơn, nó có thể dừng lại và trả về số lượng đáp số đã tìm được.

Thiết kế hướng đối tượng

Đối với bài tập này, code khởi đầu đã có một số hàm và dữ liệu, phần còn lại của thiết kế là tùy ở bạn. Mục tiêu của bạn là thiết kế các lớp và API sao cho phương thức solve() (xem dưới đây) là một thể hiện trong sáng của chiến lược mô tả ở trên, và hàm main() và chương trình GUI cũng được viết một cách trong sáng. Ta sẽ sử dụng cách tiếp cận hướng đối tượng đối với thuật toán tìm kiếm: coi mỗi ô (spot) là một đối tượng. Tạo một lớp Sudoku đóng gói một bài Sudoku và cho nó một lớp Spot là inner class đại diện cho một ô trong bài.

Tăng hiệu quả chương trình theo tỷ lệ hằng số (làm cho chương trình chạy nhanh gấp C lần) không phải là mối quan tâm lớn ở đây. Ta cần chú ý đến tính đúng đắn, tính trong sáng của code, và một chiến lược thông minh.

Hãy tập trung vào thiết kế hướng đối tượng cho lớp Spot -- đẩy sự phức tạp vào bên trong Spot, để client của Spot được đơn giản. Chẳng hạn, Spot có cổng truy nhập riêng tới lưới vuông (nhớ rằng nó là inner class của Sudoku). Xét hai ví dụ sau của client code:

// Bad 
grid[spot.getRow()][spot.getCol()] = 6; 
 
// Good 
spot.set(6);

Bạn có thể thiết kế code tùy ý, miễn thỏa mãn các yêu cầu sau...

Sudoku(int[][] grid) -- hàm tạo lấy tham số là lưới vuông ban đầu, ta giả thiết rằng client sẽ truyền vào một lưới hợp lệ, không cần kiểm tra. Các ô trống được đại diện bằng giá trị 0 trong lưới. Bạn có thể giả thiết rằng lưới có kích thước 9x9. Bạn không cần phải dùng cấu trúc int[][] để lưu trữ bên trong lớp Sudoku, nó chỉ là định dạng cho input/output.

Sudoku(String text) -- lấy tham số là bài Sudoku ở dạng text -- 81 số. (File cho sẵn đã cung cấp mã để dịch tham số dạng này).

String toString() -- cài đè toString() để trả về một String gồm 9 dòng thể hiện 9 dòng của lưới vuông, trong đó mỗi số có một kí tự space đứng trước (dùng lớp StringBuilder thay cho StringBuffer). Ví dụ, dưới đây là kết quả toString của bài "medium 5 3"...

int solve() -- giải Sudoku theo chiến lược mô tả ở trên. Trả về số đáp số và đặt trạng thái đối tượng Sudoku sẵn sàng cho các hàm getSolutionText() và getElapsed() (bên dưới). Lưới sudoku ban đầu không bị thay đổi (nghĩa là hàm toString() vẫn trả về lưới ban đầu). Trong các bài sudoku cho sẵn, mỗi bài có 01 đáp số.

String getSolutionText() -- sau mỗi lần chạy solve(), nếu có một hoặc nhiều đáp số, hàm này trả về dạng text của đáp số đầu tiên tìm được (nếu không có đáp số thì trả về xâu rỗng). Tùy theo cách bạn cài đặt solve() mà đáp số đầu tiên sẽ khác nhau.

long getElapsed() -- sau mỗi lần chạy solve(), hàm này trả về thời gian mà solve() đã chạy, tính bằng milli giây. Xem hàm System.currentTimeMillis(). Hàm này sẽ giúp thấy hiệu ứng thời gian của các thay đổi trong code của bạn.

Bạn có thể dùng Integer hoặc int hoặc gì đó tùy ý để theo dõi trạng thái của lưới. Có thể tận dụng Set<Integer>/HashSet<Integer> và các hàm có sẵn như contains(), addAll(), removeAll() để phục vụ mục đích này.

Nộp bài

File cho sẵn: Sudoku.java