| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 484 人关注过本帖
标题:数独问题的方法,关于栈的使用
只看楼主 加入收藏
taylor0904
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2014-2-10
结帖率:0
收藏
 问题点数:0 回复次数:1 
数独问题的方法,关于栈的使用
数独思想很简单,行列九宫格不能有重复的数字,不过我的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);
         }
    }
搜索更多相关主题的帖子: include 中文 九宫格 格子 
2014-02-10 18:52
taylor0904
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2014-2-10
收藏
得分:0 
我的程序可以run但是什么都没有,我想是我对stack的运用还不行,求请教,我这样的写法是什么地方理解错误了呢?
2014-02-10 18:54
快速回复:数独问题的方法,关于栈的使用
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.021877 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved