程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 用C++完成的解數獨(Sudoku)順序

用C++完成的解數獨(Sudoku)順序

編輯:關於C++

用C++完成的解數獨(Sudoku)順序。本站提示廣大學習愛好者:(用C++完成的解數獨(Sudoku)順序)文章只能為提供參考,不一定能成為您想要的結果。以下是用C++完成的解數獨(Sudoku)順序正文


我是一個C++初學者,控制台完成了一個解數獨的小順序。上面粘貼代碼。

  • 我英語沒學好,不會給變量和函數命名。當前還想添加以下功用:

  • 隨機生成數獨
  • 完成解題步驟的輸入
  • 判別數獨能否具有獨一解
  • 圖形化界面

代碼如下:

//"數獨游戲"V1.0
//李國良於2016年11月11日編寫完成

#include <iostream>
#include <fstream>
#include <string>
#include <Windows.h>

using namespace std;

const int ArSize = 9;

string loadFile(int arr[ArSize][ArSize]);//讀取文件,前往文件名
void printMap(int arr[ArSize][ArSize]);//顯示數獨
void solve(int arr[ArSize][ArSize], int enumer[ArSize], int i, int j);//計算以後單元格的候選數
bool solveV(int arr[ArSize][ArSize], int i, int j);//判別以後單元格能否可填
bool lopMap(int arr[ArSize][ArSize]);//循環遍歷未解單元格,調用solveV求解
bool loopMap(int arr[ArSize][ArSize]);//暴力圖解!!!
void saveFile(int arr[ArSize][ArSize], string str);//保管文件

int main()
{
    SetConsoleTitle("數獨游戲");
    int map[ArSize][ArSize];
    for (auto &row : map)
        for (auto &ival : row)
            ival = -1;
    string name = loadFile(map);
    printMap(map);
    bool surplus = lopMap(map);
    cout << "lopMap()解答終了" << endl;
    printMap(map);
    if (!surplus)
    {
        loopMap(map);
        cout << "loopMap()解答終了" << endl;
        printMap(map);
    }
    saveFile(map, name);
    cin.get();
    cin.get();
    return 0;
}

string loadFile(int arr[ArSize][ArSize])
{
    string fileName;
    ifstream inFile;
    cout << "請輸出文件名:" << endl;
    while (true)
    {
        cin >> fileName;
        inFile.open(fileName + ".txt");
        if (!inFile.is_open())
        {
            cout << "文件未能成功翻開,請重新輸出文件名:" << endl;
            continue;
        }
        bool judg = true;
        for (int i = 0; i < ArSize; ++i)
        {
            for (int j = 0; j < ArSize; ++j)
            {
                inFile >> arr[i][j];
                if (arr[i][j] < 0 || arr[i][j] > 9)
                    judg = false;
            }
        }
        if (judg)
        {
            cout << "文件\"" << fileName << ".txt" << "\"載入成功!" << endl;
            inFile.close();
            break;
        }
        else
        {
            cout << "文件內容有誤,請重新輸出文件名:" << endl;
            inFile.close();
            continue;
        }
    }
    return fileName;
}

void printMap(int arr[ArSize][ArSize])
{
    cout << endl;
    int num = 0;
    for (int i = 0; i < ArSize; ++i)
    {
        for (int j = 0; j < ArSize; ++j)
        {
            cout << arr[i][j];
            if (j != 8)
                cout << " ";
            if (!arr[i][j])
                num += 1;
        }
        cout << endl;
    }
    cout << num << "剩余單元格!" << endl << endl;
}

void solve(int arr[ArSize][ArSize], int enumer[ArSize], int i, int j)
{
    for (int num = 0; num < ArSize; ++num)
        enumer[num] = num + 1;
    for (int m = 0; m < ArSize; ++m)
    {
        if (arr[m][j])
            enumer[arr[m][j] - 1] = 0;
    }
    for (int n = 0; n < ArSize; ++n)
    {
        if (arr[i][n])
            enumer[arr[i][n] - 1] = 0;
    }
    for (int m = i / 3 * 3; m < i / 3 * 3 + 3; ++m)
    {
        for (int n = j / 3 * 3; n < j / 3 * 3 + 3; ++n)
        {
            if (arr[m][n])
                enumer[arr[m][n] - 1] = 0;
        }
    }
}

