Sudoku solver with Dancing Links and Knuth's Algorithm X.

sudoku_solver.c

/**
 * @file sudoku_solver.h
 * @brief Dancing Linksで数独をExact Cover ProblemとしてKnuth's Algorithm Xで解くプログラムです．
 * @note 課題の提出からしばらく経ってポインタの理解が深まってから書き直したバージョンです．
 * @author Shota Minami
 */
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/**
 * @struct dancing_links_node
 * @brief Dancing Linksで表現される行列において1と0の関係がこの構造体の存在と非存在の関係に対応します．
 */
typedef struct dancing_links_node dancing_links_node;

/**
 * @struct dancing_links_column
 * @brief dancing_links_nodeを保持するための構造体です．
 */
typedef struct dancing_links_column dancing_links_column;

/**
 * @struct dancing_links
 * @brief dancing_linksの先頭を表す構造体です．
 */
typedef struct dancing_links dancing_links;

struct dancing_links_node {
    char row_label[10];           /** ノードが含まれる行の識別子 */
    dancing_links_column *column; /** ノードが含まれる列の構造体へのポインタ */
    dancing_links_node *left;     /** 左側に隣接しているノードへのポインタ */
    dancing_links_node *right;    /** 右側に隣接しているノードへのポインタ */
    dancing_links_node *up;       /** 上側に隣接しているノードへのポインタ */
    dancing_links_node *down;     /** 下側に隣接しているノードへのポインタ */
};

struct dancing_links_column {
    int size;                 /** 行に含まれる先頭以外のノードの数 */
    char column_label[10];    /** 行の識別子 */
    dancing_links_node *self; /** 行の先頭となるノードへのポインタ */
};

struct dancing_links {
    int row_size;               /** Dancing Linksに含まれる列の数 */
    dancing_links_column *head; /** Dancing Linksの先頭となる行へのポインタ */
};

/**
 * @brief dancing_links_nodeの生成及び初期化を行います．
 * @param row_label 生成するノードが含まれる行の名前
 * @param column ノードが含まれる列の構造体へのポインタ
 * @return 初期化済みのdancing_links_node
 * @note 返される構造体のメモリの開放は手動で行う必要があります．
 */
dancing_links_node *new_dancing_links_node(char *row_label, dancing_links_column *column);

/**
 * @brief dancing_links_columnの生成及び初期化を行います．
 * @param column_label 生成する列の名前
 * @return 初期化済みのdancing_links_column
 * @note 返される構造体のメモリの開放は手動で行う必要があります．
 */
dancing_links_column *new_dancing_links_column(char *column_label);

/**
 * @brief dancing_linksの生成及び初期化を行います．
 * @param column_size dancing_linksが含む行の数
 * @param labels dancing_linksが含む行の識別子の集合
 * @return 初期化済みのdancing_links
 * @note 返される構造体のメモリの開放は手動で行う必要があります．
 */
dancing_links *new_dancing_links(int column_size, char labels[column_size][10]);

/**
 * @brief ノードを目的のノードの右隣へ挿入します．
 * @param base ノードを挿入したい位置の左隣にあるノードへのポインタ
 * @param subject これから挿入するノードへのポインタ
 */
void insert_node_right(dancing_links_node *base, dancing_links_node *subject);

/**
 * @brief ノードを目的のノードの下隣へ挿入します．
 * @param base ノードを挿入したい位置の上隣にあるノードへのポインタ
 * @param subject これから挿入するノードへのポインタ
 */
void insert_node_down(dancing_links_node *base, dancing_links_node *subject);

/**
 * @brief ノードを所属する行から不可視状態にします．
 * @param node 不可視状態にするノードへのポインタ
 */
void cover_node_left_right(dancing_links_node *node);

/**
 * @brief ノードを所属する列から不可視状態にします．
 * @param node 不可視状態にするノードへのポインタ
 * @note 列に含まれるノードの数はこの関数では変更されません．
 */
void cover_node_up_down(dancing_links_node *node);

/**
 * @brief ノードを所属する行で可視状態に戻します．
 * @param node 可視状態に戻すノードへのポインタ
 */
void uncover_node_left_right(dancing_links_node *node);

/**
 * @brief ノードを所属する列で可視状態に戻します．
 * @param node 可視状態に戻すノードへのポインタ
 * @note 列に含まれるノードの数はこの関数では変更されません．
 */
void uncover_node_up_down(dancing_links_node *node);

/**
 * @brief 起点となるノードに含まれる行に存在するノードが含まれる列に存在するノードが含まれる行を不可視状態にします．
 * @param origin 不可視状態にするノード群の起点となるノード．
 * @note この関数によって不可視状態されたノードの数だけ列に含まれるノードの数が減らされます．
 */
void cover(dancing_links_node *origin);

/**
 * @brief 起点となるノードに含まれる行に存在するノードが含まれる列に存在するノードが含まれる行を可視状態に戻します．
 * @param origin 可視状態に戻すノード群の起点となるノード．
 * @note この関数によって可視状態に戻されたノードの数だけ列に含まれるノードの数が増やされます．
 */
void uncover(dancing_links_node *origin);

/**
 * @brief 引数と同じ識別子を持つdancing_links_columnを検索して返します．
 * @param links 識別子の検索対象
 * @param label 検索する識別子
 * @return 検索結果
 * @note 検索しても見つからなかった場合はlinks->headを返します．
 */
dancing_links_column *get_dancing_links_column(dancing_links *links, char *label);

/**
 * @brief 与えられたdancing_linksをExact Cover Problemとして考えたときに解となる行を求めます．
 * @param links Exact Cover Problemとして解く対象となるdancing_links
 * @param stack 解を保存するためのポインタの配列
 * @return 解となる行の識別子の集合
 * @note 解が存在しなかった場合は0，存在した場合は1が返されます．
 */
int apply_algorithm_x(dancing_links *links, dancing_links_node **stack);

/**
 * @brief 行を生成してdancing_linksに挿入します．
 * @param links 行の挿入対象
 * @param label 行の識別子
 * @param num 行に含まれるノードの数
 * @param columns 行に含まれるノードが含まれる列の集合
 */
void create_row(dancing_links *links, char label[10], int num, dancing_links_column *columns[num]);

/**
 * @brief 数独のマスの情報を元に行を生成してdancing_linksに挿入します．
 * @param links 挿入対象
 * @param row 数独の行番号．
 * @param column 数独の列番号．
 * @param number マスに入る数．
 * @note この関数はあくまで行を挿入するためのヘルパ関数であるため，引数の妥当性を確認しません．
 */
void create_sudoku_row(dancing_links* links, int row, int column, int number);

/**
 * @brief dancing_linksを引数を元に数独向けに初期化します．
 * @param board 数独の盤面
 * @note 盤面に含まれる数字以外の文字については無視され，そのマスには何も入れられていないものとして扱われます．
 * @note 返り値のメモリ解放は手動で行う必要があります．
 */
dancing_links *create_dancing_links_for_sudoku(char board[9][10]);

/**
 * @brief 与えられた数独を解きます．
 * @param board 数独の盤面．
 * @return 解が見つかれば1，そうでなければ0
 * @note 解が見つかった場合は引数に対してその解を保存します．
 */
int solve_sudoku(char board[9][10]);

dancing_links_node *new_dancing_links_node(char row_label[10], dancing_links_column *column) {
    dancing_links_node *res = (dancing_links_node *) malloc(sizeof(dancing_links_node));
    strcpy(res->row_label, row_label);
    res->column = column;
    res->left = res->right = res->up = res->down = res;
    return res;
}

dancing_links_column *new_dancing_links_column(char column_label[10]) {
    dancing_links_column *res = (dancing_links_column *) malloc(sizeof(dancing_links_column));
    strcpy(res->column_label, column_label);
    res->size = 0;
    res->self = new_dancing_links_node("CTRL", res);
    return res;
}

dancing_links *new_dancing_links(int column_size, char labels[column_size][10]) {
    dancing_links *res = (dancing_links *) malloc(sizeof(dancing_links));
    res->head = new_dancing_links_column("HEAD");
    res->row_size = 0;
    int i;
    for (i = 0; i < column_size; i++) {
        dancing_links_column *s = new_dancing_links_column(labels[i]);
        insert_node_right(res->head->self->left, s->self);
    }
    return res;
}

void insert_node_right(dancing_links_node *base, dancing_links_node *subject) {
    subject->right = base->right;
    base->right->left = subject;
    base->right = subject;
    subject->left = base;
}

