Cách Giải Sudoku Bằng Excel / Top 17 Xem Nhiều Nhất & Mới Nhất 9/2023 # Top Trend

Luật chơi Sudoku

Trước khi tiến hành giải các ô Sudoku người chơi cần phải nắm rõ luật chơi cơ bản. Từ đó mới giải các ô câu đố hiệu quả và chính xác hơn.

– Sudoku trò chơi rất hay giúp con người rèn luyện trí tuệ, logic.

– Sudoku có nhiều phiên bản nhưng chuẩn nhất là hình vuông 9 ô lớn, chia 3×3, mỗi ô lớn gồm có 9 ô nhỏ và sẽ có 81 ô.

Luật chơi:

Người chơi phải điền tất cả các con số còn thiếu còn lại trong số 81 ô, cấp độ cơ bản càng nhiều số điền sẵn, cấp độ khó hơn hệ thống điền trước 8 – 10 ô. Điền số từ 1 đến 9 cho cả 9 ô lớn cần đáp ứng:

Số duy nhất không bị trùng trong 9 ô nhỏ với tỉ lệ là 3×3.

Số duy nhất trong 9 số dãy hàng ngang, hàng dọc.

Biến thể Sudoku

Sudoku có nhiều biến thể, mỗi biến thể lại có kích thước và số lượng ô khác nhau. Phiên bản chuẩn kích thước là 9×9 (ô nhỏ), trong đó chia thành các vùng 3×3 (9 vùng). Các biến thể Sudoku qua mỗi quốc gia lại thay đổi ít nhiều nhằm phù hợp với cách chơi của từng vùng. Một số biến thể như sau:

Kích thước 4×4 ô, với 2×2 vùng.

Kích thước 6×6 ô,với 2×3 vùng.

Kích thước 5×5 ô, chia vùng theo Pentomino.

Kích thước 7×7 ô, chia vùng theo Heptomino.

Biến thể về kích thước:

Kích thước 16×16 ô (Monster SuDoku).

Kích thước 12×12 ô, chia làm 4×3 vùng (Dodeka Sudoku).

Kích thước 25×25 ô (Giant Sudoku).

Kích thước 100×100 ô.

Cách giải Sudoku nhanh cho người mới bắt đầu 1. Nối các ô trùng lặp

Trước tiên bạn cần phải nối các ô trùng lặp đây là cách tìm kiếm các con số dễ nhất, chúng ta tìm số 5 ở vị trí dưới, khi dòng số 5 từ các ô theo hàng sẽ loại trừ được số 5 ở dưới đó đang nằm ở đâu. 2 vị trí khoanh tròn vẫn còn phải đối chiếu để tìm số 5 trong những ô đang là ẩn số.

Nối các ở trùng lập là phương pháp cơ bản khi chơi Sudoku.

2. Tìm số theo bộ 3 hàng dọc, hàng ngang

Theo dõi hình ảnh bên dưới là phép loại trừ ở hàng trên và dưới khi tham chiếu vào ô giữa, quy tắc 1 ô sẽ tồn tại trong sudoku là duy nhất ô 3×3 đó và không cùng hàng với bất cứ ô 3×3 nào khác. Đây cũng là cách tìm ẩn số ở những mức độ cơ bản.

3. Phán đoán dựa trên hàng và cột

Áp dụng trong sudoku 3×3 với con số bất kì sau đó so sánh hàng và cột. Sudoku 3×3 dưới hình ảnh có thể xác định được vị trí khoanh tròn màu đỏ là số 7.

4. Loại trừ nhằm loại số

Áp dụng quy tắc loại trừ số hiện đang có, số chưa có và số không thể xuất hiện tại 1 vị trí nhằm điền số vào ô còn lại, đây là một cách rất hay mà bạn nên áp dụng.

5. Phán đoán con số đơn độc

Trong ô Sudoku 3×3 beenduoiws hãy phán đoán 1 con số chữ có mặt, so sánh cùng với các hàng, cột trên Sudoku lớn hơn.

Ví dụ: Sudoku phía trên cùng bên trái của ô Sudoku 9×9, người chơi có thể phán đoán vị trí số 3, chắc chắc ở vị trí đang được khoanh tròn trên hình.

6. Hãy nháp các con số

