【bitse——sudoku】1.终局生成1

进度不满意，一直没有写博客。

项目github地址：

https://github.com/wlh1998/wlhbitse

将目前进度进行总结，主要是终局生成部分初版。

1 psp

单位：分钟

planning:30

estimate:14*8*60

development:12*8*60

analysis:2*8*60

design spec:1*8*60

design review:0.5*8*60

coding standard:0.5*8*60

design:1*8*60

coding:2*8*60

code review:1*8*60

test:4*8*60

reporting:2*8*60

test report:1*8*60

size measurement:0.5*8*60

postmortem& process improvement plan:0.5*8*60

sum:14*8*60+30

2 解题思路及设计实现过程

首先了解数独的特点。再根据任务划分子任务。初步划定终局生成和数独求解两个大模块。有余力再进行附加部分。所以总任务大概分为：

任务规模较小，所以通过两个函数来完成。事实上，最初考虑分解几个函数，但发现反而影响效率。

3终局生成

数独的棋盘是一个9×9的格图，每3×3又是一个9宫格。

数独的要求是每行、每列、每个9宫格中，1~9这9个数字必须出现且仅出现一次。

数独终局考虑按以下思路生成：

规律一

第一行是1~9的一个全排列。

第二到九行，第一行右移3、6、1、4、7、2、5、8列的结果。

例如：

一个终局

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

即是一个满足条件的终局。

规律二

对于任何一个合法终局。

交换4~6，7~9中任两行，仍是合法终局。

然后在这两个规律的基础上，进行变换。

首先，对于任何一个1~9的全排列，都可以通过这种方式生成一个终局。

要求第一个固定，则只有8！=40320种终局。

其次，对于每一个全排列，有3！*3！=36种。

共1451520种，全部不重复，超过最大要求。

 

        int n = number;
	char sudoku[9][10];
	
	FILE * file = fopen(path.c_str(),"w");
	for (int i = 0; i < 9; i++)
	{
		sudoku[i][9] = '\0';
	}
	int shift[9] = { 0,3,6,1,4,7,2,5,8 };
	for (int i = 0; i < 6 && n; i++)
	{
		if (i)
		{
			next_permutation(shift + 3, shift + 6);
			shift[6] = 2;
			shift[7] = 5;
			shift[8] = 8;
		}
		for (int j = 0; j < 6 && n; j++)
		{
			printf("%d\n", number - n);
			if (j)
			{
				next_permutation(shift + 6, shift + 9);

			}
			char line[10] = "678912345";
			for (int k = 0; k < 40320 && n; k++)
			{
				
				if (k)
				{
					next_permutation(line + 1, line + 9);
				}
				for (int r = 0; r < 9; r++)
				{
					for (int c = 0; c < 9; c++)
					{
						sudoku[r][(c + shift[r]) % 9] = line[c];
					}
					fputs(sudoku[r], file);
				}
				n--;
				//savesudoku(path, sudoku);

			}

		}
	}
	fclose(file);

注意：

使用char而不是int可节约内存。

不要将保存封装，频繁的io效率十分低下。