C语言解数独程序的源码

用C语言写的解数独的程序。在linux下测试成功运行。

效果如图:

这是带解的数独,需要填写的部分用数字0代替。

这是程序运行后的效果图。看看,数独已经搞定啦。

程序源码如下:

#include <stdio.h>
#include <stdlib.h>

#define SIZE 9
#define get_low_bit(x) ((~x&(x-1))+1)

struct{
 int left;
 char num;
 char try;
}board[SIZE][SIZE];

int bit2num(int bit)
{
 switch(bit){
 case 1:case 2:
  return bit;
 case 4:
  return 3;
 case 8:
  return 4;
 case 16:
  return 5;
 case 32:
  return 6;
 case 64:
  return 7;
 case 128:
  return 8;
 case 256:
  return 9;
 }
}

void printf_res()
{
 int i, j, k; 

 for(i=0; i<SIZE; i++)
 {
 if(i%3==0)
 {
  for(j=0; j<SIZE*2+4; j++)
  putchar('-');
  putchar('\n');
 } 

 for(j=0; j<SIZE; j++)
 {
  if(j%3==0)
  putchar('|');
  if(board[i][j].num > 0)
  printf("\033[0;31m%2d\033[0m", board[i][j].num);
  else
  printf("%2d", board[i][j].try);
 }
 printf("|\n");
 }
 for(i=0; i<SIZE*2+4; i++)
 putchar('-');
 putchar('\n');
}

void sub(int i, int j, int bit)
{
 int k, m; 

 for(k=0; k<SIZE; k++)
 {
 board[k][j].left &= ~bit;
 board[i][k].left &= ~bit;
 } 

 for(k=i/3*3; k<(i/3+1)*3; k++)
 for(m=j/3*3; m<(j/3+1)*3; m++)
  board[k][m].left &= ~bit;
}

void init()
{
 int i, j; 

 for(i=0; i<SIZE; i++)
 for(j=0; j<SIZE; j++)
  if(board[i][j].num > 0)
  sub(i, j, 1<<(board[i][j].num-1));
  else if(board[i][j].try > 0)
  sub(i, j, 1<<(board[i][j].try-1));
}

void add(int i, int j, int bit)
{
 int k, m;

 for(k=0; k<SIZE; k++)
 {
 board[k][j].left |= bit;
 board[i][k].left |= bit;
 }
 for(k=i/3*3; k<(i/3+1)*3; k++)
 for(m=j/3*3; m<(j/3+1)*3; m++)
  board[k][m].left |= bit;
}

void solve(int pos)
{
 int i=pos/SIZE;
 int j=pos%SIZE;
 int bit, left;

 if(pos == SIZE*SIZE)
 {
 printf_res();
 exit(0);
 }
 if(board[i][j].num > 0)
 solve(pos+1);
 else
 for(left=board[i][j].left; left; left&=(left-1))
 {
  bit = get_low_bit(left);
  sub(i, j, bit);
  board[i][j].try = bit2num(bit);

  solve(pos+1);

  add(i, j, bit);
  board[i][j].try=0;
  init();
 }
}

