8-puzzle


#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <deque>
#include <stack>
using namespace std;

class State{
public:
int a[9];

State(){
for(int i=0; i<9; i++){
a[i] = rand() % 9;
while (found(i)) { a[i] = rand() % 9; }
}
}


void print(){
cout << "-----------------" << endl;
for(int i=0; i<9; i++){
if (i>0 && i%3==0) cout << endl;
cout << a[i] << "\t";
}
cout << endl << "-----------------" << endl;
}


int found(int i){
for(int j=0; j<i; j++){
if (a[i]==a[j]) return 1;
}
return 0;
}


int findzero(){
for (int i=0; i<9; i++){
if (a[i]==0) return i;
}
}


State exch(int i, int j){
State b;
for (int k=0; k<9; k++)
b.a[k]=a[k];
int t=b.a[i];
b.a[i]=b.a[j];
b.a[j]=t;
return b;
}
int equal(State s){
for(int i=0; i<9; i++){
if (a[i]!=s.a[i]) return 0;
}
return 1;
}


int goal(){
int g[9] = {1,2,3,8,0,4,7,6,5};
for (int i=0; i<9; i++){
if (a[i]!=g[i]) return 0;
}
return 1;
}
};

class Node{
public:
State s;
Node *father;
int action, cost, depth;


Node(){
State s();
father=NULL;
action=-1;
cost=1;
depth=0;
}


Node(State _s, Node *_father, int _action, int _depth){
s=_s;
father=_father;
action=_action;
depth=_depth;
}


Node copy(){
Node b;
for (int i=0; i<9; i++)
b.s.a[i]=s.a[i];
b.father=father;
b.action=action;
b.depth=depth;

return b;
}


void print(){
cout << "Cost: \t" << cost << endl;
cout << "Depth: \t" << depth << endl;
}


void expand(deque<Node> *deque){
int p = s.findzero();
// up(0)
if ((p!=0 && p!=1 && p!=2) && action!=1){
Node n(s.exch(p,p-3), this, 0, depth+1);
(*deque).push_back(n);
}
//down (1)
if ((p!=6 && p!=7 && p!=8) && action!=0){
Node n(s.exch(p,p+3), this, 1, depth+1);
(*deque).push_back(n);
}
//right (2)
if ((p!=2 && p!=5 && p!=8) && action!=3){
Node n(s.exch(p,p+1), this, 2, depth+1);
(*deque).push_back(n);
}
//left (3)
if ((p!=0 && p!=3 && p!=6) && action!=2){
Node n(s.exch(p,p-1), this, 3, depth+1);
(*deque).push_back(n);
}
}


int expanded(deque<State> *deque){
int max=(*deque).size()>depth?depth:(*deque).size();
for (int i=0; i<max; i++){
if ( s.equal( (*deque)[i] ) ){
return 1;
}
}
return 0;
}
int bfs(){
deque<Node> toexpand;
deque<State> expanded;

toexpand.push_back(*this);
while ( !toexpand.empty() ){
if ( toexpand.front().s.goal()==1 ){
cout << "BFS" << endl;
cout << "OK i found a solution!" << endl;
toexpand.front().print();
cost = toexpand.front().cost;
toexpand.clear();
return cost;
}
else{
if ( !(toexpand.front().expanded(&expanded)) ){
toexpand.front().expand(&toexpand);
expanded.push_front( toexpand.front().s );
toexpand[1].cost=toexpand[0].cost+1;
}
toexpand.pop_front();
}
}
if ( toexpand.empty() ) cout << endl << "I can't find any solution!" << endl;
return 0;
}

int dfs(int idsdepth){
deque<Node> toexpand;

if (idsdepth==-1) idsdepth = sizeof(int);

toexpand.push_back(*this);
while ( !toexpand.empty() ){
if (toexpand.back().depth < idsdepth){
if ( toexpand.back().s.goal()==1 ){
if (idsdepth == sizeof(int))
cout << "------|DFS|------" << endl;
else
cout << "------|IDS|------" << endl;
cout << "Solution found!" << endl;
toexpand.back().print();
toexpand.clear();
return cost;
}
else{
Node t;
t= toexpand.back().copy();
toexpand.pop_back();
t.expand(&toexpand);
}
}
else return 0;
}
if ( toexpand.empty() ) cout << endl << "Solution NOT found!" << endl;
return 0;
}

int ids(){
for(int i=0;;i++){
int t = dfs(i);
if (t!=0) return t;
}
}
};
int main(int argc, char *argv[]){
int num=1;
int bfscost=0;
int bfsfail=0;
int dfscost=0;
int dfsfail=0;
int idscost=0;
int idsfail=0;
cout << "\nEnter number of problems to solve: ";
cin >> num;
cout << endl;

if (argc == 2){
cout << "-------DEMO------\n\n";
}

for(int i=0;i<num;i++){
int _bfs=0;
int _dfs=0;
int _ids=0;

cout << "\n Problem " << i+1 << endl;
srand(argc==2?(2*i+1):time(NULL)+i);
Node n;
n.s.print();

_bfs=n.bfs();
// _dfs=n.dfs(-1);
// _ids=n.ids();

if (_bfs>0)
bfscost+=_bfs;
else
bfsfail+=1;

if (_dfs>0)
dfscost+=_dfs;
else
dfsfail+=1;

if (_ids>0)
idscost+=_ids;
else
idsfail+=1;
}
if (num > 1){
cout << "\n\n------|BFS|-------";
cout << "\nAverage cost = " << bfscost/(num-bfsfail);
cout << "\nSolved " << num-bfsfail << "/" << num;
cout << "\n------------------";
// cout << "\n\n------|DFS|-------";
// cout << "\nAverage cost = " << dfscost/(num-dfsfail);
// cout << "\nSolved " << num-dfsfail << "/" << num;
// cout << "\n------------------";
// cout << "\n\n------|IDS|-------";
// cout << "\nAverage cost = " << idscost/(num-idsfail);
// cout << "\nSolved " << num-idsfail << "/" << num;
// cout << "\n------------------";
cout << endl;
}

return 0;
}

