人工智能实验一

野生智能尝试做业（8数码）

8数码答题也称为9宫答题。正在三×三的棋盘，晃有8个棋子，每一个棋子上标有一至八的某1数字，没有异棋子上标的数字没有沟通。棋盘上借有1个空格，取空格相邻的棋子能够移到空格外。请求解决的答题是：给没1个始初状况以及1个宗旨状况，找没1种从始初状况变化成宗旨状况的挪动棋子步数起码的挪动步骤。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <queue>
#include <vector>

using namespace std;

char d[五] = "drul";
int dx[四] = {一, 0, ⑴, 0}, dy[四] = {0, 一, 0, ⑴};
int cnt = 0,cnt_a = 0;
// string ed = "一二三四五六七八x";

unordered_map<string, int> p;
unordered_map<string, string> pp;

bool bfs(string s,string edd)
{
    queue<string> q;

    q.push(s);
    p[s] = 0;

    while (q.size())
    {
        string sh = q.front();
        q.pop();
        string h = sh;

        if (sh == edd) return true;

        int k = sh.find('0');
        int x = k / 三, y = k % 三;
        for (int i = 0; i < 四; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < 三 && b >= 0 && b < 三)
            {

                int t = a * 三 + b;
                swap(sh[k], sh[t]);
                if (!p.count(sh))
                {
                    p[sh] = i;
                    pp[sh] = h;
                    q.push(sh);
                }
                swap(sh[t], sh[k]);
            }
        }
    }

    return false;
}

void Left_shift(string &a, int &b){
    int len = a.size() ;
    int f = 0 ;
    for(int i = 0 ; i < len ; i ++)
    {
        if(a[i] == '0')
        {
            f = i;
            break;
        }
    }
    swap(a[f],a[f⑴]);
    cnt ++;
    cout << "**步数" << cnt <<endl ;
    cout << "|    "<< a[0] << "     " << a[一] << "     " << a[二] << "    |" << endl ;
    cout << "|    "<< a[三] << "     " << a[四] << "     " << a[五] << "    |" << endl ;
    cout << "|    "<< a[六] << "     " << a[七] << "     " << a[八] << "    |" << endl ;

}

void Right_shift(string &a, int &b){
    int len = a.size() ;
    int f = 0 ;
    for(int i = 0 ; i < len ; i ++)
    {
        if(a[i] == '0')
        {
            f = i;
            break;
        }
    }
    swap(a[f],a[f+一]);
    cnt ++;
    cout << "**步数" << cnt <<endl ;
    cout << "|    "<< a[0] << "     " << a[一] << "     " << a[二] << "    |" << endl ;
    cout << "|    "<< a[三] << "     " << a[四] << "     " << a[五] << "    |" << endl ;
    cout << "|    "<< a[六] << "     " << a[七] << "     " << a[八] << "    |" << endl ;
}

void Up_shift(string &a, int &b){
    int len = a.size() ;
    int f = 0 ;
    for(int i = 0 ; i < len ; i ++)
    {
        if(a[i] == '0')
        {
            f = i;
            break;
        }
    }
    int xi = f / 三 , yi = f % 三 ;
    int ff = (xi - 一) * 三 + yi ;
    swap(a[ff] , a[f]);
    cnt ++;
    cout << "**步数" << cnt <<endl ;
    cout << "|    "<< a[0] << "     " << a[一] << "     " << a[二] << "    |" << endl ;
    cout << "|    "<< a[三] << "     " << a[四] << "     " << a[五] << "    |" << endl ;
    cout << "|    "<< a[六] << "     " << a[七] << "     " << a[八] << "    |" << endl ;
}

void Down_shift(string &a, int &b){
    int len = a.size() ;
    int f = 0 ;
    for(int i = 0 ; i < len ; i ++)
    {
        if(a[i] == '0')
        {
            f = i;
            break;
        }
    }
    int xi = f / 三 , yi = f % 三 ;
    int ff = (xi + 一) * 三 + yi ;
    swap(a[ff] , a[f]);
    cnt ++;
    cout << "**步数" << cnt <<endl ;
    cout << "|    "<< a[0] << "     " << a[一] << "     " << a[二] << "    |" << endl ;
    cout << "|    "<< a[三] << "     " << a[四] << "     " << a[五] << "    |" << endl ;
    cout << "|    "<< a[六] << "     " << a[七] << "     " << a[八] << "    |" << endl ;
}

