首页 > 其他分享 >cpp: Sudoku

cpp: Sudoku

时间：2023-07-01 10:23:25浏览次数：82  
标签：Sudoku int ++ num grid cpp col row

 

/*****************************************************************//**
 * \file   ConsoleSudoku.cpp   c++ 14
 * \brief  九宫独数填充游戏
 * from https://github.com/vaithak/Sudoku-Generator
 * \author geovindu
 * \date   July 2023
 *********************************************************************/
// ConsoleSudoku.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>

#define UNASSIGNED 0

using namespace std;


class Sudoku {
private:
    int grid[9][9];
    int solnGrid[9][9];
    int guessNum[9];
    int gridPos[81];
    int difficultyLevel;
    bool grid_status;

public:
    Sudoku();
    Sudoku(string, bool row_major = true);
    void fillEmptyDiagonalBox(int);
    void createSeed();
    void printGrid();
    bool solveGrid();
    string getGrid();
    void countSoln(int& number);
    void genPuzzle();
    bool verifyGridStatus();
    void printSVG(string);

    void printSolveSVG(string);
    void printSolveDataSVG(vector<vector<int>> data,string);
    void calculateDifficulty();
    int  branchDifficultyScore();
    vector<vector<int>> getArr();
        
};

// START: Get grid as string in row major order
string Sudoku::getGrid()
{
    string s = "";
    for (int row_num = 0; row_num < 9; ++row_num)
    {
        for (int col_num = 0; col_num < 9; ++col_num)
        {
            s = s + to_string(grid[row_num][col_num]);
        }
    }

    return s;
}


vector<vector<int>> Sudoku::getArr()
{
    int gg[9][9] = {};
    int row_num = 9;
    int col_num = 9;
    vector<vector<int>> data;    //二维vector
    vector<int> data_row(col_num);   //存放每行数据的一维vecto

    //for (int row_num = 0; row_num < 9; ++row_num)
    //{
    //    for (int col_num = 0; col_num < 9; ++col_num)
    //    {
    //       gg[row_num][col_num]= grid[row_num][col_num];
    //    }
    //}

    for (int i = 0; i < row_num; i++)
    {
        for (int j = 0; j < col_num; j++)
            data_row[j] = grid[i][j];// i + j;     //使用下标对vector赋值时要注意vector容量是否足够
        data.push_back(data_row);
    }


    return data;
}
// END: Get grid as string in row major order


// START: Generate random number
int genRandNum(int maxLimit)
{
    return rand() % maxLimit;
}
// END: Generate random number


// START: Helper functions for solving grid
bool FindUnassignedLocation(int grid[9][9], int& row, int& col)
{
    for (row = 0; row < 9; row++)
    {
        for (col = 0; col < 9; col++)
        {
            if (grid[row][col] == UNASSIGNED)
                return true;
        }
    }

    return false;
}

bool UsedInRow(int grid[9][9], int row, int num)
{
    for (int col = 0; col < 9; col++)
    {
        if (grid[row][col] == num)
            return true;
    }

    return false;
}

bool UsedInCol(int grid[9][9], int col, int num)
{
    for (int row = 0; row < 9; row++)
    {
        if (grid[row][col] == num)
            return true;
    }

    return false;
}

bool UsedInBox(int grid[9][9], int boxStartRow, int boxStartCol, int num)
{
    for (int row = 0; row < 3; row++)
    {
        for (int col = 0; col < 3; col++)
        {
            if (grid[row + boxStartRow][col + boxStartCol] == num)
                return true;
        }
    }

    return false;
}

bool isSafe(int grid[9][9], int row, int col, int num)
{
    return !UsedInRow(grid, row, num) && !UsedInCol(grid, col, num) && !UsedInBox(grid, row - row % 3, col - col % 3, num);
}
// END: Helper functions for solving grid


