基于SAT的數(shù)獨游戲求解程序，求C語言代碼

用0代表要填的數(shù)

創(chuàng)新互聯(lián)公司是一家專業(yè)提供夏津企業(yè)網(wǎng)站建設(shè),專注與成都做網(wǎng)站、成都網(wǎng)站建設(shè)、H5建站、小程序制作等業(yè)務(wù)。10年已為夏津眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站建設(shè)公司優(yōu)惠進(jìn)行中。

#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 16:

case 256:

return 9;

基礎(chǔ)解法

排除法（摒除法）

摒除法：用數(shù)字去找單元內(nèi)唯一可填空格，稱為摒除法，數(shù)字可填唯一空格稱為排除法 (Hidden Single)。

根據(jù)不同的作用范圍，摒余解可分為下述三種：

數(shù)字可填唯一空格在「宮」單元稱為宮排除（Hidden Single in Box），也稱宮摒除法。

數(shù)字可填唯一空格在「行」單元稱為行排除法（Hidden Single in Row），也稱行摒除法。

Java數(shù)獨游戲代碼

public class ShuDu {

/**存儲數(shù)字的數(shù)組*/

static int[][] n = new int[9][9];

/**生成隨機(jī)數(shù)字的源數(shù)組，隨機(jī)數(shù)字從該數(shù)組中產(chǎn)生*/

static int[] num = {1,2,3,4,5,6,7,8,9};

public static void main(String[] args) {

//生成數(shù)字

for(int i = 0;i 9;i++){

//嘗試填充的數(shù)字次數(shù)

int time = 0;

//填充數(shù)字

for(int j = 0;j 9;j++){

//產(chǎn)生數(shù)字

n[i][j] = generateNum(time);

//如果返回值為0，則代表卡住，退回處理

//退回處理的原則是：如果不是第一列，則先倒退到前一列，否則倒退到前一行的最后一列

if(n[i][j] == 0){

//不是第一列，則倒退一列

if(j 0){

j-=2;

continue;

}else{//是第一列，則倒退到上一行的最后一列

i--;

j = 8;

continue;

}

}

//填充成功

if(isCorret(i,j)){

//初始化time，為下一次填充做準(zhǔn)備

time = 0;

}else{ //繼續(xù)填充

//次數(shù)增加1

time++;

//繼續(xù)填充當(dāng)前格

j--;

}

}

}

//輸出結(jié)果

for(int i = 0;i 9;i++){

for(int j = 0;j 9;j++){

System.out.print(n[i][j] + " ");

}

System.out.println();

}

}

/**

* 是否滿足行、列和3X3區(qū)域不重復(fù)的要求

* @param row 行號

* @param col 列號

* @return true代表符合要求

*/

public static boolean isCorret(int row,int col){

return (checkRow(row) checkLine(col) checkNine(row,col));

}

/**

* 檢查行是否符合要求

* @param row 檢查的行號

* @return true代表符合要求

*/

public static boolean checkRow(int row){

for(int j = 0;j 8;j++){

if(n[row][j] == 0){

continue;

}

for(int k =j + 1;k 9;k++){

if(n[row][j] == n[row][k]){

return false;

}

}

}

return true;

}

/**

* 檢查列是否符合要求

* @param col 檢查的列號

* @return true代表符合要求

*/

public static boolean checkLine(int col){

for(int j = 0;j 8;j++){

if(n[j][col] == 0){

continue;

}

for(int k =j + 1;k 9;k++){

if(n[j][col] == n[k][col]){

return false;

}

}

}

return true;

}

/**

* 檢查3X3區(qū)域是否符合要求

* @param row 檢查的行號

* @param col 檢查的列號

* @return true代表符合要求

*/

public static boolean checkNine(int row,int col){

//獲得左上角的坐標(biāo)

int j = row / 3 * 3;

int k = col /3 * 3;

//循環(huán)比較

for(int i = 0;i 8;i++){

if(n[j + i/3][k + i % 3] == 0){

continue;

}

for(int m = i+ 1;m 9;m++){

if(n[j + i/3][k + i % 3] == n[j + m/3][k + m % 3]){

return false;

}

}

}

return true;

}

/**

* 產(chǎn)生1-9之間的隨機(jī)數(shù)字

* 規(guī)則：生成的隨機(jī)數(shù)字放置在數(shù)組8-time下標(biāo)的位置，隨著time的增加，已經(jīng)嘗試過的數(shù)字將不會在取到

* 說明：即第一次次是從所有數(shù)字中隨機(jī)，第二次時從前八個數(shù)字中隨機(jī)，依次類推，

* 這樣既保證隨機(jī)，也不會再重復(fù)取已經(jīng)不符合要求的數(shù)字，提高程序的效率

* 這個規(guī)則是本算法的核心

* @param time 填充的次數(shù)，0代表第一次填充

* @return

*/

public static int generateNum(int time){

//第一次嘗試時，初始化隨機(jī)數(shù)字源數(shù)組

if(time == 0){

for(int i = 0;i 9;i++){

num[i] = i + 1;

}

}

//第10次填充，表明該位置已經(jīng)卡住，則返回0，由主程序處理退回

if(time == 9){

return 0;

}

//不是第一次填充

//生成隨機(jī)數(shù)字，該數(shù)字是數(shù)組的下標(biāo)，取數(shù)組num中該下標(biāo)對應(yīng)的數(shù)字為隨機(jī)數(shù)字

int ranNum = (int)(Math.random() * (9 - time));

//把數(shù)字放置在數(shù)組倒數(shù)第time個位置，

int temp = num[8 - time];

num[8 - time] = num[ranNum];

num[ranNum] = temp;

//返回數(shù)字

return num[8 - time];

}

}