int Differences(string str一,string str二){
    int len = str一.size(),count = 0;
    for(int i = 0 ; i < len ; i ++){
        if(str一[i] != str二[i]) count ++ ;
    }
    return count ;
}

int main()
{
    cout << "请输进始初状况的8数码:" <<endl ;
    string s, c;
    for (int i = 0; i < 九; i ++ ) cin >> c, s += c;
    cout << endl ;
    string ed, c一;
    cout << "请输进终极状况的8数码:" <<endl ;
    for (int i = 0; i < 九; i ++ ) cin >> c一, ed += c一;
    cout << endl ; 
    
    if (bfs(s,ed))
    {
        vector<char> arr;
        string t = ed;
        while(t != s)
        {
            arr.push_back(d[p[t]]);  //将挪动圆式存高   
            t = pp[t]; 
        }
        cout << "^^^搜刮成果：^^^"<< endl ;
        for (int i = arr.size() - 一; i >= 0; i -- )
        {
            if(arr[i] == 'l') 
            {
                Left_shift(s,cnt) ;
                cnt_a = Differences(s,ed);
                cout << "差异：" << cnt_a << endl ;
                cout << endl ;cout << "------------" << endl;
            }
            else if(arr[i] == 'r') {
                Right_shift(s,cnt) ;
                cnt_a = Differences(s,ed);
                cout << "差异：" << cnt_a << endl ;
                cout << endl ;cout << "------------" << endl;
            }
            else if(arr[i] == 'u') {
                Up_shift(s,cnt) ;
                cnt_a = Differences(s,ed);
                cout << "差异：" << cnt_a << endl ;
                cout << endl ;cout << "------------" << endl;
            }
            else if(arr[i] == 'd') {
                Down_shift(s,cnt) ;
                cnt_a = Differences(s,ed);
                cout << "差异：" << cnt_a << endl ;
                cout << endl ;cout << "------------" << endl;
            }
        }

        cout << endl;
    }
    else cout << "unsolvable" << endl;
    return 0;
}

提交做业（软搬）只为取嫩师的1致且悦目

#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <queue>
#include <vector>

using namespace std;

char d[五] = "drul";
int dx[四] = {一, 0, ⑴, 0}, dy[四] = {0, 一, 0, ⑴};
int cnt = 0;
int cnt_a = 0 ;
string ed = "一二三八0四七六五";

unordered_map<string, int> p;
unordered_map<string, string> pp;

bool bfs(string s)
{
    queue<string> q;

    q.push(s);
    p[s] = 0;

    while (q.size())
    {
        string sh = q.front();
        q.pop();
        string h = sh;

        if (sh == ed) return true;

        int k = sh.find('0');
        int x = k / 三, y = k % 三;
        for (int i = 0; i < 四; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < 三 && b >= 0 && b < 三)
            {

                int t = a * 三 + b;
                swap(sh[k], sh[t]);
                if (!p.count(sh))
                {
                    p[sh] = i;
                    pp[sh] = h;
                    q.push(sh);
                }
                swap(sh[t], sh[k]);
            }
        }
    }

    return false;
}

void Left_shift(string &a, int &b){
    int len = a.size() ;
    int f = 0 ;
    for(int i = 0 ; i < len ; i ++)
    {
        if(a[i] == '0')
        {
            f = i;
            break;
        }
    }
    swap(a[f],a[f⑴]);
    cnt ++;
    cout << "**步数" << cnt <<endl ;
    cout << "|    "<< a[0] << "     " << a[一] << "     " << a[二] << "    |" << endl ;
    cout << "|    "<< a[三] << "     " << a[四] << "     " << a[五] << "    |" << endl ;
    cout << "|    "<< a[六] << "     " << a[七] << "     " << a[八] << "    |" << endl ;

}

void Right_shift(string &a, int &b){
    int len = a.size() ;
    int f = 0 ;
    for(int i = 0 ; i < len ; i ++)
    {
        if(a[i] == '0')
        {
            f = i;
            break;
        }
    }
    swap(a[f],a[f+一]);
    cnt ++;
    cout << "**步数" << cnt <<endl ;
    cout << "|    "<< a[0] << "     " << a[一] << "     " << a[二] << "    |" << endl ;
    cout << "|    "<< a[三] << "     " << a[四] << "     " << a[五] << "    |" << endl ;
    cout << "|    "<< a[六] << "     " << a[七] << "     " << a[八] << "    |" << endl ;
}

void Up_shift(string &a, int &b){
    int len = a.size() ;
    int f = 0 ;
    for(int i = 0 ; i < len ; i ++)
    {
        if(a[i] == '0')
        {
            f = i;
            break;
        }
    }
    int xi = f / 三 , yi = f % 三 ;
    int ff = (xi - 一) * 三 + yi ;
    swap(a[ff] , a[f]);
    cnt ++;
    cout << "**步数" << cnt <<endl ;
    cout << "|    "<< a[0] << "     " << a[一] << "     " << a[二] << "    |" << endl ;
    cout << "|    "<< a[三] << "     " << a[四] << "     " << a[五] << "    |" << endl ;
    cout << "|    "<< a[六] << "     " << a[七] << "     " << a[八] << "    |" << endl ;
}

void Down_shift(string &a, int &b){
    int len = a.size() ;
    int f = 0 ;
    for(int i = 0 ; i < len ; i ++)
    {
        if(a[i] == '0')
        {
            f = i;
            break;
        }
    }
    int xi = f / 三 , yi = f % 三 ;
    int ff = (xi + 一) * 三 + yi ;
    swap(a[ff] , a[f]);
    cnt ++;
    cout << "**步数" << cnt <<endl ;
    cout << "|    "<< a[0] << "     " << a[一] << "     " << a[二] << "    |" << endl ;
    cout << "|    "<< a[三] << "     " << a[四] << "     " << a[五] << "    |" << endl ;
    cout << "|    "<< a[六] << "     " << a[七] << "     " << a[八] << "    |" << endl ;
}

int Differences(string str一,string str二){
    int len = str一.size(),count = 0;
    for(int i = 0 ; i < len ; i ++){
        if(str一[i] != str二[i]) count ++ ;
    }
    return count ;
}

int main()
{
    string s, c;
    s = "二八三一六四七0五";
    cout << "请输进始初状况的8数码:" <<endl ;
    cout <<"|    二     八     三    |" << endl ;
    cout <<"|    一     六     四    |" << endl ;
    cout <<"|    七     0     五    |" << endl ;
    cnt_a = Differences(s,ed);
    cout << "差异：" << cnt_a << endl ;
    c = s ;
    cout << endl ;
    cout << "请输进终极状况的8数码:" <<endl ;
    cout <<"|    一     二     三    |" << endl ;
    cout <<"|    八     0     四    |" << endl ;
    cout <<"|    七     六     五    |" << endl ;
    cnt_a = Differences(ed,ed);
    cout << "差异：" << cnt_a << endl ;
    // for (int i = 0; i < 九; i ++ ) cin >> c一, ed += c一;
    cout << endl ;
    if (bfs(s))
    {
        vector<char> arr;
        string t = ed;
        while(t != s)
        {
            arr.push_back(d[p[t]]);  //将挪动圆式存高
            t = pp[t];
        }
        cout << "^^^搜刮成果：^^^"<< endl ;
        cout << "**步数" << "0" <<endl ;
        cout <<"|    二     八     三    |" << endl ;
        cout <<"|    一     六     四    |" << endl ;
        cout <<"|    七     0     五    |" << endl ;
        cout << "差异：" << "五" << endl ;
        cout << endl ;cout << "------------" << endl;
        for (int i = arr.size() - 一; i >= 0; i -- )
        {
            if(arr[i] == 'l')
            {
                Left_shift(s,cnt) ;
                cnt_a = Differences(s,ed);
                cout << "差异：" << cnt_a << endl ;
                cout << endl ;cout << "------------" << endl;
            }
            else if(arr[i] == 'r') {
                Right_shift(s,cnt) ;
                cnt_a = Differences(s,ed);
                cout << "差异：" << cnt_a << endl ;
                cout << endl ;cout << "------------" << endl;
            }
            else if(arr[i] == 'u') {
                Up_shift(s,cnt) ;
                cnt_a = Differences(s,ed);
                cout << "差异：" << cnt_a << endl ;
                cout << endl ;cout << "------------" << endl;
            }
            else if(arr[i] == 'd') {
                Down_shift(s,cnt) ;
                cnt_a = Differences(s,ed);
                cout << "差异：" << cnt_a << endl ;
                cout << endl ;cout << "------------" << endl;
            }
        }

        cout << endl;
    }
    else cout << "unsolvable" << endl;
    return 0;
}

更多文章请关注《万象专栏》