使用Muduo完成數獨和八數碼問題求解服務器

在剖析完Muduo網絡庫源碼之後，我們試著完成一個高效的數獨和八數碼問題求解服務器。

先說說為什麼要選擇這兩個問題？數獨問題一直是陳碩老師很喜歡的問題，在muduo網絡庫中多次提到並有示例。八數碼問題是我很喜歡的問題，所以在此綜合完成求解數獨和八數碼問題的高效服務端程序。

編寫這樣一個看似簡單的服務程序的技術含量遠高於所謂的控件堆砌型開發，雖然有muduo網絡庫幫助我們處理網絡事件，我們只需要關注setConnectionCallback() 和setMessageCallback() 事件，但是這兩個問題都是cpu密集型任務，需要高效的算法，同時使用多核加速（ThreadPool）。我們采用Dancing Links算法求解數獨問題，使用A* 算法+康托展開 求解八數碼問題並打印操作路徑。算法由我自己編寫實現，同時通過online judge的測試數據（hdu 1043 ,poj 3074），正確性有一定保證。

（一）數獨

輸入的格式為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 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(board[i] + '0');
      }
    }
  }
  return result;
}

輸入的數據為9個字符組成的字符串，當前空格用x表示。有解返回操作字符串 l(左)、r(右)、u(上)、d(下)即最少步數移動路徑，無解返回“No solution”。

這裡要講一下，除了使用A*算法進行啟發式搜索之外，判重使用康托展開，可以有效的節約空間和提升效率（僅使用int記錄狀態即可）。

八數碼算法核心代碼：

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 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 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 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]
 



最後，這兩個服務是融合的，開啟服務器後，使用telnet命令訪問，滿足要求的字符串便會自動分類解析返回結果，效果圖如下（Linux下）：
由於是基於muduo網絡庫實現的，所以可以很輕松的實現高效可靠的並發訪問~。