數(shù)獨設(shè)計思路及全解

開始的話：這個程序現(xiàn)在還不穩(wěn)定，有時出現(xiàn)運(yùn)行時錯誤，跟蹤是由于vector的size()方法引起的。調(diào)試發(fā)現(xiàn)中間的min_seq并沒有完全按照作者的意圖變化。

運(yùn)行時，如果出現(xiàn)錯誤，就反復(fù)運(yùn)行，運(yùn)行成功即可出現(xiàn)一個正確的9*9數(shù)獨矩陣。

如果要玩預(yù)先填充一些數(shù)的游戲，只需修改初始矩陣即可。

算法：為每個位置定義一個可選元素集合，每個更新是把它所在的行，列,所在的3×3方陣中已出現(xiàn)的元素從集合中去掉。填充時，從最小候選集合中選一個(可隨即)填進(jìn)去，更新候選集合，再填充，直到所有位置填充完畢，游戲結(jié)束。

/*******9×9數(shù)獨游戲的計算機(jī)程序*******/

/*******作者：xiaocui******************/

/*******時間：2006.6.23****************/

/*******版本：v1.0*********************/

/*******算法思想***********************/

/******對每個位置的元素，考慮其可選取的數(shù)字

的集合，每次把候選元素個數(shù)最小的那個位置填充

從該最小候選集合中隨機(jī)選取一個元素填充，重復(fù)

這個過程，直到所有元素填充完畢************/

/****適用填充全空的數(shù)獨方格 和 填充已有一些數(shù)的數(shù)獨方格*****/

/****對初始化的候選集的第一次更新正是為了解決第2類數(shù)獨游戲***/

/****對于已填充一部分元素的，直接修改MATRIX矩陣即可*****/

/****數(shù)獨游戲的結(jié)果不止一種********/

#include iostream

#include ctime

#include vector

using namespace std;

/**********初始9×9的矩陣*************/

/******元素為0，說明該位置還未填充***/

int MATRIX[9][9]={ {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,0,0,0},

{0,0,0,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0} };

/*******初始給出的元素個數(shù)***********/

int INITIAL_COUNT;

/********已填充元素個數(shù)，作為填充結(jié)束標(biāo)志**********/

int FINISH_COUNT=0;

/********各個元素的初始候選集合*******/

vectorvectorint IVEC(81);

/**************函數(shù)原型******************/

/*********得到初始給出的元素個數(shù)*******/

int get_initialcount();

/*******初始化候選集合***************/

void initial_candidate();

/***********從vector中刪除指定元素*******/

void delete_value(vectorint ivec,int value);

/********更新候選集合**************/

