2ms, 120 line, c++ with DLX

• ok, not enough clean...

``````class Solution {
public:
static const int maxn = 15;

int n;

static const int maxCol = maxn * maxn * 4;
static const int maxNode = maxCol + maxn * maxn * maxn * 4;

int ID;
int h, S[maxCol], N[maxCol];
int U[maxNode], D[maxNode], L[maxNode], R[maxNode], C[maxNode], V[maxNode];

char str[maxn*maxn];

bool succ;
void DL(int c, bool uncover = false)
{
if (!uncover) {R[L[c]] = R[c], L[R[c]] = L[c];}
else {R[L[c]] = L[R[c]] = c;}
for (int i = D[c]; i != c; i = D[i]) {
for (int j = R[i]; j != i; j = R[j]) {
if (!uncover) {U[D[j]]=U[j], D[U[j]]=D[j], --S[C[j]];}
else {U[D[j]] = D[U[j]] = j, ++S[C[j]];}
}
}
}
void dfs(int dep)
{
if (succ || R[h] == h) {
succ = true;
return ;
}
int c = R[h];
for (int i = R[h]; i != h; i = R[i]) {
if (!S[i]) return ;
if (S[i] < S[c]) c = i;
}
DL(c);
for (int i = D[c]; i != c; i = D[i]) {
N[c] = V[i];
for (int j = R[i]; j != i; j = R[j]) {
DL(C[j]), N[C[j]] = V[j];
}
dfs(dep+1);
if (succ) return ;
for (int j = L[i]; j != i; j = L[j]) {
DL(C[j], true);
}
}
DL(c, true);
}
{
++S[c];
L[ID] = R[ID] = ID;
U[ID] = U[c], D[ID]  = c;
D[U[ID]] = U[D[ID]] = ID;
V[ID] = v;
C[ID] = c;
return ID++;
}
# define INSR(x, y) do{ L[y]=x,R[y]=R[x];R[L[y]]=L[R[y]]=y; }while(0)
void solveSudoku(std::vector<std::vector<char> > &board) {
n = 9;

char str[maxn*maxn];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
str[i*9+j] = board[i][j];
}
}
str[n*n] = 0;

h = 4*n*n;
for (int c = 0; c <= h; ++c) {
S[c] = 0;
C[c] = D[c] = U[c] = c;
L[c] = (c ? c-1:h), R[c] = (c==h ? 0:c+1);
}
ID = h + 1;
for (int i = 0; str[i]; ++i) {
int x = i / 9, y = i % 9;
int lo = 1, hi = n;
if ('1'<=str[i]&&str[i]<='0'+n) {
lo = hi = str[i] - '0';
V[i] = str[i] - '0';
}
for (int j = lo; j <= hi; ++j) {
INSR(a, b);
INSR(b, c);
INSR(c, d);
}
}
for (int i = R[h]; i != h; i = R[i]) {
if (S[i] == 0) return;
if (S[i] == 1) {
N[i] = V[i];
DL(i);
for (int j = D[i]; j != i; j = D[j]) {
for (int k = R[j]; k != j; k = R[k]) DL(C[k]), N[C[k]] = V[k];
}
}
}
succ = false;
dfs(0);
if (succ) {
for (int i = 0; i < n*n; ++i) {
board[i/9][i%9] = N[i] + '0';
}
}
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.