Trong vùng có 3×3 như hình bên dưới, có con số 1 có khả năng nằm 2 vị trí trở lên nhanh tay ghi chú bé sang bên cạnh để tìm ra đáp án nhanh hơn.

Chẳng hạn số 1 đều có thể nằm ở 3 vị trí khoanh tròn màu đỏ, cần nháp ra giấy rồi sau đó tính toán thêm cho chắc chắn rồi mới điền vào.

7. Những lưu ý khi chơi Sudoku

Để chơi Sudoku trò chơi trí tuệ này tốt hơn bạn nên chú ý một số điểm sau:

– Nên tìm các ô đơn giản bằng cách loại trừ 1 số.

– Tìm các ô xác suất rơi vào 2 số , viết hai số đó góc phải ô (gọi là ô hai số).

– Tương tác giữa khối và cột / khối và hàng: kiểm tra lại một khối xác định rằng một số nào đó phải nằm trong một hàng hoặc một cột cụ thể. Bạn rút con số đó ra khỏi danh sách ứng viên cho các ô khác trong cùng hàng, cột, nhưng ngoài miền 3×3.

Sudoku là trò chơi trí óc, sáng tạo, khả năng logic của con người. Đây là trò chơi có nhiều biến thể rất vui và giải trí cực tốt. Chúng tôi đã giới thiệu về những mẹo giải Sudoku thật nhanh và đơn giản sẽ giúp bạn giải quyết những ẩn số cơ bản. Còn rất nhiều những ẩn số Sudoku nằm ở mức độ cao hơn khiến người chơi phải đau đầu, nhức óc mỗi khi giải quyết.

Bất cứ trò chơi nào cũng có những quy tắc, mẹo chơi riêng và ngay cả Sudoku cũng vậy. Bạn cần phải biết mẹo chơi Sudoku và các quy tắc chơi Sudoku để có thể giải bất cứ loại sudoku nào.

Sudoku là tựa game giải đố tuân theo các logic nhất định và càng ở mức độ cao người chơi sẽ cần nhiều thời gian, sự kiên nhẫn cũng như khả năng tính toán của người chơi để có thể giải Sudoku được. Nhưng cho dù là cấp độ dễ, khó hay giải Sudoku cập độ siêu khó đi chăng nữa cũng đều có những cách chơi Sudoku nhất định, và các cách chơi Sudoku đều tuân theo một logic riêng của trò chơi giúp người chơi giải.

Và đối với những người mới chơi thì việc nắm rõ các mẹo chơi Sudoku chính là chía khóa để có thể giải nhanh Sudoku ở cấp độ đơn giản hay trung bình, dựa theo logic đó có thể vận dụng vào các bài khó hơn. Nhưng tất nhiên ở cấp độ khó chúng ta sẽ phải mất nhiều thời gian hơn cũng như sự tính toán để đạt được kết quả như mong muốn.

Sudoku và luật chơi bạn cần biết ?

– Sudoku là một trong những trò chơi rất phổ biến tại Nhật Bản, nó được đánh giá là trò chơi có khả năng rèn luyện trí tuệ cũng như tư duy logic tốt nhất. Sudoku trong tiếng Nhật bản có nghĩa là độc nhất và nó cũng là ý nghĩa lớn nhất của trò chơi.

– Sudoku có rất nhiều dạng khác nhau và nhiều phiên bản tùy từng vùng nhưng loại chuẩn nhất là hình vuông với 9 ô lớn tỉ lệ chia 3×3, trong mỗi ô lớn đó lại có 9 ô nhỏ và tổng cộng chúng ta có 81 ô tất cả.

– Luật chơi Sudoku rất đơn giản khi người chơi phải đáp ứng điền đầy đủ các con số con thiếu vào trong 81 ô đó, thông thường ở cấp độ khó hệ thống chỉ điền trước cho bạn tầm 10 ô mà thôi. Việc bạn cần làm là điền các con số từ 1 đến 9 cho cả 9 ô lớn và thỏa mãn 2 điều kiện sau.

* Thứ nhất số bạn điền phải là số duy nhất không bị trùng trong 9 ô nhỏ tỉ lệ 3×3.

* Thứ hai số bạn điền phải là duy nhất trong 9 số dãy hàng ngang, hàng dọc mà nó nằm lên trên.

Mẹo chơi Sudoku cho người mới 1. Dóng số theo hàng ngang và hàng dọc để loại trừ

Dóng số theo hàng ngang và hàng dọc là cách đơn giản nhất để bạn có thể tìm được một con số thích hợp cho vị trí cần điền, hãy tìm các con số nào xuất hiện trên màn hình nhiều nhất, và dóng nó theo hàng ngang, dọc tới ô bạn cần tìm, vì ở mỗi ô 3×3 ví trí là độc nhất nên vị trí nào không nằm cùng một đường ngang và dọc thì đó là vị trí cần tìm.

Tuy nhiên mẹo chơi Sudoku này chỉ áp dụng được với mức độ đơn giản, trung bình mà thôi. Ở mức độ khó ngay từ đầu bạn sẽ không thể áp dụng theo cách này được.

2. Tìm các ô trùng lặp để loại trừ cho ô cần tìm

Bước đầu tiên để tìm kiếm các con số dễ dàng nhất là tìm ô trùng lặp để có thể tìm ra vị trí thích hợp nhất để điền các ô số. Như trong hình trên bạn sẽ thấy chúng ta tập trung tìm số 5 ở vị trí dưới, khi dòng số 5 từ các ô theo hàng sẽ loại trừ được số 5 ở dưới đó đang nằm ở đâu. Nhưng tất nhiên ở mẹo chơi Sudoku này bạn sẽ thấy vị trí số 5 vẫn còn 1 trong 2 ô cần điền, tuy vậy chúng ta có thể sử dụng nháp điền thử để cho ra kết quả chính xác hơn nữa.

3. Điền thử số và so sánh với các hàng khác

Trong Sudoku thì mỗi số phải là độc nhất như quy tắc đã nói, ở trong hình trên bạn sẽ thấy chúng ta cần điền số 2, 5 ,7 và 9. Ở đây nhận thấy dễ dàng số 7 khi dóng cả hàng trên và dưới sẽ cho kết quả ô ở giữa là số 7 và còn lại 2, 5 và 9. Tiếp tục so sánh cách hàng chúng ta sẽ thấy ở trên chỉ có thể điền 2 hoặc 5, vì vậy cạnh số 7 tiếp đó phải là 9. Để có thể tìm nốt 2 và 5 chúng ta phải vận dụng các hàng dọc và ngang để giải các hàng đó trước khi có cấu trả lời chính xác. Lúc này bạn có thể điền thử số và giải tiếp tục nếu như không có thêm một gợi ý nào cho bạn nữa cả, nhưng xin lưu ý việc điền số thử đôi khi cũng dẫn đến tình trạng sai hàng loạt.

4. Sử dụng quy tắc loại trừ để loại số không thích hợp trông ô

Hày thử sử dụng nháp và áp dụng quy tắc loại trừ số đã có, chưa có và số không thể có tại ví trí đó để điền số vào các ô còn lại, việc sử dụng nháp cũng là giải pháp hay trong tình huống này và như hình trên chúng ta có thể thấy việc dóng hàng và loại trừ ít nhất vẫn phải khiến chúng ta phân vân ở 2 ô cho mỗi con số, vì thế hảy thử nháp và điền các con số còn lại xem sao.

https://thuthuat.taimienphi.vn/meo-choi-sudoku-nhanh-quy-tac-giai-26405n.aspx Nếu như bạn cảm thấy quá đau đầu để giải Sudoku thì hãy tạm nghưng trong ít phú để tham gia vào một trò chơi giải trí khác giúp giải tỏa căng thẳng tốt hơn. Chẳng hạn như cách chơi Megaman trên máy tính mà chúng tôi đề cập đến sau đây, khi bạn chơi Megaman trên máy tính, bạn sẽ cảm nhận được một tựa game giải trí đơn giản, thú vị và cũng rất đã tay.

Sudoku là tựa game trí tuệ hàng đầu hiện nay, với cách chơi sắp xếp các chữ số đơn giản nhưng lại không hề dễ dàng để mở tất cả, bài toán cách chơi Sudoku luôn luôn là thứ khiến người chơi đau đầu ở cấp độ khó và siêu khó.

Không có bài toàn nào là không thể giải, ngay cả cách chơi Sudoku cũng vậy thôi, cho dù bạn đang ở độ khó nào đi chăng nữa đều có những quy luật nhất định trong một trò chơi. Và nếu bạn khám phá ra được quy luật đó thì cách chơi Sudoku sẽ dễ dàng hơn rất nhiều. Để có cách chơi Sudoku logic cũng như khoa học nhất điều đầu tiên bạn cần có chính là sự kiên nhẫn khi chơi bộ môn này.