// START: Create seed grid
void Sudoku::fillEmptyDiagonalBox(int idx)
{
    int start = idx * 3;
    random_shuffle(this->guessNum, (this->guessNum) + 9, genRandNum);
    for (int i = 0; i < 3; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            this->grid[start + i][start + j] = guessNum[i * 3 + j];
        }
    }
}

void Sudoku::createSeed()
{
    /* Fill diagonal boxes to form:
        x | . | .
        . | x | .
        . | . | x
    */
    this->fillEmptyDiagonalBox(0);
    this->fillEmptyDiagonalBox(1);
    this->fillEmptyDiagonalBox(2);

    /* Fill the remaining blocks:
        x | x | x
        x | x | x
        x | x | x
    */
    this->solveGrid(); // TODO: not truly random, but still good enough because we generate random diagonals.

    // Saving the solution grid
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            this->solnGrid[i][j] = this->grid[i][j];
        }
    }
}
// END: Create seed grid


// START: Intialising
Sudoku::Sudoku()
{

    // initialize difficulty level
    this->difficultyLevel = 0;

    // Randomly shuffling the array of removing grid positions
    for (int i = 0; i < 81; i++)
    {
        this->gridPos[i] = i;
    }

    random_shuffle(this->gridPos, (this->gridPos) + 81, genRandNum);

    // Randomly shuffling the guessing number array
    for (int i = 0; i < 9; i++)
    {
        this->guessNum[i] = i + 1;
    }

    random_shuffle(this->guessNum, (this->guessNum) + 9, genRandNum);

    // Initialising the grid
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            this->grid[i][j] = 0;
        }
    }

    grid_status = true;
}
// END: Initialising


// START: Custom Initialising with grid passed as argument
Sudoku::Sudoku(string grid_str, bool row_major)
{
    if (grid_str.length() != 81)
    {
        grid_status = false;
        return;
    }

    // First pass: Check if all cells are valid
    for (int i = 0; i < 81; ++i)
    {
        int curr_num = grid_str[i] - '0';
        if (!((curr_num == UNASSIGNED) || (curr_num > 0 && curr_num < 10)))
        {
            grid_status = false;
            return;
        }

        if (row_major) grid[i / 9][i % 9] = curr_num;
        else          grid[i % 9][i / 9] = curr_num;
    }

    // Second pass: Check if all columns are valid
    for (int col_num = 0; col_num < 9; ++col_num)
    {
        bool nums[10] = { false };
        for (int row_num = 0; row_num < 9; ++row_num)
        {
            int curr_num = grid[row_num][col_num];
            if (curr_num != UNASSIGNED && nums[curr_num] == true)
            {
                grid_status = false;
                return;
            }
            nums[curr_num] = true;
        }
    }

    // Third pass: Check if all rows are valid
    for (int row_num = 0; row_num < 9; ++row_num)
    {
        bool nums[10] = { false };
        for (int col_num = 0; col_num < 9; ++col_num)
        {
            int curr_num = grid[row_num][col_num];
            if (curr_num != UNASSIGNED && nums[curr_num] == true)
            {
                grid_status = false;
                return;
            }
            nums[curr_num] = true;
        }
    }

    // Fourth pass: Check if all blocks are valid
    for (int block_num = 0; block_num < 9; ++block_num)
    {
        bool nums[10] = { false };
        for (int cell_num = 0; cell_num < 9; ++cell_num)
        {
            int curr_num = grid[((int)(block_num / 3)) * 3 + (cell_num / 3)][((int)(block_num % 3)) * 3 + (cell_num % 3)];
            if (curr_num != UNASSIGNED && nums[curr_num] == true)
            {
                grid_status = false;
                return;
            }
            nums[curr_num] = true;
        }
    }

    // Randomly shuffling the guessing number array
    for (int i = 0; i < 9; i++)
    {
        this->guessNum[i] = i + 1;
    }

    random_shuffle(this->guessNum, (this->guessNum) + 9, genRandNum);

    grid_status = true;
}
// END: Custom Initialising


