Độ phức tạp của thuật toán (Big-O) của trình giải Sudoku

Question

Tôi đang tìm "cách bạn tìm thấy" vì tôi không biết cách tiếp cận tìm sự phức tạp về thuật toán của chương trình.

Tôi đã viết một giải sudoku bằng java, mà không hiệu quả trong tâm trí (tôi muốn cố gắng làm cho nó hoạt động một cách đệ quy, mà tôi đã thành công với!)

Một số nền:

chiến lược của tôi sử dụng thụt lùi để xác định , đối với một câu đố Sudoku đã cho, câu đố chỉ có một giải pháp duy nhất hay không. Vì vậy, tôi về cơ bản đọc trong một câu đố nhất định, và giải quyết nó. Khi tôi tìm thấy một giải pháp, tôi không nhất thiết phải thực hiện, cần phải tiếp tục khám phá để có thêm giải pháp. Cuối cùng, một trong ba kết quả có thể xảy ra: câu đố không thể giải quyết được, câu đố có một giải pháp duy nhất, hoặc câu đố có nhiều giải pháp.

Chương trình của tôi đọc trong tọa độ câu đố từ tệp có một dòng cho mỗi chữ số nhất định, bao gồm hàng, cột và chữ số. Theo quy ước của riêng tôi, hình vuông trên bên trái của 7 được viết như 007.

Thực hiện:

tôi tải các giá trị trong, từ tập tin, và lưu trữ chúng trong một mảng 2-D tôi đi xuống mảng cho đến khi tôi tìm thấy một Blank (giá trị không thực hiện), và thiết lập nó để 1. Và kiểm tra cho bất kỳ xung đột (cho dù giá trị tôi nhập là hợp lệ hay không). Nếu có, tôi chuyển sang giá trị tiếp theo. Nếu không, tôi tăng giá trị lên 1, cho đến khi tôi tìm thấy một chữ số hoạt động hoặc nếu không có chữ số nào hoạt động (1 đến 9), tôi quay lại 1 bước về giá trị cuối cùng mà tôi đã điều chỉnh và tăng giá trị đó đệ quy). Tôi đã giải quyết xong khi tất cả 81 phần tử đã được lấp đầy, không có xung đột. Nếu tìm thấy bất kỳ giải pháp nào, tôi sẽ in chúng vào thiết bị đầu cuối. Nếu không, nếu tôi cố gắng "quay lại một bước" trên phần tử FIRST mà ban đầu tôi đã sửa đổi, điều đó có nghĩa là không có giải pháp nào.

Mức độ phức tạp của thuật toán chương trình của tôi như thế nào? Tôi nghĩ rằng nó có thể là tuyến tính [O (n)], nhưng tôi truy cập vào các mảng nhiều lần, vì vậy tôi không chắc chắn :(

Any help is appreciated

Answer 1

O (n ^m), nơi n là số khả năng cho mỗi vuông (ví dụ, 9 cổ điển Sudoku) và m là số lượng chỗ có trống.

Điều này có thể được nhìn thấy bằng cách làm việc ngược từ duy nhất một Nếu chỉ có một ô trống, thì bạn có n các khả năng mà bạn phải làm việc trong trường hợp xấu nhất. Nếu có hai khoảng trắng, thì bạn phải làm việc qua các ô trống n cho ô trống đầu tiên và n khả năng cho ô trống thứ hai cho từng khả năng cho ô trống đầu tiên. Nếu có ba khoảng trống, thì bạn phải làm việc qua các ô n cho ô trống đầu tiên. Mỗi khả năng đó sẽ mang lại một câu đố với hai khoảng trống có n^2 khả năng.

Thuật toán này thực hiện tìm kiếm theo chiều sâu thông qua các giải pháp khả thi. Mỗi cấp độ của biểu đồ thể hiện các lựa chọn cho một hình vuông. Độ sâu của biểu đồ là số ô vuông cần được lấp đầy.Với một yếu tố phân nhánh của n và độ sâu m, việc tìm kiếm một giải pháp trong đồ thị có một buổi biểu diễn trường hợp xấu nhất của O (n ^m).

Answer 2

Trong nhiều Sudokus, sẽ có một vài con số có thể được đặt trực tiếp với một chút suy nghĩ. Bằng cách đặt một số trong ô trống đầu tiên, bạn từ bỏ rất nhiều cơ hội để giảm khả năng. Nếu mười ô trống đầu tiên có nhiều khả năng, bạn sẽ tăng trưởng theo cấp số mũ. Tôi muốn đặt câu hỏi:

Trường hợp trong dòng đầu tiên có thể số 1 đi đâu?

Trường hợp trong dòng đầu tiên có thể số 2 đi đâu?

...

Trường hợp ở dòng cuối cùng số 9 có thể đi đâu?

Tương tự nhưng có chín cột?

Tương tự nhưng với chín hộp?

Số nào có thể đi vào ô đầu tiên?

Số nào có thể đi vào ô 81?

Đó là 324 câu hỏi. Nếu bất kỳ câu hỏi nào có chính xác một câu trả lời, bạn chọn câu trả lời đó. Nếu bất kỳ câu hỏi không có câu trả lời nào cả, bạn quay lại. Nếu mỗi câu hỏi có hai hoặc nhiều câu trả lời, bạn chọn một câu hỏi với số câu trả lời tối thiểu.

Bạn có thể nhận được tăng trưởng theo cấp số nhân, nhưng chỉ cho những sự cố thực sự khó khăn.