解数独算法--C++实现

2024-06-01 13:58
文章标签 算法 c++ 实现 解数

本文主要是介绍解数独算法--C++实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

时间比较仓促,未优化。大牛看客,勿 笑话 。当然有好的建议,我洗耳恭听。若有时间再用MFC写一个界面。
  好了,废话不多说,代码如下:
  #include <iostream>
using namespace std;
//可选数字
int candidate[] = {1,2,3,4,5,6,7,8,9};
//标记这个空格是否为原始数据
int g_a[9][9] = {0};
//打印函数
void print( int (*a)[9] )
{
for( int i = 0; i < 9; i++ )
{
  for( int j = 0; j < 9; j++ )
  {
   cout << a[i][j] << " ";
  }
  cout << endl;
}
cout << endl;
}
//判断可以放哪些数字
void ConfirmCandidate( int (*a)[9], int i, int j )
{
for( int i_candidate = 0; i_candidate < 9; i_candidate++ )
  candidate[i_candidate] = i_candidate+1;
for( int colm = 0; colm < 9; colm++ )
{
  if( a[i][colm] != 0 )
   candidate[a[i][colm]-1] = 0;
}
for( int line = 0; line < 9; line++ )
{
  if( a[line][j] != 0 )
   candidate[a[line][j]-1] = 0;
}
for( int line = i/3*3; line < i/3*3+3; line++ )
{
  for( int colm = j/3*3; colm < j/3*3+3; colm++ )
   if( a[line][colm] != 0 )
    candidate[a[line][colm]-1] = 0;
}
}
//标记每个空格位置
void TotalNumbers( int (*a)[9], int i, int j )
{
for( int line = 0; line < i; line++ )
{
  for( int colm = 0; colm < j; colm++ )
   if( a[line][colm] == 0 )
   {
    g_a[line][colm] = 1;
   }
}
}
//判断所填数字是否正确
bool JudgeValue( int (*a)[9],int i, int j )
{
//同一行有无重复数字
for( int colm = 0; colm < 9; colm++ )
{
  if( a[i][colm] == a[i][j] && j != colm )
   return false;
}
//同一列有无重复数字
for( int line = 0; line < 9; line++ )
{
  if( a[line][j] == a[i][j] && i != line )
   return false;
}
//一个3*3的方格内有无重复数字
for( int line = i/3*3; line < i/3*3+3; line++ )
{
  for( int colm = j/3*3; colm < j/3*3+3; colm++ )
   if( a[line][colm] == a[i][j] && i != line && j != colm )
    return false;
}
return true;
}
//判断是否成功
bool success( int(*a)[9], int i, int j )
{
if( i < 0 || j < 0 ) return false;
int line = i;
int colm = j;
for( ; line < 9; line++, colm = 0 )
{
  for( ; colm < 9; colm++ )
  {
   //cout << "line = " << line <<"  colm = " << colm << endl;
   //if( colm == 8 && line == 8 ) return true;
   if( a[line][colm] != 0 && g_a[line][colm] == 0 ) continue;
   ConfirmCandidate(a, line, colm);
   for(int c = 0; c < 9;  c++  )
   {
    if( candidate[c] > a[line][colm] )
    {
     a[line][colm] = candidate[c];
     /*
     *TEST
     *测试可选数字
     */
     /*
     for(int i = 0; i < 9; i++ )
      cout << candidate[i] << " ";
     cout << endl << endl;
     */
     //print(a);
     //判断放入的值是否正确
     bool bRet = JudgeValue( a, line, colm );
     if(!bRet) 
     {
      //cout << "bRet  is  false" << endl;
     }
     else{
      //cout << "bRet  is  true" << endl;
      break;
     }
    }
    else if( c == 8 && candidate[c] <= a[line][colm] )
    {
     //cout << "line = " << line <<"  colm = " << colm << endl;
     int set_colm = 8;
     a[line][colm] = 0;
     if( colm == 0 )
     {
      while( g_a[line-1][set_colm] == 0)
      {
       if( set_colm == 0) 
       {
        line--;
        set_colm = 8;
       }
       else set_colm--;
      }
      return success( a, line - 1, set_colm);
     }
     else{
      while( g_a[line][colm-1] == 0)
      {
       if( set_colm == 0) 
       {
        line--;
        set_colm = 8;
       }
       else colm--;
      }
      return success( a ,line, colm-1 );
     }
    }
   }
  }
}
return true;

}