// START: Verification status of the custom grid passed
bool Sudoku::verifyGridStatus()
{
    return grid_status;
}
// END: Verification of the custom grid passed


// START: Printing the grid
void Sudoku::printGrid()
{
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            if (grid[i][j] == 0)
                cout << ".";
            else
                cout << grid[i][j];
            cout << "|";
        }
        cout << endl;
    }

    cout << "\nDifficulty of current sudoku(0 being easiest): " << this->difficultyLevel;
    cout << endl;
}
// END: Printing the grid


// START: Modified Sudoku solver
bool Sudoku::solveGrid()
{
    int row, col;

    // If there is no unassigned location, we are done
    if (!FindUnassignedLocation(this->grid, row, col))
        return true; // success!

    // Consider digits 1 to 9
    for (int num = 0; num < 9; num++)
    {
        // if looks promising
        if (isSafe(this->grid, row, col, this->guessNum[num]))
        {
            // make tentative assignment
            this->grid[row][col] = this->guessNum[num];

            // return, if success, yay!
            if (solveGrid())
                return true;

            // failure, unmake & try again
            this->grid[row][col] = UNASSIGNED;
        }
    }

    return false; // this triggers backtracking

}
// END: Modified Sudoku Solver


// START: Check if the grid is uniquely solvable
void Sudoku::countSoln(int& number)
{
    int row, col;

    if (!FindUnassignedLocation(this->grid, row, col))
    {
        number++;
        return;
    }


    for (int i = 0; i < 9 && number < 2; i++)
    {
        if (isSafe(this->grid, row, col, this->guessNum[i]))
        {
            this->grid[row][col] = this->guessNum[i];
            countSoln(number);
        }

        this->grid[row][col] = UNASSIGNED;
    }

}
// END: Check if the grid is uniquely solvable


// START: Gneerate puzzle
void Sudoku::genPuzzle()
{
    for (int i = 0; i < 81; i++)
    {
        int x = (this->gridPos[i]) / 9;
        int y = (this->gridPos[i]) % 9;
        int temp = this->grid[x][y];
        this->grid[x][y] = UNASSIGNED;

        // If now more than 1 solution , replace the removed cell back.
        int check = 0;
        countSoln(check);
        if (check != 1)
        {
            this->grid[x][y] = temp;
        }
    }
}
// END: Generate puzzle


// START: Printing into SVG file
void Sudoku::printSVG(string path = "")
{
    string fileName = path + "svgHead.txt";
    ifstream file1(fileName.c_str());
    stringstream svgHead;
    svgHead << file1.rdbuf();

    std::cout<<svgHead.str() << endl;

    file1.close();

    string svg="puzzle.svg";
    if (!path.empty())
        svg = path;         

    ofstream outFile(svg); // std::ios::binary
    outFile << svgHead.rdbuf();

    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            cout << grid[i][j]<< endl;
            if (this->grid[i][j] != 0)
            {
                int x = 50 * j + 16;
                int y = 50 * i + 35;

                stringstream text;
                text << "<text x=\"" << x << "\" y=\"" << y << "\" style=\"font-weight:bold\" font-size=\"30px\">" << this->grid[i][j] << "</text>\n";

                outFile << text.rdbuf();
            }
        }
    }

    outFile << "<text x=\"50\" y=\"500\" style=\"font-weight:bold\" font-size=\"15px\">Difficulty Level (0 being easiest): " << this->difficultyLevel << "</text>\n";
    outFile << "</svg>";
    outFile.close();

}