void insert_node_down(dancing_links_node *base, dancing_links_node *subject) {
    subject->down = base->down;
    base->down->up = subject;
    base->down = subject;
    subject->up = base;
}

void cover_node_left_right(dancing_links_node *node) {
    node->left->right = node->right;
    node->right->left = node->left;
}

void cover_node_up_down(dancing_links_node *node) {
    node->up->down = node->down;
    node->down->up = node->up;
}

void uncover_node_left_right(dancing_links_node *node) {
    node->left->right = node;
    node->right->left = node;
}

void uncover_node_up_down(dancing_links_node *node) {
    node->up->down = node;
    node->down->up = node;
}

dancing_links_column *get_dancing_links_column(dancing_links *links, char label[10]) {
    dancing_links_column *c = links->head, *d;
    for (d = c->self->right->column; c != d; d = d->self->right->column) {
        if (strcmp(d->column_label, label) == 0) return d;
    }
    return links->head;
}

void cover(dancing_links_node *origin) {
    dancing_links_node *rnode, *cnode, *rrnode;

    // originが含まれる列を不可視状態にする．
    cover_node_left_right(origin->column->self);
    for (cnode = origin->column->self->down; origin->column->self != cnode; cnode = cnode->down) {
        for (rrnode = cnode->right; cnode != rrnode; rrnode = rrnode->right) {
            cover_node_up_down(rrnode);
            rrnode->column->size--;
        }
    }

    // originが含まれる行を右に移動しつつ，移動先のノードの列にノードを含む行を不可視状態にする．
    for (rnode = origin->right; origin != rnode; rnode = rnode->right) {
        cover_node_left_right(rnode->column->self);
        for (cnode = rnode->column->self->down; rnode->column->self != cnode; cnode = cnode->down) {
            for (rrnode = cnode->right; cnode != rrnode; rrnode = rrnode->right) {
                cover_node_up_down(rrnode);
                rrnode->column->size--;
            }
        }
    }
}

void uncover(dancing_links_node *origin) {
    dancing_links_node *rnode, *cnode, *rrnode;

    // originが含まれる行を左に移動しつつ，移動先のノードの列にノードを含む行を可視状態に戻す．
    for (rnode = origin->left; origin != rnode; rnode = rnode->left) {
        uncover_node_left_right(rnode->column->self);
        for (cnode = rnode->column->self->up; rnode->column->self != cnode; cnode = cnode->up) {
            for (rrnode = cnode->left; cnode != rrnode; rrnode = rrnode->left) {
                uncover_node_up_down(rrnode);
                rrnode->column->size++;
            }
        }
    }

    // originが含まれる行を可視状態に戻す．
    uncover_node_left_right(origin->column->self);
    for (cnode = origin->column->self->up; origin->column->self != cnode; cnode = cnode->up) {
        for (rrnode = cnode->left; cnode != rrnode; rrnode = rrnode->left) {
            uncover_node_up_down(rrnode);
            rrnode->column->size++;
        }
    }
}

void create_row(dancing_links *links, char label[10], int num, dancing_links_column *columns[num]) {
    links->row_size++;
    int i;

    // ノードを生成して先にlinksに挿入する．
    dancing_links_node *row[num];
    for (i = 0; i < num; i++) {
        row[i] = new_dancing_links_node(label, columns[i]);
        columns[i]->size++;
        insert_node_down(columns[i]->self->up, row[i]);
    }

    // ノード同士を結合させて行を生成する．
    for (i = 0; i+1 < num; i++) insert_node_right(row[i], row[i+1]);
}

int apply_algorithm_x(dancing_links *links, dancing_links_node **stack) {
    *stack = NULL;
    dancing_links_node *h, *n, *c;
    h = n = c = links->head->self;
    while ((n = n->right) != h) {
        if (c == h || c->column->size > n->column->size) c = n;
    }
    if (c == h) return 1;

    n = c;
    while ((n = n->down) != c) {
        cover(n);
        *stack = n;
        if (apply_algorithm_x(links, stack + 1)) return 1;
        uncover(n);
    }

    return 0;
}

