数独问题的方法，关于栈的使用
数独思想很简单，行列九宫格不能有重复的数字，不过我的c＋＋基础不好，要多花时间看书，不过我很想写出这个project，求请教。我的思想就是先通篇检查，把确定的确定了，确定数字＋1,并且删去所有重复的备选，然后从备选数最少的一个格子开始检查，如果只有1个备选，定为确定数字，删去其对应的行列九宫格重复， 然后有一个猜，猜的同时删去备选数，最后用一个stack，中文好像是栈？猜之前备份，这个备份就把猜的数字变为确定只有一个，把备份放在最上面，猜对了就继续，猜错了就pop。
#include <Block.h>
我的block就是九宫格，
---------------------------------------------block.h
#ifndef BLOCK_H
#define BLOCK_H
#include <set.h>
class Block
{
public:
std::set <int> candidates;
std::set<int>::iterator it;
int dv;
Block();
void erase(int);
int DecidableCell(int);
void UndecidableCell();
int getvalue();
};
#endif // BLOCK_H
---------------------------------------------block.cpp
Block::Block()
{
int z=0;
for(z=0;z<9;z++){
candidates.insert(z+1);
}
}
int Block::DecidableCell(int c){
dv=c;
return dv;
}
int Block::getvalue(){
std::set<int>::iterator decidedit=candidates.begin() ;
return *decidedit;
}
---------------------------------------------puzzle.h
#ifndef PUZZLE_H
#define PUZZLE_H
#include <Block.h>
#include <set.h>
class Puzzle
{
public:
Puzzle();
bool possible();
int decided;
void output();
void guess(int);
int GetDecided();
void setMap();
int remove(int,int,int);
private:
int number;
Block sudoku[9][9];
int sudokuPosible[9][9];
};
#endif // PUZZLE_H
---------------------------------------------puzzle.cpp
#include <Puzzle.h>
#include <iostream>
using namespace std;
Puzzle::Puzzle()
{
}
void Puzzle::setMap(){
//int decided=0;
for ( int a=0;a<9;a++){
for (int b=0;b<9;b++){
if (!(cin>>number)){
sudokuPosible[a][b]=9;
}
sudoku[a][b].DecidableCell(number);
sudokuPosible[a][b]=0;
}
}
}
int Puzzle::GetDecided(){
int i=0, j=0, s=0;
for (i=0; i<9; i++)
for (j=0; j<9; j++)
if ( sudokuPosible[i][j] == 0)
s++;
return s;
}
bool Puzzle::possible(){
int i,j,a1,a2;
for (int a=0;a<9;a++){
for (int b=0;b<9;b++){
if (sudokuPosible[a][b]==1){
sudokuPosible[a][b]=0;
sudoku[a][b].DecidableCell(sudoku[a][b].getvalue());// not sure
}
if (sudokuPosible[a][b]==0){
int Assure=sudokuPosible[a][b];
//rows
for(j=0;j<9;j++){
if (sudokuPosible[a][j]){
continue;
}
sudoku[a][j].candidates.erase(Assure);
sudokuPosible[a][j]--;
if (sudokuPosible[a][j]==0){
return false;
}
}
//columns
for(i=0;i<9;i++){
if (sudokuPosible[i][b]==0){
continue;
}
sudoku[i][b].candidates.erase(Assure);
sudokuPosible[i][b]--;
if (sudokuPosible[i][b]==0){
return false;
}
}
//grids
a1 = a/3; a2 = b/3;
a1 = a1*3; a2 = a2*3;
for (a1=0; a1<3; a1++)
{
for (a2=0; a2<3; a2++)
{
if (sudokuPosible[a1][a2]==0){
continue;
}
sudoku[a1][a2].candidates.erase(Assure);
sudokuPosible[a1][a2]--;
}
}
if (sudokuPosible[a1][a2]==0){
return false;
}
}
}
}
return true;
}
void Puzzle::guess(int a ){
int q;
int w;
int min=9;
if (a/1){
for (q=0; q<9; q++){
for (w=0; w<9; w++){
if (sudokuPosible[q][w]!=0){
if (sudokuPosible[q][w]< min){
min=sudokuPosible[q][w];
}
}
}
}
sudoku[q][w].candidates.erase(sudoku[q][w].candidates.begin());
sudokuPosible[q][w]--;
}
if (a/2){
sudoku[q][w].DecidableCell( sudoku[q][w].getvalue());
sudokuPosible[q][w]=0;
}
}
void Puzzle::output(){
int oa,ob;
for (oa=0; oa<9; oa++){
for (ob=0; ob<9; ob++){
cout<< sudoku[oa][ob].getvalue();
}
}
}
//#include <iostream>
#include <Puzzle.h>
#include <stack.h>
//using namespace std;
stack <Puzzle> a;
Puzzle p;
Puzzle c;
--------------------------------------------main
int main()
{
int count=0;
a.push(p);
a.top().setMap();
while(!a.empty()){
while(a.top().possible()){
int find=0;
find=a.top().GetDecided();
if(find==81){
count=count+1;
a.top().output();
a.pop();
}
c=p;
a.top().guess(1);
c.guess(2);
a.push(c);
}
}
