複数解答ありの数独

とりあえず解答が20個くらい出たところで止めました。

解答0
1 3 9 4 6 2 7 5 8
5 2 8 1 3 7 6 4 9
4 7 6 5 8 9 1 3 2
2 4 1 7 9 6 3 8 5
9 6 5 3 1 8 2 7 4
7 8 3 2 4 5 9 1 6
6 5 2 8 7 3 4 9 1
3 9 4 6 5 1 8 2 7
8 1 7 9 2 4 5 6 3

解答1
1 3 9 4 6 2 7 5 8
5 2 8 1 3 7 6 4 9
4 7 6 5 8 9 1 3 2
2 4 1 7 9 6 3 8 5
9 6 5 3 1 8 2 7 4
7 8 3 2 4 5 9 1 6
8 5 2 9 7 3 4 6 1
3 9 4 6 5 1 8 2 7
6 1 7 8 2 4 5 9 3

解答2
1 3 9 4 6 2 7 5 8
5 2 8 1 3 7 6 4 9
4 7 6 5 8 9 1 3 2
2 4 1 7 9 6 3 8 5
9 6 5 3 1 8 2 7 4
7 8 3 2 4 5 9 6 1
8 5 2 9 7 3 4 1 6
3 9 4 6 5 1 8 2 7
6 1 7 8 2 4 5 9 3

解答3
1 3 9 4 6 2 7 5 8
5 2 8 1 3 7 6 4 9
4 7 6 5 8 9 1 3 2
2 4 1 7 9 6 3 8 5
9 6 5 8 1 3 2 7 4
7 8 3 2 4 5 9 1 6
3 5 2 6 7 8 4 9 1
6 9 4 3 5 1 8 2 7
8 1 7 9 2 4 5 6 3

解答4
1 3 9 4 6 2 7 5 8
5 2 8 1 3 7 6 4 9
4 7 6 5 8 9 1 3 2
2 4 1 7 9 6 3 8 5
9 6 5 8 1 3 2 7 4
7 8 3 2 4 5 9 1 6
3 5 2 9 7 8 4 6 1
6 9 4 3 5 1 8 2 7
8 1 7 6 2 4 5 9 3

解答5
1 3 9 4 6 2 7 5 8
5 2 8 1 3 7 6 4 9
4 7 6 5 8 9 1 3 2
2 4 1 7 9 6 3 8 5
9 6 5 8 1 3 2 7 4
7 8 3 2 4 5 9 1 6
6 5 2 3 7 8 4 9 1
3 9 4 6 5 1 8 2 7
8 1 7 9 2 4 5 6 3

解答6
1 3 9 4 6 2 7 5 8
5 2 8 1 3 7 6 4 9
4 7 6 5 8 9 1 3 2
2 4 1 7 9 6 3 8 5
9 6 5 8 1 3 2 7 4
7 8 3 2 4 5 9 6 1
3 5 2 9 7 8 4 1 6
6 9 4 3 5 1 8 2 7
8 1 7 6 2 4 5 9 3

解答7
1 3 9 4 6 2 7 5 8
5 2 8 1 3 7 6 4 9
4 7 6 5 8 9 1 3 2
2 4 1 7 9 6 3 8 5
9 6 5 8 1 3 2 7 4
7 8 3 2 4 5 9 6 1
6 5 2 9 7 8 4 1 3
3 9 4 6 5 1 8 2 7
8 1 7 3 2 4 5 9 6

解答8
1 3 9 4 6 2 7 5 8
5 2 8 1 3 7 6 4 9
4 7 6 5 8 9 1 3 2
2 8 1 7 4 6 3 9 5
9 4 5 3 1 8 2 7 6
7 6 3 2 9 5 4 8 1
6 5 2 8 7 3 9 1 4
3 9 4 6 5 1 8 2 7
8 1 7 9 2 4 5 6 3

解答9
1 3 9 4 6 2 7 5 8
5 2 8 1 3 7 6 4 9
4 7 6 5 8 9 1 3 2
2 8 1 7 4 6 3 9 5
9 4 5 3 1 8 2 7 6
7 6 3 2 9 5 4 8 1
6 5 2 8 7 4 9 1 3
3 9 4 6 5 1 8 2 7
8 1 7 9 2 3 5 6 4