void create_sudoku_row(dancing_links* links, int row, int column, int number) {
    /*
     * RxCy#z 行x列yに数zを入れる操作に対応．その場合，
     * - Rx#z 行xに数zが入る
     * - Cy#z 列yに数zが入る
     * - Bb#z ブロックb(列x行yのマスが含まれるとする)に数zが入る
     * - RxCy 行x列yに数字が一つ入る
     * の4つの制約を満たすことになるので，これをプログラム的に表現する．
     */
    char row_label[10], column_label[10];
    sprintf(row_label, "R%dC%d#%d", row, column, number);
    dancing_links_column *columns[4];

    sprintf(column_label, "R%d#%d", row, number);
    columns[0] = get_dancing_links_column(links, column_label);

    sprintf(column_label, "C%d#%d", column, number);
    columns[1] = get_dancing_links_column(links, column_label);

    sprintf(column_label, "B%d#%d", (column) / 3 * 3 + (row) / 3, number);
    columns[2] = get_dancing_links_column(links, column_label);

    sprintf(column_label, "R%dC%d", row, column);
    columns[3] = get_dancing_links_column(links, column_label);

    create_row(links, row_label, 4, columns);
}

dancing_links *create_dancing_links_for_sudoku(char board[9][10]) {
    /*
     * Dancing Linksの制約の数について
     * - Rx#z
     * - Cy#z
     * - Bb#z
     * - RxCy
     * それぞれ9x9=81個存在するので合計で324個になる．
     */
    int constraint_size = 324;
    char column_labels[constraint_size][10];
    int i, j, k = 0;
    for (i = 0; i < 9; i++) {
        for (j = 0; j < 9; j++) {
            sprintf(column_labels[k++], "R%d#%d", i, j);
            sprintf(column_labels[k++], "C%d#%d", i, j);
            sprintf(column_labels[k++], "B%d#%d", i, j);
            sprintf(column_labels[k++], "R%dC%d", i, j);
        }
    }

    dancing_links *l = new_dancing_links(constraint_size, column_labels);
    for (i = 0; i < 9; i++) {
        for (j = 0; j < 9; j++) {
            if (isdigit(board[i][j])) create_sudoku_row(l, i, j, board[i][j] - '1');
            else for (k = 0; k < 9; k++) create_sudoku_row(l, i, j, k);
        }
    }
    return l;
}

int solve_sudoku(char board[9][10]) {
    dancing_links *l = create_dancing_links_for_sudoku(board);
    dancing_links_node *res[l->row_size + 1];

    if (!apply_algorithm_x(l, res)) return 0;
    int i;
    for (i = 0; res[i] != NULL; i++) {
        int row, column;
        char number;
        sscanf(res[i]->row_label, "R%dC%d#%c", &row, &column, &number);
        board[row][column] = number + 1;
    }
    return 1;
}

int main() {
    printf("Please input the sudoku board.\n");
    fflush(stdout);
    char board[9][10];
    int i;
    for (i = 0; i < 9; i++) scanf("%9s", board[i]);

    time_t start = clock();
    int code = solve_sudoku(board);
    time_t end = clock();

    if (code) {
        for (i = 0; i < 9; i++) printf("%s\n", board[i]);
    } else {
        printf("No solution found.\n");
    }
    printf("Time: %lf seconds", (double) (end - start) / CLOCKS_PER_SEC);
    return 0;
}

sudoku_solver_original.c

/**
 * @file sudoku_solver.h
 * @brief Dancing Linksで数独をExact Cover ProblemとしてKnuth's Algorithm Xで解くプログラムです．
 * @note ソフトウェア演習で当時提出したときのバージョンです．
 * @author Shota Minami
 */
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>

/**
 * @struct dancing_links_node
 * @brief Dancing Linksで表現される行列において1と0の関係がこの構造体の存在と非存在の関係に対応します．
 */
typedef struct dancing_links_node dancing_links_node;

/**
 * @struct dancing_links_column
 * @brief dancing_links_nodeを保持するための構造体です．
 */
typedef struct dancing_links_column dancing_links_column;

/**
 * @struct dancing_links
 * @brief dancing_linksの先頭を表す構造体です．
 */
typedef struct dancing_links dancing_links;

struct dancing_links_node {
    char row_label[10];           /** ノードが含まれる行の識別子 */
    dancing_links_column *column; /** ノードが含まれる列の構造体へのポインタ */
    dancing_links_node *left;     /** 左側に隣接しているノードへのポインタ */
    dancing_links_node *right;    /** 右側に隣接しているノードへのポインタ */
    dancing_links_node *up;       /** 上側に隣接しているノードへのポインタ */
    dancing_links_node *down;     /** 下側に隣接しているノードへのポインタ */
};

