37. sudoku solver

#include <iostream>
#include <vector>
#include <string.h>

const int MAX_SIZE = 10;
struct Node {
  int first;
  int second;
  Node(int i, int j) {
    first = i;
    second = j;
  }
  Node() {
    first = 0;
    second = 0;
  }
};

void show(int (*graph)[10]) {
  for (int i = 0; i < 9; ++i) {
    if (i % 3 == 0) {
      std::cout << std::endl;
    }
    for (int j = 0; j < 9; ++j) {
      if (j % 3 == 0) {
        std::cout << "  ";
      }
      if (graph[i][j] != 0) {
        std::cout << graph[i][j] << " ";
      } else {
        std::cout << "  ";
      }
    }
    std::cout << std::endl;
  }
}

class Solution {
public:
  void solveSudoku(std::vector<std::vector<char> >& board) {
    memset(hang, false, sizeof(hang));
    memset(lie, false, sizeof(lie));
    memset(jiu, false, sizeof(jiu));
    memset(G, 0, sizeof(G));
    noSize = 0;
    for (unsigned i = 0; i < board.size(); ++i) {
      for (unsigned j = 0; j < board[i].size(); ++j) {
        if (board[i][j] == '.') {
          noNumber[noSize++] = Node(i, j);
        } else {
          G[i][j] = board[i][j] - '0';
          char c = board[i][j];
          hang[i][c - '1'] = true;
          lie[j][c - '1'] = true;
          jiu[i/3*3+j/3][c - '1'] = true;
        }
      }
    }
    flag = false;
    dfs(0, noSize);
    for (unsigned i = 0; i < 9; ++i) {
      for (unsigned j = 0; j < 9; ++j) {
        board[i][j] = G[i][j] + '0';
      }
    }
  }
  void dfs(int j, int n) {
    if (j == n) {
      flag = true;
      //show(G);
    }
    if (flag) {
      return ;
    }
    for (int i = 0; i < 9; ++i) {
      if (flag) {
        break;
      }
      int x = noNumber[j].first;
      int y = noNumber[j].second;
      if (!hang[x][i] && !lie[y][i] && !jiu[x/3*3+y/3][i]) {
        hang[x][i] = true;
        lie[y][i] = true;
        jiu[x/3*3+y/3][i] = true;
        G[x][y] = i + 1;
        dfs(j+1, n);
        hang[x][i] = false;
        lie[y][i] = false;
        jiu[x/3*3+y/3][i] = false;
      }
    }
  }
private:
  bool hang[MAX_SIZE][MAX_SIZE];
  bool lie[MAX_SIZE][MAX_SIZE];
  bool jiu[MAX_SIZE][MAX_SIZE];
  Node noNumber[100];
  int noSize;
  bool flag;
  int G[MAX_SIZE][MAX_SIZE];
};