ACM竞赛问题——九宫格问题，元素距离问题，扑克算24问题（13L）-『提问交流』-AUTOIT CN

happytc 发表于 2012-4-17 09:21:30

回复 31# pusofalse

呵，这种方法，本质上跟我在30#提的方法其实是一样的。
只是这样产生的数独矩阵作成的九宫图，规律性太强了，解了一个，后的就很容易了。

所以我说很是ws，哈……

魔导发表于 2012-4-17 09:55:55

小弟小学文化，来看看热闹{:face (394):}

seniors 发表于 2012-4-17 10:11:49

看不懂啊，看不懂，慢慢领悟

user3000 发表于 2012-4-17 16:15:22

本帖最后由 user3000 于 2012-4-17 16:48 编辑

一一推翻原来的思路, 看来要好好研究三笑的代码才行了!

user3000 发表于 2012-4-17 19:24:50

脑子不够用了!
静下心来, 看了看P侠的代码, 忽然才发现, 这世界其实很'小'!

whitehead 发表于 2012-4-17 21:19:33

写出解所有数独问题的算法应该很难吧

zch11230 发表于 2012-4-18 01:03:34

P大的太精彩了佩服

happytc 发表于 2012-4-18 05:52:01

写出解所有数独问题的算法应该很难吧
whitehead 发表于 2012-4-17 21:19 http://www.autoitx.com/images/common/back.gif

我在29楼不是已经给出来了嘛
你把所给的数独数组里多改几个非0数字为0，就可以看到可以得到多个答案了。
理论上完全可以得到所有数独的解，只是计算时间就是天文数字了。

不过数学家已经从理论上证明的有多少种数独矩阵了。

其实另外一个问题更有趣：如何产生：给出尽量少的数字情况下的九宫图是唯一解？

3mile 发表于 2012-4-18 09:43:57

回复 39# happytc
正如happytc兄所说,29楼的代码如果是给出全0的数,猜数独的话,是可以出全排列的.
这也就解释了为何如happytc兄所举的例子中Local $array = [, _
                                       , _
                                       , _
                                       , _
                                       , _
                                       , _
                                       , _
                                       , _
                                       ]
第中的6挖去我的代码会出现死循环的结果.
happytc兄的代码是猜数,我的代码是去除不可能的数,happytc兄的代码设计想法非常先进,让人非常佩服.

虽然如此,但还是给出我在6楼代码中的修正代码,仅仅作为论坛留档,避免本地硬盘中文件管理混乱.
#include <array.au3>

$time = TimerInit()
Global $flag_W = 1
Local $k = "1234567890"
;~ Local $array = [,,,,,,,,]

Local $array = [, _
, _
, _
, _
, _
, _
, _
, _
]

$abc = sudoku($array)
_ArrayDisplay($abc, TimerDiff($time))

Func sudoku($array)
Local $str
For $i = 0 To 8;初始化
For $n = 0 To 8
$str &= $array[$i][$n] & "|"
Next

$str_1 = StringRegExpReplace($k, $str, '')
$str = ""
For $n = 0 To 8
If $array[$i][$n] = 0 Then $array[$i][$n] = $str_1
Next
$str_1 = ""
Next
;~ _ArrayDisplay($array)
While 1
;去除行重复
For $i = 0 To 8
Local $str = '', $aabb = ""
For $n = 0 To 8
If StringLen($array[$i][$n]) = 1 Then
$str &= $array[$i][$n] & "|"
EndIf
$aabb &= $array[$i][$n] & "|"
Next

For $n = 0 To 8
If StringLen($array[$i][$n]) > 1 Then
$array[$i][$n] = StringRegExpReplace($array[$i][$n], $str, '')
EndIf
Next

Local $fl =
For $o = 1 To 9
$min = StringRegExp($aabb, $o, 3)
If UBound($min) = 1 Then
_ArrayAdd($fl, $o)
EndIf
Next

For $n = 0 To 8
For $c = 1 To UBound($fl) - 1
If StringInStr($array[$i][$n], $fl[$c]) Then $array[$i][$n] = $fl[$c]
Next
Next
Next

;以下去除列重复
For $i = 0 To 8
Local $str = ''
For $n = 0 To 8
If StringLen($array[$n][$i]) = 1 Then
$str &= $array[$n][$i] & "|"
EndIf
Next

For $n = 0 To 8
If StringLen($array[$n][$i]) > 1 Then
$array[$n][$i] = StringRegExpReplace($array[$n][$i], $str, '')
EndIf
Next
Next

