ナンプレ（数独）問題作成プログラム　その８

Locked Candidate

Locked Candidate というのは列または行とブロックの共通部分を見て、片方にしかない数字があればもう片方から消せるというもの。日本語分かりにくい。（いや、俺の説明がわかりにくい）

この図でいうと、行とブロックに共通部分がある。5は行のうち共通部分にしかない。したがって、5は絶対にその共通部分になければならない。一方ブロックでは共通部分以外にも5がある。従ってこの共通部分以外の5は消せる。
プログラムは説明のまんま。特に技法なし。間違っているかも。共通部分はconstants.cに定義。

/**
 * 最初のブロックが行0,1,2と共通部分を持つ。
 * 4番目のブロックは行3,4,5と共通部分を持つ。
 */
const int locked_rows[9][3] = {
    {0, 1, 2}, {0, 1, 2}, {0, 1, 2},
    {3, 4, 5}, {3, 4, 5}, {3, 4, 5},
    {6, 7, 8}, {6, 7, 8}, {6, 7, 8}};

/**
 * 最初のブロックが列0,1,2と共通部分を持つ
 * 二番目のブロックは列3,4,5と共通部分を持つ
 */
const int locked_cols[9][3] = {
    {0, 1, 2}, {3, 4, 5}, {6, 7, 8},
    {0, 1, 2}, {3, 4, 5}, {6, 7, 8},
    {0, 1, 2}, {3, 4, 5}, {6, 7, 8}};

プログラム自体は、locked_candidate.cに記述

int kill_locked_candidate(sudoku_array * array)
{
    int count = 0;
    for (int i = 0; i < LINE_SIZE; i++) {
	for (int j = 0; j < BLOCK_COLS; j++) {
	    count += kill_locked_lines(BLOCK_COLS, blocks[i],
				       rows[locked_rows[i][j]], array->ar);
	}
	for (int j = 0; j < BLOCK_ROWS; j++) {
	    count += kill_locked_lines(BLOCK_ROWS, blocks[i],
				       cols[locked_cols[i][j]], array->ar);
	}
    }
    return count;
}


static int kill_locked_lines(int common_size, const int index1[],
			     const int index2[], cell_t array[])
{
    int result = 0;
    int common[common_size];
    search_common(common, common_size, index1, index2);
    if (common[0] == -1) {
	return 0;
    }
    for (uint16_t mask = 1; mask <= 0x100; mask = mask << 1) {
	int count = 0;
	// 共通部分に数字があるか
	for (int i = 0; i < common_size; i++) {
	    if (array[common[i]].symbol & mask) {
		count++;
	    }
	}
	if (count) {
	    // 他の部分に数字があるか
	    int diff = count_diff(mask, common, common_size, index1, array);
	    if (diff == 0) {
		result = kill_diff(mask, common, common_size, index2, array);
		if (result > 0) {
		    return 1;
		}
	    }
	    diff = count_diff(mask, common, common_size, index2, array);
	    if (diff == 0) {
		result = kill_diff(mask, common, common_size, index1, array);
		if (result > 0) {
		    return 1;
		}
	    }
	}
    }
    return 0;
}

static void search_common(int idx[], const int common_size, const int index1[], const int index2[])
{
    int p = 0;
    for (int i = 0; i < common_size; i++) {
	idx[i] = -1;
    }
    for (int i = 0; i < LINE_SIZE; i++) {
	for (int j = 0; j < LINE_SIZE; j++) {
	    if (index1[i] == index2[j]) {
		idx[p++] = index1[i];
	    }
	}
    }
}

static int is_in(const int idx[], int common_size, int num)
{
    for (int i = 0; i < common_size; i++) {
	if (idx[i] == num) {
	    return 1;
	}
    }
    return 0;
}

// idx になくてindex にあるコマについてmask の数を数える
static int count_diff(uint16_t mask, const int idx[], int common_size,
		      const int index[], cell_t array[])
{
    int count = 0;
    for (int i = 0; i < LINE_SIZE; i++) {
	if (is_in(idx, common_size, index[i])) {
	    continue;
	}
	if (array[index[i]].symbol & mask) {
	    count++;
	}
    }
    return count;
}

static int kill_diff(uint16_t mask, const int common[],
		     int common_size, const int index[], cell_t array[]) {
    uint16_t kill_mask = (‾mask) & FULL_SYMBOL;
    int count = 0;
    for (int i = 0; i < LINE_SIZE; i++) {
	if (is_in(common, common_size, index[i])) {
	    continue;
	}
	if (array[index[i]].symbol & mask) {
	    array[index[i]].symbol &= kill_mask;
	    count++;
	}
    }
    return count;
}

これ間違っているかも。9x9以外にも対応できるようにさっき書き直したけど、なんか眠くて自信ないよ。
ついでにあまり関係ないことを説明すると、symbolという変数名やdefine名で数字を表しているけど、これは別に数字じゃなくてもよくてアルファベットでも図形でもいいという意味でsymbolという言葉を使ったのである。しかし、そんな置き換えはゲームGUIアプリでやればいいことで、問題作成の時点では全部数字と考えてよいのであった。