struct dancing_links_column {
    int size;                 /** 行に含まれる先頭以外のノードの数 */
    char column_label[10];    /** 行の識別子 */
    dancing_links_node *self; /** 行の先頭となるノードへのポインタ */
};

struct dancing_links {
    int row_size;               /** Dancing Linksに含まれる列の数 */
    dancing_links_column *head; /** Dancing Linksの先頭となる行へのポインタ */
};

/**
 * @brief dancing_links_nodeの生成及び初期化を行います．
 * @param row_label 生成するノードが含まれる行の名前
 * @param column ノードが含まれる列の構造体へのポインタ
 * @return 初期化済みのdancing_links_node
 * @note 返される構造体のメモリの開放は手動で行う必要があります．
 */
dancing_links_node *new_dancing_links_node(char *row_label, dancing_links_column *column);

/**
 * @brief dancing_links_columnの生成及び初期化を行います．
 * @param column_label 生成する列の名前
 * @return 初期化済みのdancing_links_column
 * @note 返される構造体のメモリの開放は手動で行う必要があります．
 */
dancing_links_column *new_dancing_links_column(char *column_label);

/**
 * @brief dancing_linksの生成及び初期化を行います．
 * @param column_size dancing_linksが含む行の数
 * @param labels dancing_linksが含む行の識別子の集合
 * @return 初期化済みのdancing_links
 * @note 返される構造体のメモリの開放は手動で行う必要があります．
 */
dancing_links *new_dancing_links(int column_size, char labels[column_size][10]);

/**
 * @brief ノードを目的のノードの右隣へ挿入します．
 * @param base ノードを挿入したい位置の左隣にあるノードへのポインタ
 * @param subject これから挿入するノードへのポインタ
 */
void insert_node_right(dancing_links_node *base, dancing_links_node *subject);

/**
 * @brief ノードを目的のノードの下隣へ挿入します．
 * @param base ノードを挿入したい位置の上隣にあるノードへのポインタ
 * @param subject これから挿入するノードへのポインタ
 */
void insert_node_down(dancing_links_node *base, dancing_links_node *subject);

/**
 * @brief ノードを所属する行から不可視状態にします．
 * @param node 不可視状態にするノードへのポインタ
 */
void cover_node_left_right(dancing_links_node *node);

/**
 * @brief ノードを所属する列から不可視状態にします．
 * @param node 不可視状態にするノードへのポインタ
 * @note 列に含まれるノードの数はこの関数では変更されません．
 */
void cover_node_up_down(dancing_links_node *node);

/**
 * @brief ノードを所属する行で可視状態に戻します．
 * @param node 可視状態に戻すノードへのポインタ
 */
void uncover_node_left_right(dancing_links_node *node);

/**
 * @brief ノードを所属する列で可視状態に戻します．
 * @param node 可視状態に戻すノードへのポインタ
 * @note 列に含まれるノードの数はこの関数では変更されません．
 */
void uncover_node_up_down(dancing_links_node *node);

/**
 * @brief 起点となるノードに含まれる行に存在するノードが含まれる列に存在するノードが含まれる行を不可視状態にします．
 * @param origin 不可視状態にするノード群の起点となるノード．
 * @note この関数によって不可視状態されたノードの数だけ列に含まれるノードの数が減らされます．
 */
void cover(dancing_links_node *origin);

/**
 * @brief 起点となるノードに含まれる行に存在するノードが含まれる列に存在するノードが含まれる行を可視状態に戻します．
 * @param origin 可視状態に戻すノード群の起点となるノード．
 * @note この関数によって可視状態に戻されたノードの数だけ列に含まれるノードの数が増やされます．
 */
void uncover(dancing_links_node *origin);

/**
 * @brief 引数と同じ識別子を持つdancing_links_columnを検索して返します．
 * @param links 識別子の検索対象
 * @param label 検索する識別子
 * @return 検索結果
 * @note 検索しても見つからなかった場合はlinks->headを返します．
 */
dancing_links_column *get_dancing_links_column(dancing_links *links, char *label);

/**
 * @brief 引数に渡されたdancing_linksの中から含まれるノードが最も少ないdancing_links_columnを返します．
 * @param links dancing_links_columnの検索対象
 * @return 検索結果
 * @note dancing_links_columnが存在しないまたは全て不可視状態となっている場合はNULLを返します．
 */
