编程之美之数独求解器的C++实现方法

it2025-06-06 17

编程之美的第一章的第15节。讲的是构造数独。一開始拿到这个问题的确没有思路，只是看了书中的介绍之后，发现原来这个的求解思路和N皇后问题是一致的。可是不知道为啥，反正一開始确实没有想到这个回溯法。知道是用回溯法求解之后。问题就变得easy了非常多。这里我们不打算实现数独的构造。相反的，我们实现一个数独求解器，以后妈妈再也不用操心我的数独了。

当然求解器的思路和构造数独的思路一样。都是回溯法搜索，这里不再过多说明。

程序执行说明： 1.把待求解的数独数据放到in.txt文件里，程序会自己主动读取他，并将解输出到屏幕和out.txt文件里。

2.控制台颜色改变使用了SetConsoleTextAttribute函数。详细使用细节能够參考 C/C++改变控制台输出字体的背景和颜色（windows)

3.关于程序执行时间统计，使用getTickCount()或者clock()都是能够的

执行效果例如以下：红色表示部分就是求解出来的值了>_<~~

依照惯例以下是源代码：

// ================【shudu.h】=========== #pragma once #define N 9 #include <fstream> typedef struct _SearchNode { int row; int col; int data; }SearchNode; class CShuDu { public: CShuDu(); ~CShuDu(); void CreateSolution(); private: bool isOK(int row, int col); void solve(int searchNode_id); void writeFile(int id); void display(int id); void initShudu(); void output(int id); private: int m_shudu[N + 2][N + 1]; bool m_find; int m_solution_id; std::fstream outfile; SearchNode m_searchNode[N * N]; int m_searchLength; }; // =====================【shudu.cpp】================== #include <windows.h> #include "ShuDu.h" #include <stdio.h> #include <string.h> #include <fstream> #include <iostream> CShuDu::CShuDu() { memset(m_shudu, 0, sizeof(m_shudu)); m_find = false; m_solution_id = 0; outfile.open("out.txt", std::ios::out); m_searchLength = 0; memset(m_searchNode, 0, sizeof(m_searchNode)); } CShuDu::~CShuDu() { outfile.close(); } void CShuDu::CreateSolution() { initShudu(); solve(1); } bool CShuDu::isOK(int row, int col) { bool isOK = true; // 列方向检測 for (int i = 1; i != 10; i++) { if (i == row) continue; isOK = (m_shudu[i][col] == m_shudu[row][col]) ? false : true; if (isOK == false) return isOK; } // 行检測 for (int i = 1; i != 10; i++) { if (i == col) continue; isOK = (m_shudu[row][i] == m_shudu[row][col]) ?

false : true; if (isOK == false) return isOK; } // 区域检測 int block_start_row = (row - 1) / 3 * 3 + 1; int block_start_col = (col - 1) / 3 * 3 + 1; for (int i = block_start_row; i != block_start_row + 3; i++) { for (int j = block_start_col; j != block_start_col + 3; j++) { if (i == row && j == col) continue; isOK = (m_shudu[i][j] == m_shudu[row][col]) ? false : true; if (isOK == false) return isOK; } } return isOK; } void CShuDu::solve(int searchNode_id) { if (m_find == true) return; if (m_searchLength + 1 == searchNode_id) { //m_find = true; m_solution_id++; output(m_solution_id); return; } for (int i = 1; i != 10; i++) { int row = m_searchNode[searchNode_id].row; int col = m_searchNode[searchNode_id].col; m_shudu[row][col] = i; if (isOK(row, col)) { solve(searchNode_id + 1); row = m_searchNode[searchNode_id + 1].row; col = m_searchNode[searchNode_id + 1].col; m_shudu[row][col] = 0; } } } void CShuDu::display(int id) { std::cout << "===========================第" << id << "组数独数据=============================" << std::endl; system("title 数独求解器 by zhyh2010 version 1.0"); int search_id = 1; HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE); for (int i = 1; i != 10; i++) { for (int j = 1; j != 10; j++) { if (i == m_searchNode[search_id].row && j == m_searchNode[search_id].col) { SetConsoleTextAttribute(handle, FOREGROUND_INTENSITY | FOREGROUND_RED); search_id++; } else SetConsoleTextAttribute(handle, FOREGROUND_INTENSITY | FOREGROUND_RED | FOREGROUND_BLUE | FOREGROUND_GREEN); std::cout << m_shudu[i][j] << " "; } std::cout << std::endl; } std::cout << std::endl; std::cout << std::endl; SetConsoleTextAttribute(handle, FOREGROUND_INTENSITY); } void CShuDu::writeFile(int id) { outfile << "===========================第" << id << "组数独数据=============================" << std::endl; for (int i = 1; i != 10; i++) { for (int j = 1; j != 10; j++) { outfile << m_shudu[i][j] << " "; } outfile << std::endl; } outfile << std::endl; outfile << std::endl; } void CShuDu::output(int id) { display(id); writeFile(id); //getchar(); } void CShuDu::initShudu() { std::ifstream infile("in.txt"); for (int i = 1; i != 10; i++) { for (int j = 1; j != 10; j++) { infile >> m_shudu[i][j]; if (m_shudu[i][j] == 0) { m_searchLength++; m_searchNode[m_searchLength].row = i; m_searchNode[m_searchLength].col = j; } } } }

// =====================【数独求解器 main.cpp】================== // @ author : zhyh2010 // @ date : 20150624 // @ version : 1.0 // @ description : C++ // =====================【数独求解器】================== #include <stdio.h> #include "ShuDu.h" #include <time.h> void main() { //DWORD t_start = GetTickCount(); auto t = clock(); CShuDu instance; instance.CreateSolution(); //DWORD t_end = GetTickCount(); printf("程序执行时间为 %d ms\n", 1000*static_cast<float>(clock() - t)/CLOCKS_PER_SEC); }

转载于:https://www.cnblogs.com/bhlsheji/p/5260678.html