void Sudoku::printSolveSVG(string path = "")
{
    string fileName = path + "svgHead.txt";
    ifstream file1(fileName.c_str());
    stringstream svgHead;
    svgHead << file1.rdbuf();

    std::cout << svgHead.str() << endl;

    file1.close();

    string svg = "puzzle.svg";
    if (!path.empty())
        svg = path;

    ofstream outFile(svg); // std::ios::binary
    outFile << svgHead.rdbuf();

    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            cout << grid[i][j] << endl;
            if (this->grid[i][j] != 0)
            {
                int x = 50 * j + 16;
                int y = 50 * i + 35;

                stringstream text;
                text << "<text x=\"" << x << "\" y=\"" << y << "\" style=\"font-weight:bold\" font-size=\"30px\">" << this->grid[i][j] << "</text>\n";

                outFile << text.rdbuf();
            }
        }
    }

    outFile << "<text x=\"50\" y=\"500\" style=\"font-weight:bold\" font-size=\"15px\">Difficulty Level (0 being easiest): " << this->difficultyLevel << "</text>\n";
    outFile << "</svg>";
    outFile.close();

}

void Sudoku::printSolveDataSVG(vector<vector<int>> data, string path = "")
{

    string fileName = path + "svgHead.txt";
    ifstream file1(fileName.c_str());
    stringstream svgHead;
    
    svgHead << file1.rdbuf();

    std::cout << svgHead.str() << endl;

    file1.close();

    string svg = "puzzle.svg";
    if (!path.empty())
        svg = path;

    ofstream outFile(svg); // std::ios::binary
    outFile << svgHead.rdbuf();

    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            cout << data[i][j] << endl;
            if (data[i][j] != 0)
            {
                int x = 50 * j + 16;
                int y = 50 * i + 35;

                stringstream text;
                text << "<text x=\"" << x << "\" y=\"" << y << "\" style=\"font-weight:bold\" font-size=\"30px\">" << this->grid[i][j] << "</text>\n";

                outFile << text.rdbuf();
            }
        }
    }

    outFile << "<text x=\"50\" y=\"500\" style=\"font-weight:bold\" font-size=\"15px\">Difficulty Level (0 being easiest): " << this->difficultyLevel << "</text>\n";
    outFile << "</svg>";
    outFile.close();

}
// END: Printing into SVG file


// START: Calculate branch difficulty score
int Sudoku::branchDifficultyScore()
{
    int emptyPositions = -1;
    int tempGrid[9][9];
    int sum = 0;

    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            tempGrid[i][j] = this->grid[i][j];
        }
    }

    while (emptyPositions != 0)
    {
        vector<vector<int> > empty;

        for (int i = 0; i < 81; i++)
        {
            if (tempGrid[(int)(i / 9)][(int)(i % 9)] == 0)
            {
                vector<int> temp;
                temp.push_back(i);

                for (int num = 1; num <= 9; num++)
                {
                    if (isSafe(tempGrid, i / 9, i % 9, num))
                    {
                        temp.push_back(num);
                    }
                }

                empty.push_back(temp);
            }

        }

        if (empty.size() == 0)
        {
            cout << "Hello: " << sum << endl;
            return sum;
        }

        int minIndex = 0;

        int check = empty.size();
        for (int i = 0; i < check; i++)
        {
            if (empty[i].size() < empty[minIndex].size())
                minIndex = i;
        }

        int branchFactor = empty[minIndex].size();
        int rowIndex = empty[minIndex][0] / 9;
        int colIndex = empty[minIndex][0] % 9;

        tempGrid[rowIndex][colIndex] = this->solnGrid[rowIndex][colIndex];
        sum = sum + ((branchFactor - 2) * (branchFactor - 2));

        emptyPositions = empty.size() - 1;
    }

    return sum;

}
// END: Finish branch difficulty score


// START: Calculate difficulty level of current grid
void Sudoku::calculateDifficulty()
{
    int B = branchDifficultyScore();
    int emptyCells = 0;

    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            if (this->grid[i][j] == 0)
                emptyCells++;
        }
    }

    this->difficultyLevel = B * 100 + emptyCells;
}
// END: calculating difficulty level