dancing_links_column *get_smallest_dancing_links_column(dancing_links *links);

/**
 * @brief 与えられたdancing_linksをExact Cover Problemとして考えたときに解となる行を求めます．
 * @param links Exact Cover Problemとして解く対象となるdancing_links
 * @return 解となる行の識別子の集合
 * @note 解が存在しなかった場合はNULLが返されます．
 * @note 返り値のメモリ解放は手動で行う必要があります．
 */
char **apply_algorithm_x(dancing_links *links);

/**
 * @brief 行を生成してdancing_linksに挿入します．
 * @param links 行の挿入対象
 * @param label 行の識別子
 * @param num 行に含まれるノードの数
 * @param columns 行に含まれるノードが含まれる列の集合
 */
void create_row(dancing_links *links, char label[10], int num, dancing_links_column *columns[num]);

/**
 * @brief 数独のマスの情報を元に行を生成してdancing_linksに挿入します．
 * @param links 挿入対象
 * @param row 数独の行番号．
 * @param column 数独の列番号．
 * @param number マスに入る数．
 * @note この関数はあくまで行を挿入するためのヘルパ関数であるため，引数の妥当性を確認しません．
 */
void create_sudoku_row(dancing_links* links, int row, int column, int number);

/**
 * @brief dancing_linksを引数を元に数独向けに初期化します．
 * @param board 数独の盤面
 * @note 盤面に含まれる数字以外の文字については無視され，そのマスには何も入れられていないものとして扱われます．
 * @note 返り値のメモリ解放は手動で行う必要があります．
 */
dancing_links *create_dancing_links_for_sudoku(char board[9][10]);

/**
 * @brief 与えられた数独を解きます．
 * @param board 数独の盤面．
 * @return 解が見つかれば0，そうでなければ-1
 * @note 解が見つかった場合は引数に対してその解を保存します．
 */
int solve_sudoku(char board[9][10]);

dancing_links_node *new_dancing_links_node(char row_label[10], dancing_links_column *column) {
    dancing_links_node *res = (dancing_links_node *) malloc(sizeof(dancing_links_node));
    strcpy(res->row_label, row_label);
    res->column = column;
    res->left = res->right = res->up = res->down = res;
    return res;
}

dancing_links_column *new_dancing_links_column(char column_label[10]) {
    dancing_links_column *res = (dancing_links_column *) malloc(sizeof(dancing_links_column));
    strcpy(res->column_label, column_label);
    res->size = 0;
    res->self = new_dancing_links_node("CTRL", res);
    return res;
}

dancing_links *new_dancing_links(int column_size, char labels[column_size][10]) {
    dancing_links *res = (dancing_links *) malloc(sizeof(dancing_links));
    res->head = new_dancing_links_column("HEAD");
    res->row_size = 0;
    int i;
    for (i = 0; i < column_size; i++) {
        dancing_links_column *s = new_dancing_links_column(labels[i]);
        insert_node_right(res->head->self->left, s->self);
    }
    return res;
}

void insert_node_right(dancing_links_node *base, dancing_links_node *subject) {
    subject->right = base->right;
    base->right->left = subject;
    base->right = subject;
    subject->left = base;
}

void insert_node_down(dancing_links_node *base, dancing_links_node *subject) {
    subject->down = base->down;
    base->down->up = subject;
    base->down = subject;
    subject->up = base;
}

void cover_node_left_right(dancing_links_node *node) {
    node->left->right = node->right;
    node->right->left = node->left;
}

void cover_node_up_down(dancing_links_node *node) {
    node->up->down = node->down;
    node->down->up = node->up;
}

void uncover_node_left_right(dancing_links_node *node) {
    node->left->right = node;
    node->right->left = node;
}

void uncover_node_up_down(dancing_links_node *node) {
    node->up->down = node;
    node->down->up = node;
}

dancing_links_column *get_dancing_links_column(dancing_links *links, char label[10]) {
    dancing_links_column *c = links->head, *d;
    for (d = c->self->right->column; c != d; d = d->self->right->column) {
        if (strcmp(d->column_label, label) == 0) return d;
    }
    return links->head;
}

dancing_links_column *get_smallest_dancing_links_column(dancing_links *links) {
    dancing_links_node *head = links->head->self, *res = NULL, *n;
    int minsize = 1e9;
    for (n = head->right; head != n; n = n->right) {
        if (minsize < n->column->size) continue;
        minsize = n->column->size;
        res = n;
    }
    return res == NULL ? NULL : res->column;
}

void cover(dancing_links_node *origin) {
    dancing_links_node *rnode, *cnode, *rrnode;

    // originが含まれる列を不可視状態にする．
    cover_node_left_right(origin->column->self);
    for (cnode = origin->column->self->down; origin->column->self != cnode; cnode = cnode->down) {
        for (rrnode = cnode->right; cnode != rrnode; rrnode = rrnode->right) {
            cover_node_up_down(rrnode);
            rrnode->column->size--;
        }
    }

    // originが含まれる行を右に移動しつつ，移動先のノードの列にノードを含む行を不可視状態にする．
    for (rnode = origin->right; origin != rnode; rnode = rnode->right) {
        cover_node_left_right(rnode->column->self);
        for (cnode = rnode->column->self->down; rnode->column->self != cnode; cnode = cnode->down) {
            for (rrnode = cnode->right; cnode != rrnode; rrnode = rrnode->right) {
                cover_node_up_down(rrnode);
                rrnode->column->size--;
            }
        }
    }
}

void uncover(dancing_links_node *origin) {
    dancing_links_node *rnode, *cnode, *rrnode;

    // originが含まれる行を左に移動しつつ，移動先のノードの列にノードを含む行を可視状態に戻す．
    for (rnode = origin->left; origin != rnode; rnode = rnode->left) {
        uncover_node_left_right(rnode->column->self);
        for (cnode = rnode->column->self->up; rnode->column->self != cnode; cnode = cnode->up) {
            for (rrnode = cnode->left; cnode != rrnode; rrnode = rrnode->left) {
                uncover_node_up_down(rrnode);
                rrnode->column->size++;
            }
        }
    }

    // originが含まれる行を可視状態に戻す．
    uncover_node_left_right(origin->column->self);
    for (cnode = origin->column->self->up; origin->column->self != cnode; cnode = cnode->up) {
        for (rrnode = cnode->left; cnode != rrnode; rrnode = rrnode->left) {
            uncover_node_up_down(rrnode);
            rrnode->column->size++;
        }
    }
}

void create_row(dancing_links *links, char label[10], int num, dancing_links_column *columns[num]) {
    links->row_size++;
    int i;

    // ノードを生成して先にlinksに挿入する．
    dancing_links_node *row[num];
    for (i = 0; i < num; i++) {
        row[i] = new_dancing_links_node(label, columns[i]);
        columns[i]->size++;
        insert_node_down(columns[i]->self->up, row[i]);
    }

    // ノード同士を結合させて行を生成する．
    for (i = 0; i+1 < num; i++) insert_node_right(row[i], row[i+1]);
}

char **apply_algorithm_x(dancing_links *links) {
    int i;
    dancing_links_node *node_stack[links->row_size + 1]; /** 現在解として採用しているノードの集合 */
    for (i = 0; i <= links->row_size; i++) node_stack[i] = NULL;
    int stack_index = 0; /** node_stackの末尾のインデックス */

    // 見かけは複雑だが行っているのは単純な深さ優先探索
    while (1) {
        // stack_indexが-1になるのは解が存在しないときなのでNULLを返す．
        if (stack_index == -1) return NULL;

        if (node_stack[stack_index] == NULL) {
            // 次の候補となるノードが含まれる行を得る
            dancing_links_column *c = get_smallest_dancing_links_column(links);
            if (c == NULL) {
                // dancing_linksが全て不可視状態となっているので
                // 現在node_stackが保持しているノードが解である．
                // よって解となる行の集合を返す．
                char **res = (char **) malloc((stack_index + 1) * sizeof(char *));
                for (i = 0; i < stack_index; i++) {
                    res[i] = (char *) malloc(10 * sizeof(char));
                    strcpy(res[i], node_stack[i]->row_label);
                }
                res[stack_index] = NULL;
                return res;
            } else if (c->size == 0) {
                // 矛盾が生じているので解を一つ前に差し戻す．
                stack_index--;
            } else {
                // cの最初のノードを解の候補に入れる．
                node_stack[stack_index] = c->self->down;
                cover(c->self->down);
                stack_index++;
            }
        } else {
            // 一つ前で採用していたノードが解ではなかったので可視状態に戻す．
            uncover(node_stack[stack_index]);
            if (node_stack[stack_index]->down == node_stack[stack_index]->column->self) {
                // 現在見ている列のノードが全て解に含まれないので
                // 一つ前に採用した列にまで処理を戻す．
                node_stack[stack_index] = NULL;
                stack_index--;
            } else {
                // 最後に採用したノードが解に含まれないので，その
                // ノードと同じ列の次のノードを解の候補に入れる．
                node_stack[stack_index] = node_stack[stack_index]->down;
                cover(node_stack[stack_index]);
                stack_index++;
            }
        }
    }
}