解答10
1 3 9 4 6 2 7 5 8
5 2 8 1 3 7 6 4 9
4 7 6 5 8 9 1 3 2
2 8 1 7 4 6 3 9 5
9 4 5 8 1 3 2 7 6
7 6 3 2 9 5 4 8 1
3 5 2 6 7 8 9 1 4
6 9 4 3 5 1 8 2 7
8 1 7 9 2 4 5 6 3

解答11
1 3 9 4 6 2 7 5 8
5 2 8 1 3 7 6 4 9
4 7 6 5 8 9 1 3 2
2 8 1 7 4 6 3 9 5
9 4 5 8 1 3 2 7 6
7 6 3 2 9 5 4 8 1
6 5 2 3 7 8 9 1 4
3 9 4 6 5 1 8 2 7
8 1 7 9 2 4 5 6 3

解答12
1 3 9 4 6 2 7 5 8
5 2 8 1 3 7 6 4 9
4 7 6 5 8 9 1 3 2
2 8 1 7 4 6 3 9 5
9 4 5 8 1 3 2 7 6
7 6 3 2 9 5 4 8 1
8 5 2 6 7 4 9 1 3
6 9 4 3 5 1 8 2 7
3 1 7 9 2 8 5 6 4

解答13
1 3 9 4 6 2 7 5 8
5 2 8 1 3 7 6 4 9
4 7 6 5 8 9 1 3 2
2 8 3 7 4 6 9 1 5
9 4 5 3 1 8 2 7 6
7 6 1 2 9 5 3 8 4
6 5 2 8 7 3 4 9 1
3 9 4 6 5 1 8 2 7
8 1 7 9 2 4 5 6 3

解答14
1 3 9 4 6 2 7 5 8
5 2 8 1 3 7 6 4 9
4 7 6 5 8 9 1 3 2
2 8 3 7 4 6 9 1 5
9 4 5 3 1 8 2 7 6
7 6 1 2 9 5 3 8 4
8 5 2 9 7 3 4 6 1
3 9 4 6 5 1 8 2 7
6 1 7 8 2 4 5 9 3

解答15
1 3 9 4 6 2 7 5 8
5 2 8 1 3 7 6 4 9
4 7 6 5 8 9 1 3 2
2 8 3 7 4 6 9 1 5
9 4 5 3 1 8 2 7 6
7 6 1 2 9 5 4 8 3
6 5 2 8 7 4 3 9 1
3 9 4 6 5 1 8 2 7
8 1 7 9 2 3 5 6 4

解答16
1 3 9 4 6 2 7 5 8
5 2 8 1 3 7 6 4 9
4 7 6 5 8 9 1 3 2
2 8 3 7 4 6 9 1 5
9 4 5 3 1 8 2 7 6
7 6 1 2 9 5 4 8 3
8 5 2 9 7 4 3 6 1
3 9 4 6 5 1 8 2 7
6 1 7 8 2 3 5 9 4

解答17
1 3 9 4 6 2 7 5 8
5 2 8 1 3 7 6 4 9
4 7 6 5 8 9 1 3 2
2 8 3 7 4 6 9 1 5
9 4 5 8 1 3 2 7 6
7 6 1 2 9 5 3 8 4
3 5 2 6 7 8 4 9 1
6 9 4 3 5 1 8 2 7
8 1 7 9 2 4 5 6 3

解答18
1 3 9 4 6 2 7 5 8
5 2 8 1 3 7 6 4 9
4 7 6 5 8 9 1 3 2
2 8 3 7 4 6 9 1 5
9 4 5 8 1 3 2 7 6
7 6 1 2 9 5 3 8 4
3 5 2 9 7 8 4 6 1
6 9 4 3 5 1 8 2 7
8 1 7 6 2 4 5 9 3

解答19
1 3 9 4 6 2 7 5 8
5 2 8 1 3 7 6 4 9
4 7 6 5 8 9 1 3 2
2 8 3 7 4 6 9 1 5
9 4 5 8 1 3 2 7 6
7 6 1 2 9 5 3 8 4
6 5 2 3 7 8 4 9 1
3 9 4 6 5 1 8 2 7
8 1 7 9 2 4 5 6 3

解答20
1 3 9 4 6 2 7 5 8
5 2 8 1 3 7 6 4 9
4 7 6 5 8 9 1 3 2
2 8 3 7 4 6 9 1 5
9 4 5 8 1 3 2 7 6
7 6 1 2 9 5 4 8 3
8 5 2 6 7 4 3 9 1
6 9 4 3 5 1 8 2 7
3 1 7 9 2 8 5 6 4