Biểu diễn Danh sách kề sang Ma trận kề

// thêm -1 ở cuối mỗi dòng chỉ là thủ thuật nhỏ mà thôi, nếu muốn giữ nguyên input (không có -1) thì bạn phải chuyển dữ liệu nhập vào sang kiểu char rồi xử lý.

Cho danh sách kề như sau, biểu diễn đồ thị có 5 đỉnh (vertex)

v1 connect to 2, 3;

v2 -> 1, 3, 5

v3 -> 1, 2, 5

v4 -> 5

v5 -> 2, 3, 4

5
2 3 -1
1 3 5 -1
1 2 5 -1
5 -1
2 3 4 -1

…….. solution:

#include <fstream>
#include<iostream>
#include <vector>
#define MAX 1000
#define FI "DanhSachKe.INP"
#define FO "GRAPH.out"
using namespace std;
int A[MAX][MAX];//Ma tran ke
vector<vector<int>> matrix;
int N;//so dinh
ifstream fi;//doc file
ofstream fo;//xuat file
vector<int> vec;
void Input(){
 fi.open(FI);
 fi >> N;
 matrix.resize(N);
 for(int i=0; i<N; i++){
 int ver;
 do 
 {
 fi >> ver;
 if(ver != -1){
 matrix[i].push_back(ver);
 }
 } while (ver != -1);
 }
 fi.close();
}
void setMatrix(int x){
}
void Xuat(){
 fo.open(FO);
 // matrix.resize(N+1);
 for(int i=0; i<matrix.size(); i++){
 for(int j=0; j<matrix[i].size(); j++){
 cout << matrix[i][j] << " ";
 }
 cout << endl;
 }
 fo.close();
}
void DSK2MTK(){
 for(int i=0; i<N; i++){
 for(int j=0; j<N; j++){
 A[i][j] = 0;
 }
 }
 for(int i=0; i<N; i++){
 for(int j=0; j<matrix[i].size(); j++){
 A[i][matrix[i][j]-1] = 1;
 }
 }
}
void xuatMTK(){
 for(int i=0; i<N; i++){
 for(int j=0; j<N; j++){
 cout << A[i][j] << " ";
 }
 cout << endl;
 }
}
int main(){
 // nhapDSK();
 Input();
 Xuat();
 DSK2MTK();
 xuatMTK();
 return 0;
}

