//CreateData.cpp 生成數獨矩陣的算法
//調用原型
//void CreateShuDuMetrix(int DataBuffer[9][9]);
//
//code is from csdn

#include "stdafx.h"
#include <windows.h>
#include <stdlib.h>
#include "CreateData.h"


int Fill_Pos(SHUDUMETRIX dest, LINETYPE nums_possible, int line, int pos)
{
	if ( pos >= 9 )
	{
		return Fill_Line(dest, line + 1);
	}
	if ( dest[pos][line] != 0 ) return Fill_Pos(dest, nums_possible, line, pos + 1);
	for ( int i = 0; i < 9; i++ )
	{
		if ( !nums_possible[i] ) continue;
		/* 檢查本列是否重復 */
		int vetical_failed = 0;
		for ( int j = 0; j < 9; j++ ) 
		{
			if ( dest[pos][j] == i + 1 )
			{
				vetical_failed = 1;
				break;
			}
		}
		if ( vetical_failed ) continue; 

		/* 檢查九宮格是否重復 */
		int nine_failed = 0;
		int m = pos / 3;
		int n = line / 3;
		m *= 3;
		n *= 3;
		for ( int y = n; y < n + 3; y++ )
		{
			for ( int x = m; x < m + 3; x++ )
			{
				if ( dest[x][y] == i + 1 ) 
				{
					nine_failed = 1;
					break;
				}
			}
			if ( nine_failed ) break;
		}
		if ( nine_failed ) continue;
		
		/* all ok, try next position */
		dest[pos][line] = i + 1;
		nums_possible[i] = 0;
		if (Fill_Pos(dest, nums_possible, line, pos + 1) ) 
		{
			/* 本行已全部OK，嘗試下一行 */
			if ( Fill_Line(dest, line + 1) ) return 1;
			/* 下一行失敗，重新嘗試本位置的剩余可能性 */
		}
		nums_possible[i] = 1;
		dest[pos][line] = 0;
	}
	return 0;
}

/* 填下一行 */
int Fill_Line(SHUDUMETRIX dest, int line)
{
	if ( line >= 9 )
	{
		return 1;
	}
	LINETYPE nums;
	LINETYPE saveline;
	/* calc possibility(for the current line) */
	for ( int i = 0; i < 9; i++ ) nums[i] = 1; /* all can be */
	for ( i = 0; i < 9; i++ )
	{
		int n = dest[i][line];
		/* save line */
		saveline[i] = dest[i][line];
		if ( n != 0 ) nums[n - 1] = 0; /* appears */
	}
	if ( !Fill_Pos(dest, nums, line, 0) )
	{
		/* restore line */
		for (  i = 0; i < 9; i++ ) dest[i][line] = saveline[i];
		return 0;
	}
	return 1;
}

void CreateShuDuMetrix(SHUDUMETRIX dest)
{
	memset(dest, 0, sizeof(SHUDUMETRIX));
	srand( GetTickCount() );

	/* 隨機填充第一行 */
	int numbers[9] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	//隨機交換
	for ( int i = 0; i < 100; i++ )
	{
		int p1 = rand() % 9;
		int p2 = rand() % 9;
		int data = numbers[p1];
		numbers[p1] = numbers[p2];
		numbers[p2] = data;
	}
	for ( i = 0; i < 9; i++ ) dest[i][0] = numbers[i];

	//繼續填充下一行
	Fill_Line(dest, 1);
	
	return ;
}