解数独算法--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

相关文章

mybatis执行insert返回id实现详解

《mybatis执行insert返回id实现详解》MyBatis插入操作默认返回受影响行数,需通过useGeneratedKeys+keyProperty或selectKey获取主键ID,确保主键为自... 目录 两种方式获取自增 ID:1. ​​useGeneratedKeys+keyProperty(推

Spring Boot集成Druid实现数据源管理与监控的详细步骤

《SpringBoot集成Druid实现数据源管理与监控的详细步骤》本文介绍如何在SpringBoot项目中集成Druid数据库连接池,包括环境搭建、Maven依赖配置、SpringBoot配置文件... 目录1. 引言1.1 环境准备1.2 Druid介绍2. 配置Druid连接池3. 查看Druid监控

Linux在线解压jar包的实现方式

《Linux在线解压jar包的实现方式》:本文主要介绍Linux在线解压jar包的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux在线解压jar包解压 jar包的步骤总结Linux在线解压jar包在 Centos 中解压 jar 包可以使用 u

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL

C++ Log4cpp跨平台日志库的使用小结

《C++Log4cpp跨平台日志库的使用小结》Log4cpp是c++类库,本文详细介绍了C++日志库log4cpp的使用方法,及设置日志输出格式和优先级,具有一定的参考价值,感兴趣的可以了解一下... 目录一、介绍1. log4cpp的日志方式2.设置日志输出的格式3. 设置日志的输出优先级二、Window

Qt使用QSqlDatabase连接MySQL实现增删改查功能

《Qt使用QSqlDatabase连接MySQL实现增删改查功能》这篇文章主要为大家详细介绍了Qt如何使用QSqlDatabase连接MySQL实现增删改查功能,文中的示例代码讲解详细,感兴趣的小伙伴... 目录一、创建数据表二、连接mysql数据库三、封装成一个完整的轻量级 ORM 风格类3.1 表结构

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片,默认是输出到项目文件夹中,可以自己选择其他的文件夹,选择需要拆分的行数和列数,可以通过

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表(即列表中包含列表)转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert

Python使用pip工具实现包自动更新的多种方法

《Python使用pip工具实现包自动更新的多种方法》本文深入探讨了使用Python的pip工具实现包自动更新的各种方法和技术,我们将从基础概念开始,逐步介绍手动更新方法、自动化脚本编写、结合CI/C... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核