// Soduku.cpp : 定義控制台應用程式的入口點。
//
#include "stdafx.h"
#include <map>
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
using namespace std;
#define ROW_NUM (9)
#define COL_NUM (9)
#define NUMBERS (9)
const unsigned char originalArray[ROW_NUM][COL_NUM] = {
{0,0,0,1,0,0,2,6,0},
{7,0,0,0,3,0,0,0,0},
{3,0,2,0,8,0,4,0,0},
{0,0,0,4,0,8,0,0,1},
{0,3,5,0,0,0,9,4,0},
{2,0,0,3,0,5,0,0,0},
{0,0,6,0,5,0,7,0,9},
{0,0,0,0,4,0,0,0,8},
{0,5,7,0,0,9,0,0,0}
};
const unsigned char digits[NUMBERS] = {1,2,3,4,5,6,7,8,9};
struct Grid{
unsigned char row;
unsigned char column;
unsigned char value;
map<unsigned char, unsigned char> options;
Grid(){
row = 0;
column = 0;
value = 0;
options.clear();
}
};
Grid soduku[ROW_NUM][COL_NUM] = {};
struct NineGrid{
pair<unsigned char, unsigned char> start;
pair<unsigned char, unsigned char> end;
set<unsigned char> values;
NineGrid(){
start.first = 0;
start.second = 0;
end.first = 0;
end.second = 0;
values.clear();
}
};
NineGrid nineGrid[(ROW_NUM/3)*(COL_NUM/3)] = {};
void InitializeSoduku(){
for(unsigned char i = 0; i < ROW_NUM; ++i)
{
for(unsigned char j = 0; j < COL_NUM; ++j)
{
soduku[i][j].row = i;
soduku[i][j].column = j;
soduku[i][j].value = originalArray[i][j];
}
}
unsigned char index = 0;
for(unsigned char i = 0; i < ROW_NUM; i+=3)
{
for(unsigned char j = 0; j < COL_NUM; (index++,j+=3))
{
nineGrid[index].start.first = i;
nineGrid[index].start.second = j;
nineGrid[index].end.first = i+2;
nineGrid[index].end.second = j+2;
}
}
for(unsigned char n = 0; n < ROW_NUM; ++n)
{
for(unsigned char i = nineGrid[n].start.first; i <= nineGrid[n].end.first; ++i)
{
for(unsigned char j = nineGrid[n].start.second; j <= nineGrid[n].end.second; ++j)
{
if(soduku[i][j].value != 0)
{
nineGrid[n].values.insert(soduku[i][j].value);
}
}
}
}
}
void CollectRow(set<unsigned char>& row, unsigned char rowIndex)
{
for(unsigned char j = 0; j < COL_NUM; ++j)
{
if(soduku[rowIndex][j].value != 0)
{
row.insert(soduku[rowIndex][j].value);
}
}
}
void CollectColumn(set<unsigned char>& col, unsigned char colIndex)
{
for(unsigned char i = 0; i < ROW_NUM; ++i)
{
if(soduku[i][colIndex].value != 0)
{
col.insert(soduku[i][colIndex].value);
}
}
}
void CollectNineGrid(set<unsigned char>& gridSet,unsigned char row, unsigned char col)
{
for(unsigned int i = 0; i < ROW_NUM; ++i)
{
if(nineGrid[i].start.first <= row && row <= nineGrid[i].end.first)
{
if(nineGrid[i].start.second <= col && col <= nineGrid[i].end.second)
{
for(unsigned char m = nineGrid[i].start.first; m <= nineGrid[i].end.first; ++m )
{
for(unsigned char n = nineGrid[i].start.second; n <= nineGrid[i].end.second; ++n)
{
if(soduku[m][n].value != 0)
{
gridSet.insert(soduku[m][n].value);
}
}
}
break;
}
}
}
}
void CollectAll(set<unsigned char>& vals,unsigned char row, unsigned char col)
{
vals.clear();
CollectRow(vals, row);
CollectColumn(vals, col);
CollectNineGrid(vals, row, col);
}
void PrintCurrent()
{
for(unsigned char i = 0; i < ROW_NUM; ++i)
{
for(unsigned char j = 0; j < COL_NUM; ++j)
{
if(soduku[i][j].value == 0)
{
cout<<"(";
std::map<unsigned char, unsigned char>::iterator iter = soduku[i][j].options.begin();
for(iter; iter != soduku[i][j].options.end(); ++iter)
{
cout<<(unsigned short)iter->second<<",";
}
cout<<")";
}else
{
cout<<(unsigned short)soduku[i][j].value<<" ";
}
}
cout<<std::endl;
}
}
bool HasExisted(std::set<unsigned char>& values, unsigned char val)
{
return values.find(val) != values.end();
}
void DigitsLoop()
{
for(unsigned char m = 0; m < NUMBERS; ++m)
{
unsigned char digit = digits[m];
for(unsigned char n = 0; n < ROW_NUM; ++n)
{
for(unsigned char i = nineGrid[n].start.first; i <= nineGrid[n].end.first; ++i)
{
for(unsigned char j = nineGrid[n].start.second; j <= nineGrid[n].end.second; ++j)
{
if(soduku[i][j].value != 0)
{
continue;
}
set<unsigned char> values;
do
{ //驗證九宮格中的數
values.clear();
CollectNineGrid(values, i, j);
if(HasExisted(values, digit))
{
break;
}
//驗證橫排
values.clear();
CollectRow(values, i);
if(HasExisted(values, digit))
{
break;
}
//驗證豎排
values.clear();
CollectColumn(values, j);
if(HasExisted(values, digit))
{
break;
}
soduku[i][j].options[digit] = digit;
}while(0);
}
}
}
}
}
void AddToNineGridSet(unsigned char row, unsigned char col, unsigned char val)
{
for(unsigned int i = 0; i < ROW_NUM; ++i)
{
if(nineGrid[i].start.first <= row && row <= nineGrid[i].end.first)
{
if(nineGrid[i].start.second <= col && col <= nineGrid[i].end.second)
{
nineGrid[i].values.insert(val);
break;
}
}
}
}
void RemoveAll(unsigned char row, unsigned char col, unsigned char val)
{
//1.去除行中其他空格可選項中val對應的項目
std::map<unsigned char, unsigned char>::iterator iter;
for(unsigned char j = 0; j < COL_NUM; ++j)
{
if(soduku[row][j].options.empty())
{
continue;
}
iter = soduku[row][j].options.find(val);
if(iter != soduku[row][j].options.end())
{
soduku[row][j].options.erase(iter);
}
}
//2.去除列中其他空格可選項中val對應的項目
for(unsigned int i = 0; i < ROW_NUM; ++i)
{
if(soduku[i][col].options.empty())
{
continue;
}
iter = soduku[i][col].options.find(val);
if(iter != soduku[i][col].options.end())
{
soduku[i][col].options.erase(iter);
}
}
//3.去除九宮格中其他空格可選項中val對應的項目
for(unsigned int i = 0; i < ROW_NUM; ++i)
{
if(nineGrid[i].start.first <= row && row <= nineGrid[i].end.first)
{
if(nineGrid[i].start.second <= col && col <= nineGrid[i].end.second)
{
for(unsigned char m = nineGrid[i].start.first; m <= nineGrid[i].end.first; ++m )
{
for(unsigned char n = nineGrid[i].start.second; n <= nineGrid[i].end.second; ++n)
{
if(soduku[m][n].options.empty())
{
continue;
}
iter = soduku[m][n].options.find(val);
if(iter != soduku[m][n].options.end())
{
soduku[m][n].options.erase(iter);
}
}
}
break;
}
}
}
}
void MakeChoice()
{
for(unsigned char i = 0; i < ROW_NUM; ++i)
{
for(unsigned char j = 0; j < COL_NUM; ++j)
{
if(soduku[i][j].options.size() == 1)
{
//指派給對應的空格
soduku[i][j].value = soduku[i][j].options.begin()->first;
//加入九宮格中的集合中
AddToNineGridSet(i, j, soduku[i][j].value);
//去除橫列和九宮格中其他空格可選項中含有該值的項目
RemoveAll(i, j, soduku[i][j].value);
}
}
}
}
void Exception()
{
set<unsigned char> vals;
for(unsigned char i = 0; i < ROW_NUM; ++i)
{
for(unsigned char j = 0; j < COL_NUM; ++j)
{
if(soduku[i][j].value != 0)
{
continue;
}
CollectAll(vals, i, j);
vector<unsigned char> result(10);
std::set_difference(digits, digits+NUMBERS, vals.begin(), vals.end(), result.begin());
for(unsigned int n = 0; n < result.size(); ++n)
{
if(result[n] != 0)
{
soduku[i][j].options[result[n]] = result[n];
}
}
}
}
}
bool CanEnd()
{
for(unsigned char i = 0; i < ROW_NUM; ++i)
{
for(unsigned char j = 0; j < COL_NUM; ++j)
{
if(soduku[i][j].value == 0)
{
return false;
}
}
}
return true;
}
int _tmain(int argc, _TCHAR* argv[])
{
InitializeSoduku();
do
{
DigitsLoop();
MakeChoice();
Exception();
MakeChoice();
}while(!CanEnd());
PrintCurrent();
getchar();
return 0;
}