プログラミングの美1.15節:構造数独アルゴリズム-遡及法と置換法

1.遡及法-手順

/**   
 *       
 * From     1.15
*/

#include <stdio.h>
#include <time.h>

/*          */
#define SUDOKU_NUM 1

/**
 *   is_digital_match
 *   sudoku[i][j]         
*/
int is_digital_match(int sudoku[][9], int i, int j)
{
	int temp = sudoku[i][j];
	int p, q;
	int m, n;
	
	for(p=0; p<9; p++)
		if(p!=i && sudoku[p][j]==temp)
			return 0;
	for(p=0; p<9; p++)
		if(p!=j && sudoku[i][p]==temp)
			return 0;

	p = i/3;
	q = j/3;
	for(m=p*3; m<p*3+3; m++)
		for(n=q*3; n<q*3+3; n++)
			if(m!=i && n!=j && sudoku[m][n]==temp)
				return 0;
	
	return 1;
}

/*      */
void sudoku_print(int sudoku[][9])
{
	int i,j;
	for(i=0; i<9; i++)
	{
		for(j=0; j<9; j++)
			printf("%4d", sudoku[i][j]);
		printf("
");
	}
}

int main(void)
{
    int sudoku[9][9] = {0};
    int i, j, temp=0;
    int k=0, num=0;

	srand(time(0));
	for(i=0; i<9; i++)
		for(j=0; j<9; j++)
			sudoku[i][j] = 0;
	/*         ，            */
	/*       ，          */
    for(i=0; i<9; i++)
	{
		temp = rand() % 81;
		sudoku[temp/9][temp%9] = i+1;
	}
	/*   ，      */
    while(1)
    {
        i = k/9;
        j = k%9;

		while(1)
		{
			sudoku[i][j]++;
			if(sudoku[i][j] == 10)
			{
				sudoku[i][j] = 0;
        		--k;
				break;
			}
			else if(is_digital_match(sudoku, i, j) == 1)
			{
				++k;
				break;
			}
		}

		if(k == 81)
		{
			printf("Proper sudoku matrix %d: 
", ++num);
			sudoku_print(sudoku);
			if(num >= SUDOKU_NUM)
				return 0;

			--k;
		}
    }
	
    return 0;
}

出力結果:

Proper sudoku matrix 1: 
   2   1   4   5   6   7   9   3   8
   3   5   7   1   8   9   2   4   6
   6   8   9   4   2   3   1   5   7
   4   2   1   3   7   5   8   6   9
   8   6   3   2   9   1   4   7   5
   7   9   5   6   4   8   3   1   2
   5   3   6   8   1   2   7   9   4
   1   7   8   9   5   4   6   2   3
   9   4   2   7   3   6   5   8   1

2.置き換えの方法

/**    
 *             
 * From：    1.15 
 *     ，     
*/

#include <stdio.h>
#include <time.h>

int main()
{
    int ini_matrix[3][3];    /*   3*3    ，    9*9    */
    int sudoku[9][9] = {0};
    int i,j;

    for(i=0; i<3; i++)
    {
        for (j=0; j<3; j++)
        {
            ini_matrix[i][j] = i*3+j+1;
        }
    }
    /*       */
    srand(time(0));
    for(i=0; i<9; i++)
    {
        int temp = rand() % 9;
        j = ini_matrix[i/3][i%3];
        ini_matrix[i/3][i%3] = ini_matrix[temp/3][temp%3];
        ini_matrix[temp/3][temp%3] = j;
    }

    printf("Initial matrix:
");
    for(i=0; i<3; i++)
    {
        for (j=0; j<3; j++)
        {
            printf("%d\t", ini_matrix[i][j]);
        }
        printf("
");
    }

    /*Put the ini_matrix to the center of sudoku*/
    for(i=0; i<3; i++)
    {
        for (j=0; j<3; j++)
        {
            sudoku[i+3][j+3] = ini_matrix[i][j];
            if(i==0)
            {
                sudoku[i+4][j] = ini_matrix[i][j];
                sudoku[i+5][j+6] = ini_matrix[i][j];
            }
            else if(i==1)
            {
                sudoku[i+4][j] = ini_matrix[i][j];
                sudoku[i+2][j+6] = ini_matrix[i][j];
            }
            else
            {
                sudoku[i+1][j] = ini_matrix[i][j];
                sudoku[i+2][j+6] = ini_matrix[i][j];
            }

            if(j==0)
            {
                sudoku[i][j+4] = ini_matrix[i][j];
                sudoku[i+6][j+5] = ini_matrix[i][j];
            }
            else if(j==1)
            {
                sudoku[i][j+4] = ini_matrix[i][j];
                sudoku[i+6][j+2] = ini_matrix[i][j];
            }
            else
            {
                sudoku[i][j+1] = ini_matrix[i][j];
                sudoku[i+6][j+2] = ini_matrix[i][j];
            }
        }
    }

    for(i=3; i<6; i++)
    {
        for (j=0; j<3; j++)
        {
            if(j==0)
            {
                sudoku[i-3][j+1] = sudoku[i][j];
                sudoku[i+3][j+2] = sudoku[i][j];
            }
            else if(j==1)
            {
                sudoku[i-3][j+1] = sudoku[i][j];
                sudoku[i+3][j-1] = sudoku[i][j];
            }
            else
            {
                sudoku[i-3][j-2] = sudoku[i][j];
                sudoku[i+3][j-1] = sudoku[i][j];
            }
        }
    }

    for(i=3; i<6; i++)
    {
        for (j=6; j<9; j++)
        {
            if(j==6)
            {
                sudoku[i-3][j+1] = sudoku[i][j];
                sudoku[i+3][j+2] = sudoku[i][j];
            }
            else if(j==7)
            {
                sudoku[i-3][j+1] = sudoku[i][j];
                sudoku[i+3][j-1] = sudoku[i][j];
            }
            else
            {
                sudoku[i-3][j-2] = sudoku[i][j];
                sudoku[i+3][j-1] = sudoku[i][j];
            }
        }
    }

    printf("Final matrix:
");
    for(i=0; i<9; i++)
    {
        for (j=0; j<9; j++)
        {
            printf("%d\t", sudoku[i][j]);
        }
        printf("
");
    }

    return 0;
}

出力結果:

Initial matrix：
3	5	7	
2	6	4	
8	9	1	
Final matrix：
1	8	9	7	3	5	4	2	6	
7	3	5	4	2	6	1	8	9	
4	2	6	1	8	9	7	3	5	
8	9	1	3	5	7	2	6	4	
3	5	7	2	6	4	8	9	1	
2	6	4	8	9	1	3	5	7	
9	1	8	5	7	3	6	4	2	
5	7	3	6	4	2	9	1	8	
6	4	2	9	1	8	5	7	3