Ngoài ra đây cũng là bộ môn rất được khuyến khích vì cách chơi Sudoku giúp chúng ta rèn luyện trí nào rất tốt. Với những ai đam mê sáng tạo, thử thách cái mới thì Sudoku hay cách chơi Minecraft là sự lựa chọn phù hợp nhất, đặc biệt khi bạn kết hợp sự thử thách với cách chơi Sudoku cấp độ khó và sau đó giải trí bằng sự sáng tạo đến từ cách chơi minecraft thật tuyệt vời. Tuy vậy mục đích của bài viết hôm nay chúng ta sẽ không phải là giới thiệu về tựa game Sudoku này, với những ai đang có ý định chơi, hoặc đang chơi sudoku cho dù cấp độ dễ, khó hay siêu khó cần phải biết các mẹo, cách quy luật sau để có thể giải Sudoku một cách dễ dàng nhất.

Cách chơi Sudoku cấp độ khó, giải sudoku siêu khó 1. Nối tìm ô trùng lặp để loại trừ

Bước đầu tiên để tìm kiếm các con số dễ dàng nhất là tìm ô trùng lặp và dòng để có thể tìm ra vị trí thích hợp nhất để điền các ô số. Như trong hình trên bạn sẽ thấy chúng ta tập trung tìm số 5 ở vị trí dưới, khi dòng số 5 từ các ô theo hàng sẽ loại trừ được số 5 ở dưới đó đang nằm ở đâu. Tất nhiên ở 2 vị trí khoanh tròn đó vẫn còn phải tiếp tục đối chiếu để biết thực sự số 5 đang nằm ở đâu nhưng chúng ta có thể sử dụng nháp để tạm một vị trí nào đó và đối chiếu các số ở các ô khác nhau nữa.

Phương pháp nối các ô trùng lặp là cách chơi Sudoku cơ bản mà bạn phải biết nếu muốn giải các cấp độ khó khi mà không có nhiều thông tin cho vấn đề này.

2. Tìm số theo bộ 3 hàng dọc, ngang

Chỉ cần nhìn hình trên và nhìn vào ô khoanh tròn, chúng ta có phép loại trừu ở hàng trên và dươi khi tham chiếu vào ô ở giữa, quy tắc để một ô được tồn tại trong sudoku các bạn phải nhớ là duy nhất trong ô 3×3 đó và không cùng hàng với bất cứ ô 3×3 nào khác. Tất nhiên ở các cập độ sudoku cao cấp thì việc để tìm được một bộ ba chứa 1 số như thế này là rất khó, tuy nhiên bạn cũng nên áp dụng cách chơi Sudoku này để kiểm tra thử.

4. Sử dụng nháp khi chơi Sudoku

Cho dù bạn đang chơi Sudoku ở cấp độ nào đi chăng nữa việc ghi chú ra nháp là điều không thể bỏ qua nếu muốn hoàn tất một ván Sudoku. Như ở hình trên chúng ta có thể thấy ở một vùng 3×3 có một số có khả năng nằm ở 2 vị trí trở lên thì hãy ghi chú bé sang bên cạnh để tìm ra đáp án chắc chắn dễ dàng hơn.

5. Lưu ý khi chơi Sudoku

Để có thể cách chơi Sudoku tốt hơn, bạn cần biết một vài gợi ý sau đây

– Tìm các ô dễ trước bằng cách loại trừ (1 số)– Tìm các ô mà khả năng xảy ra chỉ rơi vào 2 số xác định, viết hai số đó nhỏ nhỏ ở góc phải ô (gọi là ô hai số)– ô hai số là cách tuyệt vời để suy luận các ô còn lại trong cột / hàng / bảng

Có rất nhiều mẹo chơi Sudoku mà các bạn có thể áp dụng trong cách chơi của mình, mẹo chơi Sudoku nhanh giúp bạn vượt qua nhiều thử trách trong game.

https://thuthuat.taimienphi.vn/cach-giai-sudoku-cap-do-kho-va-sieu-kho-26406n.aspx Còn nếu chán với những con số mà vẫn muốn chơi các thể loại game giúp bạn mở mang trí óc,tính logic hay suy luận tại sao không thử các tựa game kinh dị hiện nay, game kinh dị ngày nay để thu hút các game thủ đã cải tiến rất nhiều. Không chỉ yếu tốt kinh dị mà còn đòi hỏi tính logic cao, sự khám phá và mày mò của bản thân người chơi.

Microsoft Exel là một công cụ tính toán rất mạnh. Exel có thể làm được rất nhiều việc từ đơn giản đến phức tạp như thực hiện các bảng tính toán đơn giản hay lập các bảng thống kê kinh tế, báo cáo tài chính. v . .v . . Việc giải các phương trình bậc cao hay các hệ phương trình nhiều biến là một công việc khá khó khăn. Tuy nhiên có sự may mắn là hiện nay ta có nhiều công cụ hỗ trợ để giải quyết các công việc này như máy tính cá nhân, máy vi tính với các phần mềm có sẵn, trong đó có phần mềm MS Excel. Bài viết này nhằm giới thiệu cách giải một phương trình bậc cao bằng cách sử dụng phần mềm MS Excel.

Giả sử ta có phương trình bậc 3 là:

– Dòng 1: Bạn tạo các cột các hệ số A,B,C,D và ẩn X, hàm f(x).Như hình sau đây

– Dòng 2: Tương ứng với các hệ số A,B,C,D ẩn X,Hàm f(x) bạn nhập giá trị ở dòng này.Như hình sau đây

Note: Ẩn X : khi này bạn cho 1 giá trị bất kì,k cần thiết là nghiệm.Cho giá trị nào cũng được

Tại ô giá trị hàm f(x): Bạn gõ công thức : =4X^3+5X^2+6X+7

Trong Exel mình sẽ nhập giá trị A=4,… tại các cột dòng 2.Bạn làm vậy khi giải phương trình khác bạn chỉ cần nhập A,B,C,D chứ k phải viết lại

Của mình sẽ là =H8*L8^3+I8*L8^2+J8*L8+K8

Như hình sau đây:

Bạn vào Tool chọn Goal Sheet ( đối với Exel 2003 )

Bạn vào Data chọn What – if Analysis chọn Goal Sheet ( đối với Exel 2007 )

Như hình sau đây :

Khi đó bảng Goal Sheet sẽ hiện ra như sau

Giải thích về cái bảng này chút:

Bạn nhập như này cho mình:

xong ấn ok giá trị bạn thu được tại X sẽ là nghiệm của phương trình

Chú ý: Exel chỉ có thể tính gần đúng nghiệm cho bạn chữ k thể tính được nghiệm chuẩn xác.

Quy lui là một kĩ thuật thiết kế giải thuật dựa trên đệ quy. Ý tưởng của quay lui là tìm lời giải từng bước, mỗi bước chọn một trong số các lựa chọn khả dĩ và đệ quy. Ok. Có vẻ vẫn chưa được rõ ràng lắm. Giờ chúng ta xem xét một vài ví dụ và khái quát hóa phương pháp quay lui.

Bài toán $n$ quân hậu ($n$ Queens)

Bài toán như sau:

Problem 1: Cho một bàn cờ hình vuông kích thước $n times n$ và $n$ quân hậu. Hãy tìm cách đặt $n$ quân hậu trên bàn cờ sao cho không có 2 quân hậu nào có thể ăn được nhau.

Mã hóa lời giải: ta thấy để các quân hâu không ăn được nhau, ta phải xếp $n$ quân hậu trên $n$ hàng của bàn cờ. Ta dùng mảng $Q[1,2,ldots,n]$, trong đó $Q[i] = j$ nếu quân hậu ở hàng thứ $i$ được đặt ở cột $j$.

Ý tưởng chính của thuật toán: giả sử chúng ta đã đặt được $r-1$ quân hậu, $1 leq r < n$, trên $r-1$ hàng đầu tiên sao cho không có 2 quân hậu nào ăn được nhau. Cụ thể các phần tử $Q[1,2,ldots, r-1]$ sẽ khác $0$ và các phần tử $Q[r,r+1. ldots, n]$ đều bằng $0$. Chúng ta tìm cách đặt một quân hậu trên hàng thứ $r$. Ta sẽ thử lần lượt đặt vào cột thứ $1,2,ldots, n$. Nếu đặt vào cột thứ $j$ mà bị một trong $r$ quân hậu đã đặt trước đó ăn, ta sẽ thử cột thứ $j+1$. Nếu ta tìm được một ví trí đặt khả dĩ (a feasible position), ta sẽ đặt vào đó và gọi đệ quy để đặt hàng thứ $r+1$. Giả mã như sau:

RecursiveQueen($Q[1,2,ldots, n],r$):     if$(r = n+ 1)$         print $Q$    else         for $j leftarrow 1$ to $n$             $legal leftarrow $ True             for $i leftarrow 1$ to $r-1$              $ll$ check conflict $gg$                 if $(Q[i] = j)$ or $(Q[i] = j+r-i)$ or $(Q[i] = j-r+i)$                     $legal leftarrow $ False             if $legal =$ True                 $Q[r] leftarrow j$                 RecursiveQueen($Q[1,2,ldots, n],r+1$)

  Code của giả mã bằng C. Code đầy đủ được cho ở cuối bài.

void recursive_queen(int _array[], int n, int r){ int i=1, j = 1; int legal = 0; if(r == n +1){ print_queen(_array, n); exit(0); } else{ for(j = 1; j &lt;= n ; j++){ legal = 1; for(i = 1; i &lt;= r-1; i++){ legal = 0; } } if(legal == 1) { _array[r] = j; recursive_queen(_array, n, r+1); } } } }

  Có thể thấy thuật toán trên có thời gian cỡ $O(n!)$. Tuy nhiên nếu bạn cần một lời giải bất kì, bài toán này có công thức giải và bạn chỉ mất thời gian để in lời giải ra ($O(n)$)[3].

Sudoku

Sudoku là một trò chơi khá phổ biến và chắc ai (readers of this bog) cũng biết. Trò chơi như sau: có một hình vuông được chia thành 9×9 ô vuông con. Mỗi ô vuông con có giá trị trong khoảng từ 1 đến 9. Ban đầu hình vuông có một số ô vuông con cho trước (có điền sẵn số) và còn lại là trống. Hãy điền các số từ 1-9 vào các ô con lại sao cho: hàng ngang là các số khác nhau từ 1 đến 9, hàng dọc là các số khác nhau từ 1 đến 9, và mỗi khối 3×3 chính là các số khác nhau từ 1 đến 9. Ví dụ một câu đố và lời gải tương ứng như sau (hình được lấy từ wikipedia):

Trong bài này mình sẽ giới thiệu cách giải sudoku bằng thuật toán quay lui. Ý tưởng của thuật toán cũng giống bài toán $n$ quân hậu. Mỗi bước tìm tập các giá trị khả dĩ để điền vào ô trống, và sau đó đệ quy để điền ô tiếp theo. Giả mã của thuật toán (ở đây chú ý mảng chỉ có kích thước $9times 9$). Thủ tục Feasible$(S,x,y,k)$ kiểm trả xem giá trị $k$ có khả dĩ với ô $S[x][y]$ không.

Sudoku($S[1,2,ldots, 9][1,2,ldots, 9],x,y$):     if $y = 10$         if $x = 9$             print $S$        else             Sudoku($S[1,2,ldots, 9][1,2,ldots, 9],x+1,1$)     else if $S[x,y] = emptyset$         for $k leftarrow 1$ to $9$             if Feasible$(S,x,y,k)$                 $S[x,y] leftarrow k$                 Sudoku($S[1,2,ldots, 9][1,2,ldots, 9],x,y+1$)                 $S[x,y] leftarrow emptyset$        $ll$ for next branching $gg$     else                                    $ll S[x,y]$ is given $gg$         Sudoku($S[1,2,ldots, 9][1,2,ldots, 9],x,y+1$)

  Code của giả mã trên bằng C:

void solve_sudoku(int S[][9], int x, int y){ if(y == 9){ if(x == 8){ printSolution(S); exit(0); } else { solve_sudoku(S, x+1,0); } } else if(S[x][y] == 0){ int k = 0; for (k = 1; k &lt;=9; k++){ if(feasible(S,x,y,k)){ S[x][y] = k; solve_sudoku(S, x, y+1); S[x][y] = 0; } } } else { solve_sudoku(S,x,y+1); } }

  Giả mã của thủ tục Feasible$(S,x,y,k)$ như sau:

Feasible($S[1,2,ldots, 9][1,2,ldots, 9],x,y, k$):     for $i leftarrow 1$ to $9$         if $S[x,i]=k$             return False     for $i leftarrow 1$ to $9$         if $S[i,y]=k$             return False     $a leftarrow lfloor (x-1)/3 rfloor, b leftarrow lfloor (y-1)/3 rfloor $     for $i leftarrow 3a+1$ to $3a+3$         for $j leftarrow 3b+1$ to $3b+3$            if $S[i,j] = k$                 return False     return True

  Code bằng C của giả mã (code đầy đủ được cho ở cuối bài):

int feasible(int S[][9], int x, int y, int k){ int i = 0, j = 0; for(i = 0; i &lt;9 ; i++){ if(S[x][i] == k) return 0; } for(i = 0; i &lt;9 ; i++){ if(S[i][y] == k) return 0; } int a = x/3, b = y/3; for(i = 3*a; i &lt; 3*a+3; i++){ for(j = 3*b; j &lt; 3*b+3; j++){ if(S[i][j] == k) return 0; } } return 1; }

Subset Sum

Subset Sum là một trong những bài toán NP-hard. Trong bài này chúng ta sẽ thiết kế thuật toán quay lui để giải bài toán Subset Sum.

Problem 2: Cho một mảng $n$ phần tử $X[1,2,ldots, n]$ không âm và một số $T$. Có tồn tại một tập con các phần tử của mảng $X$ sao cho tổng của chúng bằng $T$.

  Ví dụ: $X = {8,6,7,5,3,10,9}$ và $T = 12$. Lời giải là true vì tập con ${7,5}$ của $X$ có tổng bằng 12.

Ý tưởng của thuật toán quay lui dựa trên quan sát sau: xét một phần tử $x in X$, tồn tại một dãy con có tổng bằng $T$ nếu một trong hai điều kiện sau là đúng:

Tồn tại một tập con của $X setminus {x}$ có tổng bằng $T – x$

Tồn tại một tập con của $X setminus {x}$ có tổng bằng $T$

Giả mã như sau:

SubsetSum($X[1,2,ldots, n],r,T$):     if $T = 0$         return True         return False     return SubsetSum$(X[1,2,ldots,n-1],T)$ Or                 SubsetSum$(X[1,2,ldots,n-1],T- X[n])$

  Code của giả mã bằng C:

int subset_sum(int X[], int r, int T){ if(T == 0) return 1; if(subset_sum(X, r-1, T-X[r]) == 1) return 1; if(subset_sum(X,r-1, T) == 1) return 1; return 0; }

Phân tích thời gian: Ở mỗi bước của thuật toán quay lui, ta gọi đệ quy hai lần trên mảng con của $X$ với kích thước nhỏ hơn 1. Ta có:

$ T(n) = 2T(n-1) + O(1) = O(2^n)$

Code: queen, sudoku, subsetsum, data of subsetsum

Tài liệu tham khảo

[1] J. Erickson. Algorithm Lecture Notes, UIUC. [2] $n$ queen on stackexchange: http://cstheory.stackexchange.com/questions/12682/is-the-n-queens-problem-np-hard [3] B. Bernhardsson, Explicit Solutions to the N-queens Problem for All N, SIGART Bull. 2(2)(1991)7.

Bài Tập

Bài 1 (Longest Increasing Subsequence) Cho một mảng $n$ phần tử $A[1,2,ldots,n]$. Tìm một dãy dài nhất ($k$ lớn nhất) các chỉ số $1 leq i_1$ < $i_2 $<$ ldots $<$ i_k leq n $ sao cho $A[i_1] leq A[i_2] leq ldots leq A[i_k]$ bằng phương pháp quay lui. (Gợi ý: xét $A[1]$, nếu $A[1]$ nằm trong dãy con tăng, đệ quy trên $A[2,3,ldots]$ tìm dãy con tăng dài nhất mà mọi phần tử đều lớn hơn $A[1]$. Nếu $A[1]$ không nằm trong dãy con tăng, đệ quy trên $A[2,3,ldots,n]$).

Bài 3 Hãy sửa đổi thuật toán quay lui ở trên của bài toán Subset Sum để in ra ít nhất một dãy con có tổng bằng $T$ của $X$.