void create_sudoku_row(dancing_links* links, int row, int column, int number) {
    /*
     * RxCy#z 行x列yに数zを入れる操作に対応．その場合，
     * - Rx#z 行xに数zが入る
     * - Cy#z 列yに数zが入る
     * - Bb#z ブロックb(列x行yのマスが含まれるとする)に数zが入る
     * - RxCy 行x列yに数字が一つ入る
     * の4つの制約を満たすことになるので，これをプログラム的に表現する．
     */
    char row_label[10], column_label[10];
    sprintf(row_label, "R%dC%d#%d", row, column, number);
    dancing_links_column *columns[4];

    sprintf(column_label, "R%d#%d", row, number);
    columns[0] = get_dancing_links_column(links, column_label);

    sprintf(column_label, "C%d#%d", column, number);
    columns[1] = get_dancing_links_column(links, column_label);

    sprintf(column_label, "B%d#%d", (column-1)/3*3 + (row-1)/3 + 1, number);
    columns[2] = get_dancing_links_column(links, column_label);

    sprintf(column_label, "R%dC%d", row, column);
    columns[3] = get_dancing_links_column(links, column_label);

    create_row(links, row_label, 4, columns);
}

dancing_links *create_dancing_links_for_sudoku(char board[9][10]) {
    /*
     * Dancing Linksの制約の数について
     * - Rx#z
     * - Cy#z
     * - Bb#z
     * - RxCy
     * それぞれ9x9=81個存在するので合計で324個になる．
     */
    int constraint_size = 324;
    char column_labels[constraint_size][10];
    int i, j, k = 0;
    for (i = 1; i <= 9; i++) {
        for (j = 1; j <= 9; j++) {
            sprintf(column_labels[k++], "R%d#%d", i, j);
            sprintf(column_labels[k++], "C%d#%d", i, j);
            sprintf(column_labels[k++], "B%d#%d", i, j);
            sprintf(column_labels[k++], "R%dC%d", i, j);
        }
    }

    dancing_links *l = new_dancing_links(constraint_size, column_labels);
    for (i = 1; i <= 9; i++) {
        for (j = 1; j <= 9; j++) {
            if (isdigit(board[i-1][j-1])) create_sudoku_row(l, i, j, board[i-1][j-1] - '0');
            else for (k = 1; k <= 9; k++) create_sudoku_row(l, i, j, k);
        }
    }
    return l;
}

int solve_sudoku(char board[9][10]) {
    dancing_links *l = create_dancing_links_for_sudoku(board);
    char **ans = apply_algorithm_x(l);
    if (ans == NULL) return -1;
    int i;
    for (i = 0; ans[i] != NULL; i++) {
        int row, column;
        char number;
        sscanf(ans[i], "R%dC%d#%c", &row, &column, &number);
        board[row-1][column-1] = number;
    }
    return 0;
}

int main() {
    printf("Please input the sudoku board.\n");
    fflush(stdout);
    char board[9][10];
    int i;
    for (i = 0; i < 9; i++) {
        char tmp[11];
        scanf("%10s", tmp);
        tmp[10] = '\0';
        if (strlen(tmp) != 9) {
            printf("The length of the input string is needed to be 9.");
            return -1;
        }
        strcpy(board[i], tmp);
    }

    struct timeval start, end;
    gettimeofday(&start, NULL);
    int code = solve_sudoku(board);
    gettimeofday(&end, NULL);

    if (code == 0) {
        for (i = 0; i < 9; i++) printf("%s\n", board[i]);
    } else {
        printf("No solution found.\n");
    }
    printf("Time: %lf milliseconds", (end.tv_usec - start.tv_usec) / 1000.0);
    return 0;
}