void refresh_candidate();

/*********返回9×9候選集合元素最少的候選集合序號*******/

int min_seq();

/********隨機(jī)生成一個位置序號并取得該序號所對應(yīng)的元素值******/

int choose_seq(int min_seq);

/*******填充該元素并判斷是否填充完畢********/

int is_finish(int min_seq, int choose_value);

int main()

{

/******得到初始給出的元素個數(shù)*****/

INITIAL_COUNT=get_initialcount();

/******初始化候選集合*******/

initial_candidate();

/********先更新候選集合(為了應(yīng)付已經(jīng)填充一部分?jǐn)?shù)的情況)******/

refresh_candidate();

int i;

int MinSeq;

int ChooseValue;

MinSeq=min_seq();

ChooseValue=choose_seq(MinSeq);

while(is_finish(MinSeq,ChooseValue)!=1)

{

refresh_candidate();

MinSeq=min_seq();

ChooseValue=choose_seq(MinSeq);

}

/**********輸出填好的數(shù)獨游戲結(jié)果*********/

for( i=0;i9;++i)

{

for(int j=0;j9;++j)

{

coutMATRIX[i][j]'\t';

}

coutendl;

}

return 0;

}

/*******************函數(shù)定義***********************/

/*********得到初始給出的元素個數(shù)*******/

int get_initialcount()

{

int count=0;

for(int i=0;i9;++i)

{

for(int j=0;j9;++j)

{

if(MATRIX[i][j]!=0)

{

count++;

}

}

}

return count;

}

/*******初始化候選集合***************/

void initial_candidate()

{

for(int i=0;i81;++i)

{

for(int j=1;j10;++j)

{

IVEC[i].push_back(j);

}

}

}

/***********從vector中刪除指定元素*******/

void delete_value(vectorint ivec,int value)

{

/*******如果ivec已經(jīng)為空，直接退出**********/

if (ivec.size()==0)

{

return;

}

vectorint::iterator iter=ivec.begin();

while( iterivec.end() (*iter)!=value )

{

iter++;

}

if(iterivec.end())//在vector中找到已填充的元素，把它刪除

{

ivec.erase(iter);

}

}

/********更新候選集合**************/

void refresh_candidate()

{

int i;

int rownum,colnum;

int row,col;

/******更新81個vector*******/

for(i=0;i81;++i)

{

row=i/9;

col=i%9;

if(MATRIX[row][col]!=0)//該位置已經(jīng)填充

{

if(IVEC[i].size()!=0)//該vector不空

{

/********刪除整個候選集***********/

IVEC[i].erase(IVEC[i].begin(),IVEC[i].end());

}

}

else

{

/*****刪除同一行中的元素****/

for(colnum=0;colnum9;++colnum)

{

delete_value(IVEC[i],MATRIX[row][colnum]);

}

/*****刪除同一列中的元素****/

for(rownum=0;rownum9;++rownum)

{

delete_value(IVEC[i],MATRIX[rownum][col]);

}

/*****刪除在一個3×3方陣中的元素******/

/******在第1塊中，刪除3×3方陣元素*****/

if(row/3==0 col/3==0)

{

for(int r=0;r3;++r)

{

for(int c=0;c3;++c)

{

delete_value(IVEC[i],MATRIX[r][c]);

}

}

}

/******在第2塊中，刪除3×3方陣元素*****/

if(row/3==0 col/3==1)

{

for(int r=0;r3;++r)

{

for(int c=3;c6;++c)

{

delete_value(IVEC[i],MATRIX[r][c]);

}

}

}

/******在第3塊中，刪除3×3方陣元素*****/

if(row/3==0 col/3==2)

{

for(int r=0;r3;++r)

{

for(int c=6;c9;++c)

{

delete_value(IVEC[i],MATRIX[r][c]);

}

}

}

/******在第4塊中，刪除3×3方陣元素*****/

if(row/3==1 col/3==0)

{

for(int r=3;r6;++r)

{

for(int c=0;c3;++c)

{

delete_value(IVEC[i],MATRIX[r][c]);

}

}

}

/******在第5塊中，刪除3×3方陣元素*****/

if(row/3==1 col/3==1)

{

for(int r=3;r6;++r)

{

for(int c=3;c6;++c)

{

delete_value(IVEC[i],MATRIX[r][c]);

}

}

}

/******在第6塊中，刪除3×3方陣元素*****/

if(row/3==1 col/3==2)

{

for(int r=3;r6;++r)

{

for(int c=6;c9;++c)

{

delete_value(IVEC[i],MATRIX[r][c]);

}

}

}

/******在第7塊中，刪除3×3方陣元素*****/

if(row/3==2 col/3==0)

{

for(int r=6;r9;++r)

{

for(int c=0;c3;++c)

{

delete_value(IVEC[i],MATRIX[r][c]);

}

}

}

/******在第8塊中，刪除3×3方陣元素*****/

if(row/3==2 col/3==1)

{

for(int r=6;r9;++r)

{

for(int c=3;c6;++c)

{

delete_value(IVEC[i],MATRIX[r][c]);

}

}

}

/******在第9塊中，刪除3×3方陣元素*****/

if(row/3==2 col/3==2)

{

for(int r=6;r9;++r)

{

for(int c=6;c9;++c)

{

delete_value(IVEC[i],MATRIX[r][c]);

}

}

}

}

}

}

/*********返回9×9候選集合元素最少的候選集合序號*******/

int min_seq()

{

int count[81];

int i;

for(i=0;i81;++i)

{

count[i]=IVEC[i].size();

}

int value=10;

int min_seq;

for(i=0;i81;++i)

{

if(count[i]==0)

{

continue;

}

if(count[i]value)

{

value=count[i];

min_seq=i;

}

}

return min_seq;

}

/********隨機(jī)生成一個位置序號并取得該序號所對應(yīng)的元素值******/

int choose_seq(int min_seq)

{

/*****根據(jù)當(dāng)前時間設(shè)置種子******/

srand((unsigned)time( NULL ));

int random_seq=rand()%(IVEC[min_seq].size());

return IVEC[min_seq][random_seq];

}

/*******填充該元素并判斷是否填充完畢********/

int is_finish(int min_seq, int choose_value)

{

int row, column;

row=min_seq/9;

column=min_seq%9;

MATRIX[row][column]=choose_value;

FINISH_COUNT++; /****已填充元素個數(shù)加1*****/

/*******填充完畢判斷********/

if(FINISH_COUNT==81-INITIAL_COUNT)

{

return 1;

}

else

{

return 0;

}

}

希望對你有幫助！！

c++或java 寫一個解3階數(shù)獨的程序

123456789101112131415161718192021public static Geocache[] createGeocaches(int a) { if(a = 0) return new Geocache[0]; Random rand = new Random(); Geocache[] result = new Geocache[a]; for(int i = 0; i a; i++) { //因為題目沒有描述，這里假設(shè)x, y是隨機(jī)整數(shù)，Geocache有a href=";tn=44039180_cprfenlei=mv6quAkxTZn0IZRqIHckPjm4nH00T1dhrjIWn1D4n19hmWDzm1R0IAYqnWm3PW64rj0d0AP8IA3qPjfsn1bkrjKxmLKz0ZNzUjdCIZwsrBtEXh9GuA7EQhF9pywdQhPEUiqkIyN1IA-EUBtkPWm4rjR4rHbLPWR1nH63P16L" target="_blank" class="baidu-highlight"構(gòu)造函數(shù)/a(int, int) int x = rand.nextInt(); int y = rand.nextInt(); result[i] = new Geocache(x, y); } return result; }

求數(shù)獨高級解法

知道RStudio嗎，隨便填一個題目格式如下

8--------

--36-----

-7--9-2--

-5---7---

----457--

---1---3-

--1----68

--85---1-

-9----4--

存為sudo.txt

然后安裝名為sudoku的package，運(yùn)行下面的代碼

install.packages("sudoku")

library(sudoku)

s - readSudoku("D:/sudoku.txt")

solveSudoku(s)

一共就兩行代碼，難一點的數(shù)獨也不過10多秒吧就能解決。。。

當(dāng)然這樣就失去了做數(shù)獨的樂趣了，不過當(dāng)有人問你的時候，這個絕對是裝逼神器