```cpp
#include <stdio.h>
#include <string.h>

struct SUUDOKU
{
	unsigned int table[9][9];
};

struct SUUDOKU ans_list[20] = {0};

bool check(const struct SUUDOKU suudoku, const unsigned int i, const unsigned int x, const unsigned y)
{
	for(unsigned int px = 0; px < 9; px++)
	{
		if( i == suudoku.table[y][px] )
		{
			return false;
		}
	}
	for(unsigned int py = 0; py < 9; py++)
	{
		if( i == suudoku.table[py][x] )
		{
			return false;
		}
	}
	const unsigned int py_offset = (y/3)*3;
	const unsigned int px_offset = (x/3)*3;
	for(unsigned int py = py_offset; py < 3+py_offset; py++)
	{
		for(unsigned int px = px_offset; px < 3+px_offset; px++)
		{
			if( i == suudoku.table[py][px] )
			{
				return false;
			}
		}
	}
	return true;
}

bool solve(struct SUUDOKU suudoku, const unsigned int x, const unsigned int y)
{
	static unsigned int list_cnt = 0;
	if( y == 9 )
	{
		printf("解答%d\n", list_cnt);
		for(unsigned int py = 0; py < 9; py++)
		{
			for(unsigned int px = 0; px < 9; px++)
			{
				printf("%d ",suudoku.table[py][px]);
			}
			printf("\n");
		}
		printf("\n");
		if(list_cnt < 20)
		{
			for( unsigned int cnt = 0; cnt < list_cnt; cnt++)
			{
				int ret = memcmp(&ans_list[cnt], &suudoku, sizeof(struct SUUDOKU));
				if( ret == 0 )
				{
					printf("解答がかぶってる！！");
				}
			}
			ans_list[list_cnt] = suudoku;
		}
		list_cnt++;
		return true;
	}
	if( suudoku.table[y][x] != 0 )
	{
		return solve(suudoku, (x != 8) ? x+1: 0, (x != 8) ? y: y+1);
	}
	else
	{
		for(unsigned int i = 1; i <= 9; i++)
		{
			if( check(suudoku, i, x, y) == false )
			{
				continue;
			}
			suudoku.table[y][x] = i;
			bool ret = solve(suudoku, (x != 8) ? x+1: 0, (x != 8) ? y: y+1);
			//if( ret == true )
			//{
			//	return true;
			//}
		}
		return false;
	}
}

int main()
{
	//const struct SUUDOKU suudoku = {{
	//	{8,0,0, 0,0,0, 0,0,0},
	//	{0,0,3, 6,0,0, 0,0,0},
	//	{0,7,0, 0,9,0, 2,0,0},
	//	{0,5,0, 0,0,7, 0,0,0},
	//	{0,0,0, 0,4,5, 7,0,0},
	//	{0,0,0, 1,0,0, 0,3,0},
	//	{0,0,1, 0,0,0, 0,6,8},
	//	{0,0,8, 5,0,0, 0,1,0},
	//	{0,9,0, 0,0,0, 4,0,0}
	//}};
	const struct SUUDOKU suudoku = {{
		{0,0,9, 0,0,0, 7,0,0},
		{0,2,8, 0,0,0, 6,4,0},
		{0,0,0, 0,0,0, 0,0,0},
		{0,0,0, 7,0,6, 0,0,0},
		{0,0,0, 0,1,0, 0,0,0},
		{0,0,0, 2,0,5, 0,0,0},
		{0,0,0, 0,0,0, 0,0,0},
		{0,9,4, 0,0,0, 8,2,0},
		{0,0,7, 0,0,0, 5,0,0}
	}};
	//const struct SUUDOKU suudoku = {{
	//	{0,5,7, 4,9,0, 0,3,0},
	//	{2,0,4, 0,8,0, 1,0,0},
	//	{9,0,0, 0,0,6, 0,0,0},
	//	{4,7,0, 0,0,0, 0,0,0},
	//	{0,0,9, 0,6,0, 2,0,0},
	//	{0,0,0, 0,0,0, 0,5,1},
	//	{0,0,0, 6,0,0, 0,0,3},
	//	{0,0,3, 0,7,0, 4,0,8},
	//	{0,4,0, 0,2,8, 9,1,0}
	//}};
	solve(suudoku, 0, 0);
	printf("end\n");
	getchar();
	return 0;
}
```