DFS / BFS / Euler trên ma trận kề

Cho ma trận kề:

8 // số đỉnh (the number of vertex)
0 1 0 0 0 0 1 1
1 0 0 1 0 0 0 0
0 0 0 0 1 0 1 1
0 1 0 0 1 0 0 0
0 0 1 1 0 1 1 0
0 0 0 0 1 0 1 0
1 0 1 0 1 1 0 0
1 0 1 0 0 0 0 0

……….. Simple solution for beginner:

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define FI "MTK.INP"
#define FO "DFS.OUT"
#define MAX 100
ifstream fi;
ofstream fo;
int n;
vector<vector<int> > MTK;
vector<bool> visited;
void DocFile(){
 fi.open(FI);
 fi >> n;
 visited.resize(n);
 MTK.resize(n);
 for(int i=0; i<n; i++){
 for(int j=0; j<n; j++){
 int temp;
 fi >> temp;
 MTK[i].push_back(temp);
 }
 }
 fi.close();
}
void InitUnvisited(){
 for(int i=0; i<visited.size(); i++){
 visited[i] = false;
 }
}
void DFS(int u){
 visited[u] = true;
 // cout << u << "-> ";
 for(int i=0; i<n; i++){
 if(visited[i] == false && MTK[u][i] == 1){
 DFS(i);
 }
 }
}
int KiemTraChuaXet(){
 for (int i=0;i<n;i++)
 if (visited[i]==false) return i;
 return -1;
}
int DemThanhPhanLienThong(){
 int slt = 0;
 InitUnvisited();
 while(KiemTraChuaXet()!=-1){
 int i = KiemTraChuaXet();
 DFS(i);
 slt++;
 }
 cout << slt;
 return slt;
}
int BacDinh(int i){
 int bac = 0;
 for(int j=0; j<n; j++){
 bac += MTK[i][j];
 }
 return bac;
}
// 
// void XuatFile(){
// fo.open(FO);
// 
// for(int i=0; i<MTK.size(); i++){
// for(int j=0; j<MTK.size(); j++){
// fo << MTK[i][j] << " ";
// }
// fo << endl;
// }
// fo.close();
// }
// 
void isEuler(){
 if(DemThanhPhanLienThong() == 1){
 int sodinhle = 0;
 for(int i=0; i<n; i++){
 if(BacDinh(i) % 2 !=0){
 sodinhle++;
 }
 }
 if(sodinhle == 0){
 cout << "la Euler";
 }
 else{
 if(sodinhle == 2){
 cout << "nua euler";
 }
 else{ cout << "khong phai euler";}
 }
 }
 else { cout << "no";}
}
void BFS(int u){
 int queue[MAX], dau = 0, cuoi = 0;
 InitUnvisited();
 for(int i=0; i<MAX; i++){
 queue[i] = 0;
 }
 queue[cuoi] = u;
 visited[u] = true;
 cout << u << "->";
 while(dau >= cuoi){
 int p = queue[cuoi];
 cuoi++;
 for(int i=0; i<n; i++){
 if(visited[i] == false && MTK[p][i] == 1){
 dau++;
 queue[dau] = i;
 visited[i] = true;
 cout << i << "->";
 }
 }
}
}
int main()
{
 DocFile();
 InitUnvisited();
 DFS(0);
 //DemThanhPhanLienThong();
 // XuatFile();
 isEuler();
 BFS(0);
return 0;
}