[상단] Muduo를 사용하여 수독과 8수 코드 문제 해결 서버 완성

Muduo 네트워크 라이브러리의 원본 코드를 분석한 후에 우리는 효율적인 수독과 8수 코드 문제 풀이 서버를 완성하려고 한다.
먼저 왜 이 두 문제를 선택해야 하는지 말씀해 주시겠어요?수독 문제는 진석 선생님이 좋아하시는 문제로 무두 인터넷 라이브러리에서 여러 차례 언급되고 예시가 있다.8수 코드 문제는 내가 매우 좋아하는 문제이기 때문에 여기서 수독과 8디지털 문제를 해결하는 효율적인 서버 프로그램을 종합적으로 완성한다.
이렇게 간단해 보이는 서비스 프로그램을 작성하는 기술적 함량은 이른바 컨트롤러 축적형 개발보다 훨씬 높다. 비록 muduo 네트워크 라이브러리가 우리가 네트워크 이벤트를 처리하는 데 도움을 주지만 우리는 setConnection Callback () 과 setMessage Callback () 사건에 주목하기만 하면 된다. 그러나 이 두 가지 문제는 모두 cpu 밀집형 작업이기 때문에 효율적인 알고리즘이 필요하고 다중 핵 가속 (Thread Pool) 을 사용해야 한다.우리는 Dancing Links 알고리즘을 이용하여 수별 문제를 풀고 A* 알고리즘 + 콘토를 사용하여 8수 코드 문제를 풀고 조작 경로를 출력합니다.알고리즘은 내가 직접 작성하여 실현하는 동시에 온라인judge의 테스트 데이터(hdu1043,poj3074)를 통해 정확성이 어느 정도 보장된다.
이 안에 언급된 알고리즘에 대해 더 이상 설명하지 않겠습니다. 알고리즘의 기초가 약한 독자들은 아래의 참고 링크를 보십시오.
Dancing Links 알고리즘:http://wenku.baidu.com/link?url=ENP5vkf6Ws54iuVhEFFvnkLrgWuv_ukhVnfBUfszEifQjRzX-hXJa-laCcL6Bkos-X1SDV3uyV0vXSf2j95LrW_p_FYqkDW2Zk2LmzLCxQ3
A* 알고리즘:http://www.cnblogs.com/luxiaoxun/archive/2012/08/05/2624115.html
콘토 전개:http://baike.baidu.com/link?url=kBFlr76wrl2UsxzU_pNNJpCtIvOa8LSjM5_b6DI6XBhekB00ax8fR7YbkTQhbzt-dNK4v90VrlH1kujTqZazB_
유일무이하다
입력한 형식은 81개의 숫자로 바둑판의 왼쪽에서 오른쪽, 위에서 아래로 배열되며, 앞에는 다음과 같은 ":"로 구분된 번호와 로고가 붙을 수 있습니다.
00000000000.....00000 또는 a:00000000000...00000, 답안 문자열 응답 없음, No solution 응답 없음
독립 실행형 알고리즘의 핵심 코드 클래스는 다음과 같습니다.

struct Node;
typedef Node Column;
struct Node
{
    Node* left;
    Node* right;
    Node* up;
    Node* down;
    Column* col;
    int name;
    int size;
};

const int kMaxNodes = 1 + 81*4 + 9*9*9*4;
// const int kMaxColumns = 400;
const int kRow = 100, kCol = 200, kBox = 300;
extern const char kNoSolution[] = "NoSolution";

class SudokuSolver
{
 public:
    SudokuSolver(int board[kCells])
      : inout_(board),
        cur_node_(0)
    {
        stack_.reserve(100);

        root_ = new_column();
        root_->left = root_->right = root_;
        memset(columns_, 0, sizeof(columns_));

        bool rows[kCells][10] = { {false} };
        bool cols[kCells][10] = { {false} };
        bool boxes[kCells][10] = { {false} };

        for (int i = 0; i < kCells; ++i) {
            int row = i / 9;
            int col = i % 9;
            int box = row/3*3 + col/3;
            int val = inout_[i];
            rows[row][val] = true;
            cols[col][val] = true;
            boxes[box][val] = true;
        }

        for (int i = 0; i < kCells; ++i) {
            if (inout_[i] == 0) {
                append_column(i);
            }
        }

        for (int i = 0; i < 9; ++i) {
            for (int v = 1; v < 10; ++v) {
                if (!rows[i][v])
                    append_column(get_row_col(i, v));
                if (!cols[i][v])
                    append_column(get_col_col(i, v));
                if (!boxes[i][v])
                    append_column(get_box_col(i, v));
            }
        }

        for (int i = 0; i < kCells; ++i) {
            if (inout_[i] == 0) {
                int row = i / 9;
                int col = i % 9;
                int box = row/3*3 + col/3;
                //int val = inout[i];
                for (int v = 1; v < 10; ++v) {
                    if (!(rows[row][v] || cols[col][v] || boxes[box][v])) {
                        Node* n0 = new_row(i);
                        Node* nr = new_row(get_row_col(row, v));
                        Node* nc = new_row(get_col_col(col, v));
                        Node* nb = new_row(get_box_col(box, v));
                        put_left(n0, nr);
                        put_left(n0, nc);
                        put_left(n0, nb);
                    }
                }
            }
        }
    }

    bool solve()
    {
        if (root_->left == root_) {
            for (size_t i = 0; i < stack_.size(); ++i) {
                Node* n = stack_[i];
                int cell = -1;
                int val = -1;
                while (cell == -1 || val == -1) {
                    if (n->name < 100)
                        cell = n->name;
                    else
                        val = n->name % 10;
                    n = n->right;
                }

                //assert(cell != -1 && val != -1);
                inout_[cell] = val;
            }
            return true;
        }

        Column* const col = get_min_column();
        cover(col);
        for (Node* row = col->down; row != col; row = row->down) {
            stack_.push_back(row);
            for (Node* j = row->right; j != row; j = j->right) {
                cover(j->col);
            }
            if (solve()) {
                return true;
            }
            stack_.pop_back();
            for (Node* j = row->left; j != row; j = j->left) {
                uncover(j->col);
            }
        }
        uncover(col);
        return false;
    }

 private:

    Column* root_;
    int*    inout_;
    Column* columns_[400];
    std::vector<Node*> stack_;
    Node    nodes_[kMaxNodes];
    int     cur_node_;

    Column* new_column(int n = 0)
    {
        assert(cur_node_ < kMaxNodes);
        Column* c = &nodes_[cur_node_++];
        memset(c, 0, sizeof(Column));
        c->left = c;
        c->right = c;
        c->up = c;
        c->down = c;
        c->col = c;
        c->name = n;
        return c;
    }

    void append_column(int n)
    {
        assert(columns_[n] == NULL);

        Column* c = new_column(n);
        put_left(root_, c);
        columns_[n] = c;
    }

    Node* new_row(int col)
    {
        assert(columns_[col] != NULL);
        assert(cur_node_ < kMaxNodes);

        Node* r = &nodes_[cur_node_++];

        //Node* r = new Node;
        memset(r, 0, sizeof(Node));
        r->left = r;
        r->right = r;
        r->up = r;
        r->down = r;
        r->name = col;
        r->col = columns_[col];
        put_up(r->col, r);
        return r;
    }

    int get_row_col(int row, int val)
    {
        return kRow+row*10+val;
    }

    int get_col_col(int col, int val)
    {
        return kCol+col*10+val;
    }

    int get_box_col(int box, int val)
    {
        return kBox+box*10+val;
    }

    Column* get_min_column()
    {
        Column* c = root_->right;
        int min_size = c->size;
        if (min_size > 1) {
            for (Column* cc = c->right; cc != root_; cc = cc->right) {
                if (min_size > cc->size) {
                    c = cc;
                    min_size = cc->size;
                    if (min_size <= 1)
                        break;
                }
            }
        }
        return c;
    }

    void cover(Column* c)
    {
        c->right->left = c->left;
        c->left->right = c->right;
        for (Node* row = c->down; row != c; row = row->down) {
            for (Node* j = row->right; j != row; j = j->right) {
                j->down->up = j->up;
                j->up->down = j->down;
                j->col->size--;
            }
        }
    }

    void uncover(Column* c)
    {
        for (Node* row = c->up; row != c; row = row->up) {
            for (Node* j = row->left; j != row; j = j->left) {
                j->col->size++;
                j->down->up = j;
                j->up->down = j;
            }
        }
        c->right->left = c;
        c->left->right = c;
    }

    void put_left(Column* old, Column* nnew)
    {
        nnew->left = old->left;
        nnew->right = old;
        old->left->right = nnew;
        old->left = nnew;
    }

    void put_up(Column* old, Node* nnew)
    {
        nnew->up = old->up;
        nnew->down = old;
        old->up->down = nnew;
        old->up = nnew;
        old->size++;
        nnew->col = old;
    }
};

string solveSudoku(const StringPiece& puzzle)
{
  assert(puzzle.size() == kCells);

  string result = kNoSolution;

  int board[kCells] = { 0 };
  bool valid = true;
  for (int i = 0; i < kCells; ++i)
  {
    board[i] = puzzle[i] - '0';
    valid = valid && (0 <= board[i] && board[i] <= 9);
  }

  if (valid)
  {
    SudokuSolver s(board);
    if (s.solve())
    {
      result.clear();
      result.resize(kCells);
      for (int i = 0; i < kCells; ++i)
      {
        result[i] = static_cast<char>(board[i] + '0');
      }
    }
  }
  return result;
}

(2)8수
입력한 데이터는 9자로 구성된 문자열로 현재 공백은 x로 표시됩니다.해제 반환 작업 문자열 l(왼쪽), r(오른쪽), u(위), d(아래) 즉 최소 단계 이동 경로입니다. 해제 없이 "No solution"으로 돌아갑니다.
여기서 말하자면 A* 알고리즘을 사용하여 계발식 검색을 하는 것 외에 콘토 전개를 다시 사용하면 공간을 효과적으로 절약하고 효율을 높일 수 있다(int 기록 상태만 사용하면 된다).
8수 코드 알고리즘 핵심 코드:

struct Node
{
    int maze[3][3];
    int fun_h,fun_g;
    int pos_x,pos_y;
    int Hash;
    bool operator<(const Node nt)const{
        return fun_h+fun_g>nt.fun_h+nt.fun_g;
    }

    bool check()
    {
        if(pos_x>=0 && pos_x<3 && pos_y>=0 && pos_y<3)
            return true;
        return false;
    }
};

const int MAXNUM=370000;
int HASH[9]={1,1,2,6,24,120,720,5040,40320};//0!~8!
int dest=46233;
int vis[MAXNUM];
int pre[MAXNUM];
int way[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//4 ways

class EightSolver
{
    public:
        EightSolver(string s)
        {
            memset(vis,-1,sizeof(vis));
            memset(pre,-1,sizeof(pre));
            int k=0;
            for(int i=0;i<3;i++)
                for(int j=0;j<3;j++)
                {
                    if((s[k]<='9'&&s[k]>='0')||s[k]=='x')
                    {
                        if(s[k]=='x')
                        {
                            begNode.maze[i][j]=0;
                            begNode.pos_x=i;
                            begNode.pos_y=j;
                        }
                        else
                            begNode.maze[i][j]=s[k]-'0';
                    }

                    k++;
                }
            begNode.Hash=getHash(begNode);
            begNode.fun_g=0;
            begNode.fun_h=getH(begNode);
            vis[begNode.Hash]=1;

        }
        string getAns()
        {
            string ans="";
            int nxt=dest;
            while(pre[nxt]!=-1)
            {
                switch(vis[nxt])
                {
                    case 0:ans+='r';break;
                    case 1:ans+='l';break;
                    case 2:ans+='d';break;
                    case 3:ans+='u';break;
                }
                nxt=pre[nxt];
            }
            reverse(ans.begin(),ans.end());
            return ans;
        }
        bool isOK()
        {
            std::vector<int> v;
            for(int i=0;i<3;i++)
                for(int j=0;j<3;j++)
                    v.push_back(begNode.maze[i][j]);
            int sum=0;
            for(int i=0;i<9;i++)
                for(int j=i+1;j<9;j++)
                    if(v[j]&&v[i]&&v[i]>v[j])
                        sum++;
            return !(sum&1);

        }
        void aStar()
        {
            if(begNode.Hash==dest)
                return ;
            std::priority_queue<Node> que;
            que.push(begNode);
            while(!que.empty())
            {
                Node u=que.top();
                que.pop();
                for(int i=0;i<4;i++)
                {
                    Node v=u;
                    v.pos_x+=way[i][0];
                    v.pos_y+=way[i][1];
                    if(v.check())
                    {
                        std::swap(v.maze[v.pos_x][v.pos_y],v.maze[u.pos_x][u.pos_y]);
                        v.Hash=getHash(v);
                        if(vis[v.Hash]==-1)
                        {
                            vis[v.Hash]=i;
                            v.fun_g++;
                            pre[v.Hash]=u.Hash;
                            v.fun_h=getH(v);
                            que.push(v);
                        }
                        if(v.Hash==dest)
                            return ;
                    }
                }
            }

        }
    private:
        Node begNode;
        int getHash(Node &tmp)
        {
            std::vector<int> v;
            for(int i=0;i<3;i++)
                for(int j=0;j<3;j++)
                    v.push_back(tmp.maze[i][j]);
            int res=0;
            for(int i=0;i<9;i++)
            {
                int k=0;
                for(int j=i+1;j<9;j++)
                    if(v[j]<v[i])
                        k++;
                res+=HASH[8-i]*k;
            }
            return res;
        }


        int getH(Node &tmp)
        {
            int ans=0;
            for(int i=0;i<3;i++)
                for(int j=0;j<3;j++)
                    if(tmp.maze[i][j])
                        ans+=abs(i-(tmp.maze[i][j]-1)/3)+abs(j-(tmp.maze[i][j]-1)%3);
            return ans;
        }
};


string solveEight(const StringPiece& puzzle)
{
    string board="";
    string constStr="No solution";
    for(int i=0;i<puzzle.size();i++)
    {
        board+=puzzle[i];
    }
    EightSolver s(board);
    if(!s.isOK())
        return constStr;
    else
    {
       s.aStar();
       return s.getAns();
    }

}

마지막으로 이 두 서비스는 융합된 것이다. 서버를 연 후telnet 명령으로 접근하면 요구를 충족시키는 문자열은 자동으로 결과를 분류하고 해석한다. 효과도는 다음과 같다(Linux 아래).
muduo 네트워크 라이브러리를 바탕으로 이루어진 것이기 때문에 효율적이고 신뢰할 수 있는 병렬 접근을 쉽게 실현할 수 있습니다.
프로젝트의 모든 소스는 Github에 관리됩니다(https://github.com/Tachone/sukuEight), 관심 있는 독자는 계속 보완할 수 있을 뿐만 아니라 전단의 학생들이 웹 인터페이스를 만들어 이 해답 프로그램을 더욱 인성화시키는 것을 강력히 환영합니다.