【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效率十分低下。