ACM竞赛问题——九宫格问题，元素距离问题，扑克算24问题（13L）

happytc

回复 31# pusofalse


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

所以我说很是ws，哈……

魔导

小弟小学文化，来看看热闹

seniors

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

user3000

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

user3000

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

whitehead

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

zch11230

P大的太精彩了  佩服

happytc

写出解所有数独问题的算法应该很难吧
whitehead 发表于 2012-4-17 21:19

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

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

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

3mile

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

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

#include <array.au3>

$time = TimerInit()
Global $flag_W = 1
Local $k = "1234567890"
;~ Local $array[9][9] = [[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]]

Local $array[9][9] = [[0, 6, 0, 0, 4, 0, 9, 0, 3], _
                [0, 7, 0, 0, 8, 5, 0, 1, 0], _
                [4,0,1,7,0,0,0,0,2], _
                [0,9,0,0,5, 0, 0, 6,4], _
                [0, 4, 0, 8, 9, 0, 0, 5, 0], _
                [1, 8, 0, 0, 0, 4, 0, 9, 0], _
                [3, 0, 0, 0, 0, 8, 7, 0, 5], _
                [0, 1, 0, 5, 7, 0, 0, 2, 0], _
                [7, 0, 9, 0, 2, 0, 0, 3, 0]]

$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[1] = [0]
                        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[3][3], $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[1] = [0]
                                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

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

kenan

睡不着，把这道题做了
同学说用回溯法就可以解决。我一开始怎么就没想到这个呢，还以为是要找出什么规律，每个数字都可以算出来的
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[row][i]==n) return false;
                if(a[i][col]==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[row+i][col+j]==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[i][j]<<" ";
                         }
                         cout<<endl;
                 }
                return;
        }
        int row=k/9;
        int col=k%9;
        int i;
        if(a[row][col]==0){
                for(i=1;i<=9;i++){
                        if(CanPut(a,i,k)){
                                a[row][col]=i;
                                BackTrack(a,k+1);
                                a[row][col]=0;
                        }
                }
                if(a[row][col]==0){
                        return;
                }
        }
        BackTrack(a,k+1);
}

int main(){
     int **a = new int*[9];
     for(int i = 0; i < 9; ++i){
         a[i] = new int[9];
         for(int j = 0; j < 9; ++j){
             cin >> a[i][j];
         }
     }
        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

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

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

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

MicroBlue

看看3mail的答案是什么！

whitehead

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