int main(int argc, char const* argv[])
{
    std::cout << "Hello World!涂聚文！geovindu,Geovin Du\n";

    /*
    int grid[9][9] = {
    {0, 0, 0, 0, 0, 9, 0, 5, 0},
    {0, 0, 8, 0, 0, 0, 0, 7, 9},
    {0, 0, 1, 5, 0, 2, 0, 0, 0},
    {3, 0, 0, 0, 1, 0, 5, 0, 7},
    {2, 0, 4, 0, 0, 7, 0, 0, 0},
    {0, 0, 0, 6, 0, 0, 2, 0, 0},
    {0, 0, 0, 0, 7, 0, 3, 4, 0},
    {1, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 3, 0, 0, 5, 6, 0, 0, 0}
    };
    string fileName = "svgHead.txt";
    ifstream file1(fileName.c_str());
    stringstream svgHead;
    svgHead << file1.rdbuf();

    std::cout << svgHead.str() << endl;

    ofstream outFile("puzzle.svg"); // std::ios::binary
    outFile << svgHead.rdbuf();
    
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            if (grid[i][j] != 0)
            {
                int x = 50 * j + 16;
                int y = 50 * i + 35;

                stringstream text;
                text << "<text x=\"" << x << "\" y=\"" << y << "\" style=\"font-weight:bold\" font-size=\"30px\">" << grid[i][j] << "</text>\n";

                outFile << text.rdbuf();
            }
        }
    }

    outFile << "<text x=\"50\" y=\"500\" style=\"font-weight:bold\" font-size=\"15px\">Difficulty Level (0 being easiest): " << 3 << "</text>\n";
    outFile << "</svg>";
    outFile.close();
    */

    // Initialising seed for random number generation
    srand(time(NULL));

    // Creating an instance of Sudoku
    Sudoku* puzzle = new Sudoku();

    // Creating a seed for puzzle generation
    puzzle->createSeed();

    // Generating the puzzle
    puzzle->genPuzzle();

    // Calculating difficulty of puzzle
    puzzle->calculateDifficulty();

    // testing by printing the grid
    puzzle->printGrid();

    // Printing the grid into SVG file
    string rem = "sudokuGen";
    string path = argv[0];
    path = path.substr(0, path.size() - rem.size());
    //puzzle->printSVG(path);
    puzzle->printSVG("");// 生成当前问题图
    cout << "The above sudoku puzzle has been stored in puzzles.svg in current folder\n";

    puzzle->solveGrid(); //解决方案
    puzzle->printGrid();//打印解决方案
    puzzle->printSVG("solvepuzzle.svg");// 生成当前答案问题图 没有生成
    /*
    puzzle->getGrid();
    cout << puzzle->getGrid() << endl;
    cout << puzzle->getArr().size() << endl;
    int row = puzzle->getArr().size();
    int col = puzzle->getArr().size();
    vector<vector<int>> data = puzzle->getArr();
    for (int i = 0; i < row; i++)
        for (int j = 0; j < col; j++)
        {
            if (j < col - 1)
                cout << data[i][j] << "\t";
            else
                cout << data[i][j] << endl;
        }
    puzzle->printSolveDataSVG(data, "sovepuzzle.svg");
    //puzzle->printSolveSVG("sovepuzzle.svg");
    */
    // freeing the memory
    delete puzzle;
    system("pause");
    return 0;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件

　

 

from:

https://github.com/robatron/sudoku.js js
https://github.com/huaminghuangtw/Web-Sudoku-Puzzle-Game js
https://github.com/t-dillon/tdoku c++
https://github.com/MorvanZhou/sudoku python
https://github.com/RutledgePaulV/sudoku-generator python
https://github.com/JoeKarlsson/python-sudoku-generator-solver python
https://github.com/BurnYourPc/Sudoku python
https://github.com/ArjArav98/Sudoku-Solver c++
https://github.com/flyingpeakock/Console_sudoku c++
https://github.com/sfuhrm/sudoku java
https://github.com/basil2style/Sudoku-Pattern-Generator-App java
https://github.com/Yanndroid/Sudoku java
https://github.com/firateski/SudokuLibrary C#
https://github.com/firateski/SudokuGameWindowsForms C#
https://github.com/nayanbunny/Sudoku-CSharp C#
https://github.com/ashplaysbass97/Sudoku C#
https://github.com/Maxhebda/SudokuMaxSolver C#
https://github.com/ilyakom/Sudoku c#
https://github.com/topics/sudoku-generator

　

标签：Sudoku,int,++,num,grid,cpp,col,row
From： https://www.cnblogs.com/geovindu/p/17518904.html

相关文章

  • cpp: Two-level pointer and double dimensional array
    /*****************************************************************//***\fileConsoleTextFileDemoApp.cppc++14*\brief***\authorgeovindu*\dateJune2023*********************************************************************/......
  • cpp condition_variable wait_for unique_mutex,chrono::seconds
    #include<chrono>#include<condition_variable>#include<ctime>#include<fstream>#include<future>#include<iomanip>#include<iostream>#include<thread>#include<uuid/uuid.h>#include<vector......
  • cppchecker简单介绍和原理初窥
    1.概述：c/c++代码静态分析工具，用于检查编译器难以觉察的bug，其设计目标是没有漏报2.准确率：不能包治百病，但配合testing、instrumenting，可以极大减少bug3.检查内容：64位兼容性自动变量生存周期检查数组越界检查类检查，包括缺少构造函数，变量在构造函数中是否初始化及其初始化顺......
  • findstr /s "AttachedDevice" *.cpp
    findstr/s"AttachedDevice"*.cppchapter22\FileFilter\DriverEntry.cpp:     if(!fido->AttachedDevice||(fido->AttachedDevice->Flags&DO_POWER_PAGABLE))chapter22\FileFilter\DriverEntry.cpp: PDEVICE_OBJECTldo=......
  • strDivide2.cpp字符串划分
    //strDivide2.cpp:Definestheentrypointfortheconsoleapplication.//#include"stdafx.h"#include"string.h"/*s为bwe@#$at111YYY*oo那么func(s)将打印atbweooYYY★树★(240028358)21:07:57先挑字母，再排序吧国嵌唐老师(22134670)21:21:25我来说说......
  • lower_bound upper_bound in cpp
    upper_boundReturnsaniteratorpointingtothefirstelementintherange[first,last)whichcomparesgreaterthanval.ReturnvalueAniteratortotheupperboundpositionforvalintherange.Ifnoelementintherangecomparesgreaterthanval,the......
  • cpp: Interpreter Pattern
     /*****************************************************************//***\fileDuSimple.h*\briefInterpreterPattern解释器模式C++14*2023年6月10日涂聚文GeovinDuVisualStudio2022edit.*\authorgeovindu*\dateJune2023**********......
  • 【八股cover#2】CPP语法 Q&A与知识点
    CPP语法Q&A与知识点简历cover1、熟练使用C的指针应用及内存管理指针与引用的区别指针是一个存储地址的变量，可以有多级，可以为空，并且在初始化后可以改变指向；引用是原变量的别名，只有一级，不能为NULL，必须在定义时初始化，并且一旦初始化后就不能再改变。指针在作为参数传递时不会......
  • cppcheck代码扫描安装及使用
    一、 简介& 官网简介：CppCheck是一个静态代码检查工具,支持c/c++代码;作为编译器的一种补充检查,CppCheck对产品的源代码执行严格的逻辑检查。官网：http://cppcheck.net 二、安装环境安装gcc/g++  sudoapt-getinstallgccg++三、编译unzipcppcheck-......
  • cpp: Memento Pattern
     /*****************************************************************//***\fileActorMemento.h*\brief备忘录模式MementoPattern亦称：快照、Snapshot、MementoC++14*2023年6月6日涂聚文GeovinDuVisualStudio2022edit.*\authorgeovindu*\da......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99