bool solveV(int arr[ArSize][ArSize], int i, int j)
{
    int enumeration[ArSize];
    int ation[ArSize];
    solve(arr, enumeration, i, j);
    int x = 0;
    int y;
    for (int i = 0; i < ArSize; ++i)
    {
        if (enumeration[i])
        {
            y = i;
            x += 1;
        }
    }
    if (x == 1)
    {
        arr[i][j] = enumeration[y];
        return true;
    }
    else
    {
        for (y = 0; y < ArSize; ++y)
        {
            if (enumeration[y])
            {
                for (int m = 0; m < ArSize; ++m)
                {
                    if (arr[m][j] == 0 && m != i)
                    {
                        solve(arr, ation, m, j);
                        if (ation[y])
                        {
                            break;
                        }
                    }
                }
                if (!ation[y])
                {
                    arr[i][j] = enumeration[y];
                    return true;
                }
                for (int n = 0; n < ArSize; ++n)
                {
                    if (arr[i][n] == 0 && n != j)
                    {
                        solve(arr, ation, i, n);
                        if (ation[y])
                        {
                            break;
                        }
                    }
                }
                if (!ation[y])
                {
                    arr[i][j] = enumeration[y];
                    return true;
                }
                bool judge = false;
                for (int m = i / 3 * 3; m < i / 3 * 3 + 3; ++m)
                {
                    for (int n = j / 3 * 3; n < j / 3 * 3 + 3; ++n)
                    {
                        if (arr[m][n] == 0 && (m != i || n != j))
                        {
                            solve(arr, ation, m, n);
                            if (ation[y])
                            {
                                goto label;
                            }
                        }
                    }
                }
                label:
                if (!ation[y])
                {
                    arr[i][j] = enumeration[y];
                    return true;
                }
            }
        }
    }
    return false;
}

bool lopMap(int arr[ArSize][ArSize])
{
    int num = 0;
    while (true)
    {
        int number = 0;
        for (int i = 0; i < ArSize; ++i)
        {
            for (int j = 0; j < ArSize; ++j)
            {
                if (!arr[i][j])
                {
                    if (!solveV(arr, i, j))
                    {
                        number += 1;
                    }
                }
            }
        }
        if (!number || num == number)
        {
            num = number;
            break;
        }
        num = number;
    }
    return num == 0 ? true : false;
}

bool loopMap(int arr[ArSize][ArSize])
{
    for (int i = 0; i < ArSize; ++i)
    {
        for (int j = 0; j < ArSize; ++j)
        {
            if (!arr[i][j])
            {
                int enumer[ArSize];
                solve(arr, enumer, i, j);
                for (int n = 0; n < ArSize; ++n)
                {
                    if (enumer[n])
                    {
                        int maps[ArSize][ArSize];
                        for (int x = 0; x < ArSize; ++x)
                        {
                            for (int y = 0; y < ArSize; ++y)
                            {
                                maps[x][y] = arr[x][y];
                            }
                        }
                        maps[i][j] = enumer[n];
                        if (lopMap(maps))
                        {
                            for (int x = 0; x < ArSize; ++x)
                            {
                                for (int y = 0; y < ArSize; ++y)
                                {
                                    arr[x][y] = maps[x][y];
                                }
                            }
                            return true;
                        }
                        else
                        {
                            bool judge = true;
                            for (int i = 0; i < ArSize; ++i)
                            {
                                for (int j = 0; j < ArSize; ++j)
                                {
                                    if (!maps[i][j])
                                    {
                                        int num = 0;
                                        int enumerat[ArSize];
                                        solve(maps, enumerat, i, j);
                                        for (auto n : enumerat)
                                        {
                                            num += n;
                                        }
                                        if (!num)
                                        {
                                            judge = false;
                                        }
                                    }
                                }
                            }
                            if (judge)
                            {
                                if (loopMap(maps))
                                {
                                    for (int x = 0; x < ArSize; ++x)
                                    {
                                        for (int y = 0; y < ArSize; ++y)
                                        {
                                            arr[x][y] = maps[x][y];
                                        }
                                    }
                                    return true;
                                }
                            }
                        }
                    }
                }
                return false;
            }
        }
    }
}

void saveFile(int arr[ArSize][ArSize], string str)
{
    ofstream outFile;
    outFile.open(str + "answer.txt");
    if (!outFile.is_open())
    {
        cout << "文件保管失敗!" << endl;
        return;
    }
    for (int i = 0; i < ArSize; ++i)
    {
        for (int j = 0; j < ArSize; ++j)
        {
            outFile << arr[i][j];
            if (j != 8)
                outFile << " ";
        }
        outFile << endl;
    }
    cout << "文件\"" << str << "answer.txt" << "\"保管成功!" << endl;
    outFile.close();
}

loopMap()函數運用了遞歸,遞歸函數寫的十分傷腦筋,覺得這個函數寫的不好,目前還沒找到改良的方法,權且能用。


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved