プログラム

/******************************************************************************
ナンスケ
******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define OK 0
#define NG -1
#define NN 1000
#define OFF 0
#define ON 1
#define YOKO 0
#define TATE 1
#define NXY 100 /* 盤の最大の大きさ */
#define NS 1000 /* 数列の最大数 */
typedef struct {
    int x;
    int y;
    int len;
    int hoko;
} DEF;
typedef struct {
    int len;
    char r1[NXY];
} NUM;
int ban[NXY][NXY];  /* 盤 黒=OFF 白=ON */
int ban2[NXY][NXY]; /* 盤 解(１〜９） */
int ban3[NXY][NXY]; /* 盤 そこを通った数列の数 初期値＝０ */
NUM num[NS];
int f1[NS];
int nNum = 0;
DEF def[NS];
int nDef = 0;
int nx = -1 , ny = 0; /* 盤の大きさ */
/******************************************************************************
機能：初期化
引数：
戻り値：
******************************************************************************/
int init(char *filename)
{
    FILE *fpi;
    char buf[NN];
    char *status;
    int x , y;
    int len;
    int i;
    for(y = 0 ; y < NXY ; y++) {
        for(x = 0 ; x < NXY ; x++) ban[y][x] = OFF;
    }
    fpi = fopen(filename , "r");
    if(fpi == NULL) {
        fprintf(stderr , "%sをオープンできません\n" , filename);
        return(NG);
    }
    status = fgets(buf , NN , fpi);
    len = strlen(buf) - 1;
    while(len > 0) {
        for(x = 0 ; x < len; x++) {
            if(buf[x] == '1') ban[ny][x] = ON;
            else ban[ny][x] = OFF;
        }
        if(len > nx) nx = len;
        ny++;
        status = fgets(buf , NN , fpi);
        len = strlen(buf) - 1;
    }
    status = fgets(buf , NN , fpi);
    while(status != NULL) {
        len = strlen(buf) - 1;
        if(len > 1) {
            num[nNum].len = len;
            for(x = 0 ; x < len ; x++) {
                num[nNum].r1[x] = buf[x] - '0';
            }
            nNum++;
        }
        status = fgets(buf , NN , fpi);
    }
    fclose(fpi);
    for(y = 0 ; y < ny ; y++) {
        for(x = 0 ; x < nx ; x++) {
            if(ban[y][x] == 0) continue;
            if((x == 0 || (x > 0 && ban[y][x - 1] == OFF)) &&
                ban[y][x + 1] == ON) {
                for(i = 2 ; i < NXY ; i++) {
                    if(ban[y][x + i] == OFF) {
                        def[nDef].x = x;
                        def[nDef].y = y;
                        def[nDef].hoko = YOKO;
                        def[nDef++].len = i;
                        break;
                    }
                }
            }
            if((y == 0 || (y > 0 && ban[y - 1][x] == OFF)) &&
                ban[y + 1][x] == ON) {
                for(i = 2 ; i < NXY ; i++) {
                    if(ban[y + i][x] == OFF) {
                        def[nDef].x = x;
                        def[nDef].y = y;
                        def[nDef].hoko = TATE;
                        def[nDef++].len = i;
                        break;
                    }
                }
            }
        }
    }
    for(x = 0 ; x < nNum ; x++) f1[x] = OFF;
    for(y = 0 ; y < NXY ; y++) {
        for(x = 0 ; x < NXY ; x++) ban3[y][x] = 0;
    }
    return(OK);
}
/******************************************************************************
機能：解答を表示する
引数：なし
戻り値：なし
******************************************************************************/
void disp(void)
{
    int x , y;
    for(y = 0 ; y < ny ; y++) {
        for(x = 0 ; x < nx ; x++) {
            if(ban[y][x] == OFF) printf(" ");
            else printf("%d" , ban2[y][x]);
        }
        printf("\n");
    }
}
/******************************************************************************
機能：再帰関数
引数：
戻り値：なし
******************************************************************************/
void proc(int n)
{
    int x , y , xhoko , yhoko , len;
    int i , j;
    if(n == nDef) {
        disp();
        return;
    }
    x = def[n].x;
    y = def[n].y;
    xhoko = TATE - def[n].hoko;
    yhoko = def[n].hoko;
    len = def[n].len;
    for(i = 0 ; i < nNum ; i++) {
        if(num[i].len != len) continue;
        if(f1[i] == ON) continue;
        for(j = 0 ; j < len ; j++) {
            if(ban3[y + j * yhoko][x + j * xhoko] != 0 &&
                ban2[y + j * yhoko][x + j * xhoko] != num[i].r1[j]) break;
        }
        if(j != len) continue;
        for(j = 0 ; j < len ; j++) {
            ban2[y + j * yhoko][x + j * xhoko] = num[i].r1[j];
            ban3[y + j * yhoko][x + j * xhoko]++;
        }
        f1[i] = ON;
        proc(n + 1);
        f1[i] = OFF;
        for(j = 0 ; j < len ; j++) {
            ban3[y + j * yhoko][x + j * xhoko]--;
        }
    }
}
/******************************************************************************
機能：メイン
引数：コマンドラインの引数
戻り値：
******************************************************************************/
int main(int argc , char **argv)
{
    if(argc != 2) {
        fprintf(stderr , "使用方法 : %s ファイル\n" , argv[0]);
        return(EXIT_FAILURE);
    }
    if(init(argv[1]) == NG) {
        return(EXIT_FAILURE);
    }
    proc(0);
    return(EXIT_SUCCESS);
}

入力データ

 1111 11111
1 1 111  1
11111 11111
1  1 1 1 1
1111 11111
  1  1  1
 11111 1111
 1 1 1 1  1
11111 11111
 1  111 1 1
11111 1111

122
144
211
244
284
364
416
434
441
621
818
826
842
861
4126
4416
4686
8246
8624
8824
11868
12624
21868
22864
41868
64481
64681
66212
68181
68281
86416