http://www.shengshiyouxi.com

  int main()
{
//initialization
int a[9][9] = {
  {8,0,0,0,0,0,0,0,0},
  {0,0,3,6,0,0,0,0,0},
  {0,7,0,0,9,0,2,0,0},
  {0,5,0,0,0,7,0,0,0},
  {0,0,0,0,4,5,7,0,0},
  {0,0,7,1,0,0,0,3,0},
  {0,0,1,0,0,0,0,6,8},
  {0,0,8,5,0,0,0,1,0},
  {0,9,0,0,0,0,4,0,0}
};
   //test
/*
int a[9][9] = {
  {8,0,0,0,0,0,0,0,0},
  {0,0,0,0,0,0,0,0,0},
  {0,0,0,0,0,0,0,0,0},
  {0,0,0,0,0,0,0,0,0},
  {0,0,0,0,0,0,0,0,0},
  {0,0,0,0,0,0,0,0,0},
  {0,0,0,0,0,0,0,6,8},
  {0,0,0,0,0,0,0,0,0},
  {0,0,0,0,0,0,0,0,0}
};
*/ 
TotalNumbers( a, 9, 9 );
success( a, 0, 0 );
print(a);
}

这篇关于解数独算法--C++实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1021206

相关文章

Python实现终端清屏的几种方式详解

《Python实现终端清屏的几种方式详解》在使用Python进行终端交互式编程时,我们经常需要清空当前终端屏幕的内容,本文为大家整理了几种常见的实现方法,有需要的小伙伴可以参考下... 目录方法一:使用 `os` 模块调用系统命令方法二:使用 `subprocess` 模块执行命令方法三:打印多个换行符模拟

SpringBoot+EasyPOI轻松实现Excel和Word导出PDF

《SpringBoot+EasyPOI轻松实现Excel和Word导出PDF》在企业级开发中,将Excel和Word文档导出为PDF是常见需求,本文将结合​​EasyPOI和​​Aspose系列工具实... 目录一、环境准备与依赖配置1.1 方案选型1.2 依赖配置(商业库方案)二、Excel 导出 PDF

Python实现MQTT通信的示例代码

《Python实现MQTT通信的示例代码》本文主要介绍了Python实现MQTT通信的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 安装paho-mqtt库‌2. 搭建MQTT代理服务器(Broker)‌‌3. pytho

使用zip4j实现Java中的ZIP文件加密压缩的操作方法

《使用zip4j实现Java中的ZIP文件加密压缩的操作方法》本文介绍如何通过Maven集成zip4j1.3.2库创建带密码保护的ZIP文件,涵盖依赖配置、代码示例及加密原理,确保数据安全性,感兴趣的... 目录1. zip4j库介绍和版本1.1 zip4j库概述1.2 zip4j的版本演变1.3 zip4

python生成随机唯一id的几种实现方法

《python生成随机唯一id的几种实现方法》在Python中生成随机唯一ID有多种方法,根据不同的需求场景可以选择最适合的方案,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习... 目录方法 1:使用 UUID 模块(推荐)方法 2:使用 Secrets 模块(安全敏感场景)方法

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)

Spring StateMachine实现状态机使用示例详解

《SpringStateMachine实现状态机使用示例详解》本文介绍SpringStateMachine实现状态机的步骤,包括依赖导入、枚举定义、状态转移规则配置、上下文管理及服务调用示例,重点解... 目录什么是状态机使用示例什么是状态机状态机是计算机科学中的​​核心建模工具​​,用于描述对象在其生命

Spring Boot 结合 WxJava 实现文章上传微信公众号草稿箱与群发

《SpringBoot结合WxJava实现文章上传微信公众号草稿箱与群发》本文将详细介绍如何使用SpringBoot框架结合WxJava开发工具包,实现文章上传到微信公众号草稿箱以及群发功能,... 目录一、项目环境准备1.1 开发环境1.2 微信公众号准备二、Spring Boot 项目搭建2.1 创建

IntelliJ IDEA2025创建SpringBoot项目的实现步骤

《IntelliJIDEA2025创建SpringBoot项目的实现步骤》本文主要介绍了IntelliJIDEA2025创建SpringBoot项目的实现步骤,文中通过示例代码介绍的非常详细,对大家... 目录一、创建 Spring Boot 项目1. 新建项目2. 基础配置3. 选择依赖4. 生成项目5.