/**
* 数独求解程åº
* 输入方å¼ï¼Œä»¥è¡Œä¸ºå•ä½ï¼ŒæŒ‰ç…§ 9*9 å®«æ ¼çš„æ–¹å¼ï¼Œæ¯è¾“å…¥ä¸€è¡ŒæŒ‰ä¸‹ä¸€ä¸ªå›žè½¦ï¼Œç©ºæ ¼ç”¨ 0 表示
* 例如：
* input >
* 000003080 [Enter]
* 030000090 [Enter]
* 800090003 [Enter]
* 000080905 [Enter]
* 009007800 [Enter]
* 106000000 [Enter]
* 600040008 [Enter]
* 040000010 [Enter]
* 090800000 [Enter]
* output >
* 9 1 2 4 5 3 6 8 7
* 5 3 4 6 7 8 1 9 2
* 8 6 7 2 9 1 4 5 3
*
* 2 7 3 1 8 4 9 6 5
* 4 5 9 3 6 7 8 2 1
* 1 8 6 9 2 5 3 7 4
*
* 6 2 1 7 4 9 5 3 8
* 7 4 8 5 3 6 2 1 9
* 3 9 5 8 1 2 7 4 6
*/
#include
using namespace std;
/* æž„é€ å®Œæˆæ ‡å¿— */
bool sign = false;
/* 创建数独矩阵 */
int num[9][9];
/* 函数声明 */
void Input();
void Output();
bool Check(int n, int key);
int DFS(int n);
/* 主函数 */
int main()
{
cout << "请输入一个9*9的数独矩阵，空ä½ä»¥0表示:" << endl;
Input();
DFS(0);
Output();
system("pause");
}
/* 读入数独矩阵 */
void Input()
{
char temp[9][9];
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
cin >> temp[i][j];
num[i][j] = temp[i][j] - '0';
}
}
}
/* 输出数独矩阵 */
void Output()
{
cout << endl;
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
cout << num[i][j] << " ";
if (j % 3 == 2)
{
cout << " ";
}
}
cout << endl;
if (i % 3 == 2)
{
cout << endl;
}
}
}
/* 判æ–keyå¡«å…¥n时是å¦æ»¡è¶³æ¡ä»¶ */
bool Check(int n, int key)
{
/* 判æ–n所在横列是å¦åˆæ³• */
for (int i = 0; i < 9; i++)
{
/* j为nç«–åæ ‡ */
int j = n / 9;
if (num[j][i] == key) return false;
}
/* 判æ–n所在竖列是å¦åˆæ³• */
for (int i = 0; i < 9; i++)
{
/* j为n横åæ ‡ */
int j = n % 9;
if (num[i][j] == key) return false;
}
/* x为n所在的å°ä¹å®«æ ¼å·¦é¡¶ç‚¹ç«–åæ ‡ */
int x = n / 9 / 3 * 3;
/* y为n所在的å°ä¹å®«æ ¼å·¦é¡¶ç‚¹æ¨ªåæ ‡ */
int y = n % 9 / 3 * 3;
/* 判æ–n所在的å°ä¹å®«æ ¼æ˜¯å¦åˆæ³• */
for (int i = x; i < x + 3; i++)
{
for (int j = y; j < y + 3; j++)
{
if (num[i][j] == key) return false;
}
}
/* 全部åˆæ³•ï¼Œè¿”回æ£ç¡® */
return true;
}
/* æ·±æœæž„é€ æ•°ç‹¬ */
int DFS(int n)
{
/* 所有的都符åˆï¼Œé€€å‡ºé€’å½’ */
if (n > 80)
{
sign = true;
return 0;
}
/* 当å‰ä½ä¸ä¸ºç©ºæ—¶è·³è¿‡ */
if (num[n / 9][n % 9] != 0)
{
DFS(n + 1);
}
else
{
/* å¦åˆ™å¯¹å½“å‰ä½è¿›è¡Œæžšä¸¾æµ‹è¯• */
for (int i = 1; i <= 9; i++)
{
/* 满足æ¡ä»¶æ—¶å¡«å…¥æ•°å— */
if (Check(n, i) == true)
{
num[n / 9][n % 9] = i;
/* 继ç»æœç´¢ */
DFS(n + 1);
/* è¿”å›žæ—¶å¦‚æžœæž„é€ æˆåŠŸï¼Œåˆ™ç›´æŽ¥é€€å‡º */
if (sign == true) return 0;
/* å¦‚æžœæž„é€ ä¸æˆåŠŸï¼Œè¿˜åŽŸå½“å‰ä½ */
num[n / 9][n % 9] = 0;
}
}
}
}