;去除九宫重复
For $i = 0 To 8 Step 3
For $n = 0 To 8 Step 3
Local $temp, $sp = '', $aabb = ""
For $a = 0 To 2
For $b = 0 To 2
If StringLen($array[$a + $i][$b + $n]) = 1 Then $sp &= $array[$a + $i][$b + $n]
Next
Next

For $a = 0 To 2
For $b = 0 To 2
If StringLen($array[$a + $i][$b + $n]) > 1 Then $array[$a + $i][$b + $n] = StringRegExpReplace($array[$a + $i][$b + $n], '[' & $sp & ']', '')
$aabb &= $array[$a + $i][$b + $n] & "|"
Next
Next

Local $fl =
For $o = 1 To 9
$min = StringRegExp($aabb, $o, 3)
If UBound($min) = 1 Then
_ArrayAdd($fl, $o)
EndIf
Next

For $a = 0 To 2
For $b = 0 To 2
For $c = 1 To UBound($fl) - 1
If StringInStr($array[$a + $i][$b + $n], $fl[$c]) Then $array[$a + $i][$b + $n] = $fl[$c]
Next
Next
Next

Next
Next

Local $flag = 0
For $i = 0 To 8
For $n = 0 To 8
If StringLen($array[$i][$n]) > 1 Then $flag = 1
Next
Next
;~ _ArrayDisplay($array)
If $flag = 0 Then ExitLoop
$flag_W += 1
If $flag_W > 10 Then
MsgBox(0,0,"不止一种解,或许条件不完整!")
ExitLoop
            endif
WEnd
Return $array
EndFunc ;==>sudoku

whitehead 发表于 2012-4-18 20:32:49

确实，无论如何只有有限多种可能，理论上计算机是能够求出解的。

kenan 发表于 2012-4-19 04:29:10

睡不着，把这道题做了
同学说用回溯法就可以解决。我一开始怎么就没想到这个呢，还以为是要找出什么规律，每个数字都可以算出来的
c++代码，写得应该很清晰了，au3就不写了#include <iostream>
using namespace std;
bool CanPut(int *a [],int n,int k){
int row=k/9;
int col=k%9;
int i;
for(i=0;i<9;i++){
if(a==n) return false;
if(a==n) return false;
}
row=row/3*3;
col=col/3*3;
for(i=0;i<3;i++)
for(int j=0;j<3;j++)
if(a==n) return false;
return true;
}

void BackTrack(int *a [],int k){
if(k==81) {
for(int i = 0; i < 9; ++i){
for(int j = 0; j < 9; ++j){
cout<< a<<" ";
}
cout<<endl;
}
return;
}
int row=k/9;
int col=k%9;
int i;
if(a==0){
for(i=1;i<=9;i++){
if(CanPut(a,i,k)){
a=i;
BackTrack(a,k+1);
a=0;
}
}
if(a==0){
return;
}
}
BackTrack(a,k+1);
}

int main(){
int **a = new int*;
for(int i = 0; i < 9; ++i){
      a = new int;
      for(int j = 0; j < 9; ++j){
         cin >> a;
      }
}
cout<<endl;
BackTrack(a,0);
return 0;
}
/*
0 6 1 0 3 0 0 2 0
0 5 0 0 0 8 1 0 7
0 0 0 0 0 7 0 3 4
0 0 9 0 0 6 0 7 8
0 0 3 2 0 9 5 0 0
5 7 0 3 0 0 9 0 0
1 9 0 7 0 0 0 0 0
8 0 2 4 0 0 0 6 0
0 4 0 0 1 0 2 5 0
*/

kenan 发表于 2012-4-19 04:53:36

本帖最后由 kenan 于 2012-4-19 14:06 编辑

大清早起来，花上点时间做下这个题

三笑，你的代码可能有问题的或效率低，当把数字多挖几个出去，就 ...
happytc 发表于 2012-4-17 06:25 http://www.autoitx.com/images/common/back.gif

都是回溯法，感觉你写的复杂一点，扫了几眼，没能完全读懂
其实思路很简单，按顺序一个数字一个数字的填，比如，填第一个数字，从1-9中，把1填进去发现能满足要求，那么继续填第二个数字，从1-9中，填1不行，填2不行，继续填3，行了，填第三个数字，从1-9，发现1-9都不能满足要求，那么就回退，重填第二个数字，3不能填，那么填4填5看行不行，如果行了，那就继续填第三个数字。。。。以此类推

MicroBlue 发表于 2012-4-19 18:28:51

看看3mail的答案是什么！

whitehead 发表于 2012-4-20 23:21:07

回复 42# kenan
这就是计算机求解与人脑求解的不同之处。
人脑能用的方法电脑用不了，反之大体一样

页: 1 2 [3]

AUTOIT CN's Archiver