Home > Programming > How to solve Sudoku puzzle within 1 minute?

How to solve Sudoku puzzle within 1 minute?

Sudoku hấp dẫn người ta ở chỗ biến hóa không lường mặc dù luật chơi hết sức đơn giản. Chính vì vậy, những thủ thuật được giới thiệu trong nhiều tài liệu hướng dẫn chơi xem ra không có gì là thủ thuật. Sudoku vẫn là thách thức cho tất cả chúng ta, điều này hoàn toàn khác hẳn với Rubik. Vậy tại sao title lại dám viết như vậy?

Những bạn đọc tinh ý chắc cũng đoán được rằng chỉ có cách dùng máy tính thì mới giải nhanh như thế được. Chính xác là như vậy! Tôi đã dựa trên một  thuật toán hết sức cùi bắp, dùng c++ để viết cách giải cho bất kì bài toán Sudoku nào. Cụ thể như sau:

+Các ô hàng ngang, hàng dọc đều được đánh số thứ tự từ 0 đến 8, thuật toán bắt đầu điền từ ô (0,0)

+Ô nào đề bài đã cho số thì skip sang ô kế tiếp, ô nào trống sẽ được lựa 1 số (bắt đầu từ 1) điền vào, lựa bằng cách xem hàng nganh, hàng học và trông ô vuông nhỏ có số đó chưa, điền xong nhảy sang ô kế.

+Điền xong ô (8,8) thì kết thúc.

+Nếu thử từ 1 đến 9 đều không được thì nhảy trở về ô trước đó được điền để chọn số khác.

Bạn nào quan tâm có thể xem file .cpp đính kèm. Nếu chỉ cần bài giải thì bạn làm như sau:

+Click here to download the package

+Extract

+Edit file input.txt: enter row no (0 to 8), column no(0 to 8), and the value of that cell (as in the problem), put -1 at the end of the file.

+Double click run.bat and open output.txt to view the result.

PS: Báo tuổi trẻ có đăng trò chơi này thường xuyên, giải sớm rinh về 200K.

#include<iostream>
using namespace std;
class Sudoku{
int cells[9][9];
int x,y;
public:
Sudoku();
void Add(int ,int ,int);
bool isGood(int ,int,int);
bool Fill(int,int);
friend ostream & operator <<(ostream & out,const Sudoku & s){
out<<endl;
for(int i=0;i<9;i++){
if(i==0||i==3||i==6)
out<<” ———————–\n”;
for(int j=0;j<9;j++){
if(j==0||j==3||j==6)
out<<“| “;
out<<s.cells[i][j]<<‘ ‘;
}
out<<‘|'<<endl;
}
out<<” ———————–“<<endl;
return out;
}
};
Sudoku::Sudoku(){
for(int i=0;i<9;i++)
for(int j=0;j<9;j++){
cells[i][j]=0;
}
}
void Sudoku::Add(int x,int y,int v){
cells[x][y]=v;
}
bool Sudoku::isGood(int x,int y, int v){
int i,j;
for(i=0;i<9;i++)
if(v==cells[i][y])return 0;
for(i=0;i<9;i++)
if(v==cells[x][i])return 0;
if(x>=0&&x<=2&&y>=0&&y<=2){
for(i=0;i<=2;i++)
for(j=0;j<=2;j++)
if(v==cells[i][j])return 0;
}
if(x>=0&&x<=2&&y>=3&&y<=5){
for(i=0;i<=2;i++)
for(j=3;j<=5;j++)
if(v==cells[i][j])return 0;
}
if(x>=0&&x<=2&&y>=6&&y<=8){
for(i=0;i<=2;i++)
for(j=6;j<=8;j++)
if(v==cells[i][j])return 0;
}
if(x>=3&&x<=5&&y>=0&&y<=2){
for(i=3;i<=5;i++)
for(j=0;j<=2;j++)
if(v==cells[i][j])return 0;
}
if(x>=3&&x<=5&&y>=3&&y<=5){
for(i=3;i<=5;i++)
for(j=3;j<=5;j++)
if(v==cells[i][j])return 0;
}
if(x>=3&&x<=5&&y>=6&&y<=8){
for(i=3;i<=5;i++)
for(j=6;j<=8;j++)
if(v==cells[i][j])return 0;
}
if(x>=6&&x<=8&&y>=0&&y<=2){
for(i=6;i<=8;i++)
for(j=0;j<=2;j++)
if(v==cells[i][j])return 0;
}
if(x>=6&&x<=8&&y>=3&&y<=5){
for(i=6;i<=8;i++)
for(j=3;j<=5;j++)
if(v==cells[i][j])return 0;
}
if(x>=6&&x<=8&&y>=6&&y<=8){
for(i=6;i<=8;i++)
for(j=6;j<=8;j++)
if(v==cells[i][j])return 0;
}
return 1;
}bool Sudoku::Fill(int x,int y){
if (y == 9) {
y = 0;
if (++x == 9)
return true;
}
if (cells[x][y] != 0)  // skip filled cells
return Fill(x,y+1);for (int val = 1; val <= 9; ++val) {
if (isGood(x,y,val)) {
cells[x][y] = val;
if (Fill(x,y+1))
return true;
}
}
cells[x][y] = 0; // reset on backtrack
return false;

}
int main(){
Sudoku s;
int x1,y1,v1;
while(cin>>x1){
if(x1>=0&&x1<9){
cin>>y1>>v1;
s.Add(x1,y1,v1);
}
else{
s.Fill(0,0);
cout<<s;
return 0;
}
}
return 0;
}

Sudoku hấp dẫn người ta ở chỗ biến hóa không lường mặc dù luật chơi hết sức đơn giản. Chính vì vậy, những thủ thuật được giới thiệu trong nhiều tài liệu hướng dẫn chơi xem ra không có gì là thủ thuật. Sudoku vẫn là thách thức cho tất cả chúng ta, điều này hoàn toàn khác hẳn với Rubik. Vậy tại sao title lại dám viết như vậy?

Những bạn đọc tinh ý chắc cũng đoán được rằng chỉ có cách dùng máy tính thì mới giải nhanh như thế được. Chính xác là như vậy! Tôi đã dựa trên một  thuật toán hết sức cùi bắp, dùng c++ để viết cách giải cho bất kì bài toán Sudoku nào. Cụ thể như sau:

+Các ô hàng ngang, hàng dọc đều được đánh số thứ tự từ 0 đến 8, thuật toán bắt đầu điền từ ô (0,0)

+Ô nào đề bài đã cho số thì skip sang ô kế tiếp, ô nào trống sẽ được lựa 1 số (bắt đầu từ 1) điền vào, lựa bằng cách xem hàng nganh, hàng học và trông ô vuông nhỏ có số đó chưa, điền xong nhảy sang ô kế.

+Điền xong ô (8,8) thì kết thúc.

+Nếu thử từ 1 đến 9 đều không được thì nhảy trở về ô trước đó được điền để chọn số khác.

Bạn nào quan tâm có thể xem file .cpp đính kèm. Nếu chỉ cần bài giải thì bạn làm như sau:

+Click here to download the package

+Extract

+Edit file input.txt: enter row no (0 to 8), column no(0 to 8), and the value of that cell (as in the problem), put -1 at the end of the file.

+Double click to run.bat and open output.txt to view the result.

PS: Báo tuổi trẻ có đăng trò chơi này thường xuyên, giải sớm rinh về 200K.

#include<iostream>
using namespace std;
class Sudoku{
int cells[9][9];
int x,y;
public:
Sudoku();
void Add(int ,int ,int);
bool isGood(int ,int,int);
bool Fill(int,int);
friend ostream & operator <<(ostream & out,const Sudoku & s){
out<<endl;
for(int i=0;i<9;i++){
if(i==0||i==3||i==6)
out<<” ———————–\n”;
for(int j=0;j<9;j++){
if(j==0||j==3||j==6)
out<<“| “;
out<<s.cells[i][j]<<‘ ‘;
}
out<<‘|'<<endl;
}
out<<” ———————–“<<endl;
return out;
}
};
Sudoku::Sudoku(){
for(int i=0;i<9;i++)
for(int j=0;j<9;j++){
cells[i][j]=0;
}
}
void Sudoku::Add(int x,int y,int v){
cells[x][y]=v;
}
bool Sudoku::isGood(int x,int y, int v){
int i,j;
for(i=0;i<9;i++)
if(v==cells[i][y])return 0;
for(i=0;i<9;i++)
if(v==cells[x][i])return 0;
if(x>=0&&x<=2&&y>=0&&y<=2){
for(i=0;i<=2;i++)
for(j=0;j<=2;j++)
if(v==cells[i][j])return 0;
}
if(x>=0&&x<=2&&y>=3&&y<=5){
for(i=0;i<=2;i++)
for(j=3;j<=5;j++)
if(v==cells[i][j])return 0;
}
if(x>=0&&x<=2&&y>=6&&y<=8){
for(i=0;i<=2;i++)
for(j=6;j<=8;j++)
if(v==cells[i][j])return 0;
}
if(x>=3&&x<=5&&y>=0&&y<=2){
for(i=3;i<=5;i++)
for(j=0;j<=2;j++)
if(v==cells[i][j])return 0;
}
if(x>=3&&x<=5&&y>=3&&y<=5){
for(i=3;i<=5;i++)
for(j=3;j<=5;j++)
if(v==cells[i][j])return 0;
}
if(x>=3&&x<=5&&y>=6&&y<=8){
for(i=3;i<=5;i++)
for(j=6;j<=8;j++)
if(v==cells[i][j])return 0;
}
if(x>=6&&x<=8&&y>=0&&y<=2){
for(i=6;i<=8;i++)
for(j=0;j<=2;j++)
if(v==cells[i][j])return 0;
}
if(x>=6&&x<=8&&y>=3&&y<=5){
for(i=6;i<=8;i++)
for(j=3;j<=5;j++)
if(v==cells[i][j])return 0;
}
if(x>=6&&x<=8&&y>=6&&y<=8){
for(i=6;i<=8;i++)
for(j=6;j<=8;j++)
if(v==cells[i][j])return 0;
}
return 1;
}bool Sudoku::Fill(int x,int y){
if (y == 9) {
y = 0;
if (++x == 9)
return true;
}
if (cells[x][y] != 0)  // skip filled cells
return Fill(x,y+1);for (int val = 1; val <= 9; ++val) {
if (isGood(x,y,val)) {
cells[x][y] = val;
if (Fill(x,y+1))
return true;
}
}
cells[x][y] = 0; // reset on backtrack
return false;

}
int main(){
Sudoku s;
int x1,y1,v1;
while(cin>>x1){
if(x1>=0&&x1<9){
cin>>y1>>v1;
s.Add(x1,y1,v1);
}
else{
s.Fill(0,0);
cout<<s;
return 0;
}
}
return 0;
}

Categories: Programming Tags:
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: