Bài toán sudoku

khanhoatink4 · 18-04-2012, 11:16 AM

Như chúng ta đã biết trò chơi sudoku là một trò chơi khá nổi tiếng...Mình có 1 thắc mắc là hỏi có bao nhiêu cách điền vào các ô sudoku mà không lặp lại. Ban đầu các ô của sudoku đều trống.

**batigoal** · 18-04-2012, 06:02 PM

Trích:

Nguyên văn bởi khanhoatink4

Như chúng ta đã biết trò chơi sudoku là một trò chơi khá nổi tiếng...Mình có 1 thắc mắc là hỏi có bao nhiêu cách điền vào các ô sudoku mà không lặp lại. Ban đầu các ô của sudoku đều trống.

Bài toán này nếu giải theo toán học thuần túy thì khá trâu.Mình nghĩ đây là bài toán dành cho tin học thì đúng hơn.
PS: Để duyệt bài toán này chỉ cần sử dụng thuật toán quay lui. kết quả chắc vài giây là máy tính cho xong kết quả .

AnhIsGod · 18-04-2012, 06:10 PM

Đây là sudoku thể loại gì đây, 12x12 ak

khanhoatink4 · 19-04-2012, 04:28 PM

, mình nhầm 9x9, bài này kết quả khá lớn, máy chạy ko nỗi, theo mình nghỉ số kết quả sẻ là 9!x8!x7!x...x2!x1!, có cao nhân nào biết chỉ giúp mình cái,M gà về toán quá

cloner · 19-04-2012, 05:08 PM

Mình nghĩ đây là một bài toán rất hay trong tin học. Trước giờ mình mới chỉ thấy người ta dùng Backtracking để giải 1 trường hợp cho Sudoku, mình nghĩ dùng nó để đếm tất cả thì hơi bị khủng đó

AnhIsGod · 19-04-2012, 05:27 PM

Đây có bài viết về sudoku hay nè các bạn: [Only registered and activated users can see links. ]

franciscokison · 25-04-2012, 09:44 AM

Trích:

Nguyên văn bởi khanhoatink4

Như chúng ta đã biết trò chơi sudoku là một trò chơi khá nổi tiếng...Mình có 1 thắc mắc là hỏi có bao nhiêu cách điền vào các ô sudoku mà không lặp lại. Ban đầu các ô của sudoku đều trống.

Số cách điền này phụ thuộc vào thuật toán mà mình đưa ra, nếu dùng nguyên quay lui thì là $9!\cdot 8!\cdot...\cdot\1! $, nếu kết hợp thêm các hàm (các nhiều càng tốt- đỡ mất nhiều trường hợp quay lui) nhưng số phép toán so sánh tăng lên):
-Kiểm tra tính hiện diện: xem trong hàng, cột, vùng (3x3) đã có chưa
-Kiểm tra tính tồn tại: nếu trong hàng, cột, vùng chưa có
-...
Tức là mỗi phần tử (ô) gắn cho một mảng chứa các địa chỉ "đánh dấu" được điền, không được điền và chưa điền, khi ấy ở mỗi bước backtracking kiểm tra là ok.
Cuối cùng tính độ phức tạp của nó

18-04-2012, 11:16 AM	#1
khanhoatink4 +Thành Viên+ Tham gia ngày: Jan 2010 Bài gởi: 6 Thanks: 0 Thanked 0 Times in 0 Posts	Bài toán sudoku Như chúng ta đã biết trò chơi sudoku là một trò chơi khá nổi tiếng...Mình có 1 thắc mắc là hỏi có bao nhiêu cách điền vào các ô sudoku mà không lặp lại. Ban đầu các ô của sudoku đều trống.

19-04-2012, 05:08 PM	#5
cloner +Thành Viên+ Tham gia ngày: Mar 2011 Đến từ: Khu ổ chuột có cái view nhìn ra biển Bài gởi: 74 Thanks: 52 Thanked 37 Times in 24 Posts	Mình nghĩ đây là một bài toán rất hay trong tin học. Trước giờ mình mới chỉ thấy người ta dùng Backtracking để giải 1 trường hợp cho Sudoku, mình nghĩ dùng nó để đếm tất cả thì hơi bị khủng đó __________________ MỌI NGƯỜI ƠI VÀO GIẢI MẤY BÀI NÀY NÈ http://forum.mathscope.org/showthread.php?t=39613 http://forum.mathscope.org/showthread.php?t=39567 thay đổi nội dung bởi: cloner, 19-04-2012 lúc 05:13 PM

18-04-2012, 06:10 PM	#3
AnhIsGod +Thành Viên+ Tham gia ngày: Nov 2011 Đến từ: Vô cực Bài gởi: 267 Thanks: 358 Thanked 48 Times in 32 Posts	Đây là sudoku thể loại gì đây, 12x12 ak

19-04-2012, 04:28 PM	#4
khanhoatink4 +Thành Viên+ Tham gia ngày: Jan 2010 Bài gởi: 6 Thanks: 0 Thanked 0 Times in 0 Posts	, mình nhầm 9x9, bài này kết quả khá lớn, máy chạy ko nỗi, theo mình nghỉ số kết quả sẻ là 9!x8!x7!x...x2!x1!, có cao nhân nào biết chỉ giúp mình cái,M gà về toán quá

19-04-2012, 05:27 PM	#6
AnhIsGod +Thành Viên+ Tham gia ngày: Nov 2011 Đến từ: Vô cực Bài gởi: 267 Thanks: 358 Thanked 48 Times in 32 Posts	Đây có bài viết về sudoku hay nè các bạn: [Only registered and activated users can see links. ]