数独解题程序源码

code by ssins

#include<iostream>
using namespace std;

struct Board
{
    int grid[9][9];
    int topX, topY;
};

Board myBoard;
//int grid[9][9];

void InitGrid(Board& board);
int PreGrid(Board& board);
bool Maybe(Board& board, int I, int J, int V);
bool sloveBoard(Board& board);

void printMessage()
{
    cout << "输入格式：\n123------\n---456---\n------789\n---------\n---------\n---------\n---------\n---------\n---------\n";
    cout << endl << "输入题目：" << endl;
}


int main()
{
    printMessage();
    InitGrid(myBoard);
    cout << endl;
    if (sloveBoard(myBoard))
    {
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                cout << myBoard.grid[i][j];
                if (j % 3 == 2)
                {
                    cout << "|";
                }
                else
                {
                    cout << " ";
                }
            }
            cout << endl;
            if (i % 3 == 2)
            {
                cout << "--------------------" << endl;
            }
        }
    }
    else
    {
        cout << "error" << endl;
    }

    system("pause");
    return 0;
}

//返回board能否得到正确解
bool sloveBoard(Board& board)
{
    Board tmpBoard = board;
    int ans = PreGrid(tmpBoard);
    if (ans < 0)
    {
        return false;
    }
    if (ans == 1)
    {
        board = tmpBoard;
        return sloveBoard(board);
    }
    if (ans == 2)
    {
        board = tmpBoard;
        return true;
    }
    if(ans == 0)
    {
        int V = tmpBoard.grid[tmpBoard.topX][tmpBoard.topY];
        while (V > 0)
        {
            int testV = V % 10;
            V /= 10;
            Board ttBoard = tmpBoard;
            ttBoard.grid[tmpBoard.topX][tmpBoard.topY] = testV;
            if (sloveBoard(ttBoard))
            {
                board = ttBoard;
                return true;
            }
        }
        return false;
    }
    return false;
}

//读入题目
void InitGrid(Board& board)
{
    int readNum = 0;
    while (readNum < 81)
    {
        char c;
        cin >> c;
        if (c > '0' && c <= '9')
        {
            board.grid[readNum / 9][readNum % 9] = (int)(c - '0');
        }
        else if (c == '-' || c == '0')
        {
            board.grid[readNum / 9][readNum % 9] = 0;
        }
        else
        {
            continue;
        }
        readNum++;
    }
}

/*
-1：错误
0：完成预填
1：预填因出现确定格子而终止
2：没有格子可以预填（完成数独）
*/
int PreGrid(Board& board)
{
    int initDate = 1300000000;
    int minGridValue = initDate;
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            if (board.grid[i][j] > 0 && board.grid[i][j] < 10)
            {
                if (!Maybe(board, i, j, board.grid[i][j]))
                    return -1;
                continue;
            }
            else
            {
                board.grid[i][j] = 0;
                for (int t = 1; t < 10; t++)
                {
                    if (Maybe(board,i, j, t))
                    {
                        board.grid[i][j] *= 10;
                        board.grid[i][j] += t;
                    }
                }
                if (board.grid[i][j] > 0 && board.grid[i][j] < 10)
                {
                    return 1;
                }
                else if (board.grid[i][j] <= 0)
                {
                    return -1;
                }
                else
                {
                    if (board.grid[i][j] < minGridValue)
                    {
                        minGridValue = board.grid[i][j];
                        board.topX = i;
                        board.topY = j;
                    }
                }
            }
        }
    }
    if (minGridValue == initDate)
    {
        return 2;
    }
    else
    {
        return 0;
    }
}

//返回board中坐标（I,J）位置是否可能为值V，可能返回true，不可能返回false
bool Maybe(Board& board,int I, int J, int V)
{
    int baseX = I- I % 3;
    int baseY = J- J % 3;
    for (int s = 0; s < 9; s++)
    {
        if (s != I && board.grid[s][J] == V)
        {
            return false;
        }
        if (s != J && board.grid[I][s] == V)
        {
            return false;
        }
        int dltX = s / 3;
        int dltY = s % 3;
        if (((baseX + dltX) != I || (baseY + dltY) != J) && board.grid[baseX + dltX][baseY + dltY] == V)
        {
            return false;
        }
    }
    return true;
}