int main()
{
 int i, j, c;

 for(i=0; i<SIZE; i++)
 for(j=0; j<SIZE; j++)
 {
  while((c=getchar())<'0' || c>'9')
  ;
  board[i][j].num = c-'0';
  board[i][j].try = 0;
  board[i][j].left = 0x0001FF;
 }
 init();
 solve(0);

 return 0;
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • c++递归解数独方法示例

    复制代码 代码如下: #include<iostream> using namespace std; void init();void function(int m); int canplace(int row,int col,int c); void outputresult(); int a[9][9], maxm = 0; int main() {   init(); function(0);  return 0; } void init(){ int i, j; for(i = 0;

  • C语言实现数独游戏的求解

    玩家需要根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行.每一列.每一个同色九宫内的数字均含1-9,不重复. 输入包含9x9的已知数字,空位用0补齐,中间用空格隔开.(输入数独题目确保正确) 输出为输入数独题目的解. 样例输入: 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 0 1 0 0 0 3 0 0 0 1 0 0 0 0 6 8

  • C语言数独游戏的求解方法

    数独游戏的解法: 先将数独分为九个格子,用一个数组将每个小九宫格的候选数存放下来,将候选数挨个放进数独里的空位,如果这一行和这一列都没有这个数字,继续放入下一个,如果不能放入的话就回到上一步继续尝试,直到成功求出数独的解为止: 比如这个数独第一个九宫格的候选数就有1,2,7,8,9,我们需要从1开始放入第一个格子挨个尝试直到8的时候发现剩下的两个格子都不能放入 这个时候我们就要撤回上一个插入的7,发现8仍然不能放入,就继续撤回2,发现8可以放入,就将8放入3号位置,然后将9插入 这个时候我们发现

  • C语言解数独程序的源码

    用C语言写的解数独的程序.在linux下测试成功运行. 效果如图: 这是带解的数独,需要填写的部分用数字0代替. 这是程序运行后的效果图.看看,数独已经搞定啦. 程序源码如下: #include <stdio.h> #include <stdlib.h> #define SIZE 9 #define get_low_bit(x) ((~x&(x-1))+1) struct{ int left; char num; char try; }board[SIZE][SIZE];

  • 微信 小程序前端源码详解及实例分析

    微信小程序前端源码逻辑和工作流 看完微信小程序的前端代码真的让我热血沸腾啊,代码逻辑和设计一目了然,没有多余的东西,真的是大道至简. 废话不多说,直接分析前端代码.个人观点,难免有疏漏,仅供参考. 文件基本结构: 先看入口app.js,app(obj)注册一个小程序.接受一个 object 参数,其指定小程序的生命周期函数等.其他文件可以通过全局方法getApp()获取app实例,进而直接调用它的属性或方法,例如(getApp().globalData) //app.js App({ onLau

  • 详解go中panic源码解读

    panic源码解读 前言 本文是在go version go1.13.15 darwin/amd64上进行的 panic的作用 panic能够改变程序的控制流,调用panic后会立刻停止执行当前函数的剩余代码,并在当前Goroutine中递归执行调用方的defer: recover可以中止panic造成的程序崩溃.它是一个只能在defer中发挥作用的函数,在其他作用域中调用不会发挥作用: 举个栗子 package main import "fmt" func main() { fmt.

  • C语言实现学生管理系统的源码分享

    注意:没有用到数据库使用链表完成此系统! 多文件实现 正式开始 代码都可以直接使用 不想看的,直接复制代码块里面的内容就行! 我用的visual studio 2019   有些使用了 _s  如果是用别的编译器,可以自行修改! 功能介绍 增,删,改,查,退出,保存,以至于格式化! 1.录入学生信息 2.查看录入的学生信息(全部学生信息) 3.修改已录入的学生信息(以学号) 4.删除已录入的学生信息(以学号) 5.保存信息到文件 6.指定查找(以学号) 7.隐藏选项(格式化链表--清空) 'q'

  • Go语言读写锁RWMutex的源码分析

    目录 前言 RWMutex 总览 深入源码 数据结构 RLock() RUnlock() Lock() Unlock() 常见问题 实战一下 前言 在前面两篇文章中 初见 Go Mutex .Go Mutex 源码详解,我们学习了 Go语言 中的 Mutex,它是一把互斥锁,每次只允许一个 goroutine 进入临界区,可以保证临界区资源的状态正确性.但是有的情况下,并不是所有 goroutine 都会修改临界区状态,可能只是读取临界区的数据,如果此时还是需要每个 goroutine 拿到锁依

  • python实现解数独程序代码

    偶然发现linux系统附带的一个数独游戏,打开玩了几把.无奈是个数独菜鸟,以前没玩过,根本就走不出几步就一团浆糊了. 于是就打算借助计算机的强大运算力来暴力解数独,还是很有乐趣的. 下面就记录一下我写解数独程序的一些思路和心得. 一.数独游戏的基本解决方法 编程笼统的来说,就是个方法论.不论什么程序,都必须将问题的解决过程分解成计算机可以实现的若干个简单方法.俗话说,大道至简.对于只能明白0和1的计算机来说,就更需要细分步骤,一步一步的解决问题了. 首先来思考一下解数独的基本概念. 数独横九竖九

  • 小米5s微信跳一跳小程序python源码

    本文实例为大家分享了微信跳一跳小程序python源码,供大家参考,具体内容如下 微信跳一跳小程序小米5s源码python,搭建环境后亲测可用. # coding: utf-8 import os import sys import subprocess import shutil import time import math from PIL import Image, ImageDraw import random import json import re # === 思路 === # 核

  • Python编写一个验证码图片数据标注GUI程序附源码

    做验证码图片的识别,不论是使用传统的ORC技术,还是使用统计机器学习或者是使用深度学习神经网络,都少不了从网络上采集大量相关的验证码图片做数据集样本来进行训练. 采集验证码图片,可以直接使用Python进行批量下载,下载完之后,就需要对下载下来的验证码图片进行标注.一般情况下,一个验证码图片的文件名就是图片中验证码的实际字符串. 在不借助工具的情况下,我们对验证码图片进行上述标注的流程是: 1.打开图片所在的文件夹: 2.选择一个图片: 3.鼠标右键重命名: 4.输入正确的字符串: 5.保存 州

  • Mybatis-plus使用TableNameHandler分表详解(附完整示例源码)

    为什么要分表 Mysql是当前互联网系统中使用非常广泛的关系数据库,具有ACID的特性. 但是mysql的单表性能会受到表中数据量的限制,主要原因是B+树索引过大导致查询时索引无法全部加载到内存.读取磁盘的次数变多,而磁盘的每次读取对性能都有很大的影响. 这时一个简单可行的方案就是分表(当然土豪也可以堆硬件),将一张数据量庞大的表的数据,拆分到多个表中,这同时也减少了B+树索引的大小,减少磁盘读取次数,提高性能. 两种基础分表逻辑 说完了为什么要分表,下面聊聊业务开发中常见的两种基础的分表逻辑.

  • 详解SpringBoot自动配置源码

    一.引导加载自动配置类 @SpringBootApplication注解相当于@SpringBootConfiguration.@EnableAutoConfiguration.@ComponentScan这三个注解的整合 @SpringBootConfiguration 这个注解也使用了@Configuration标注,代表当前是一个配置类 @ComponentScan 包扫描,指定扫描哪些注解 @EnableAutoConfiguration 这个注解也是一个合成注解 @AutoConfig

随机推荐