来玩数独吧，抛砖引玉

以前没有学过ruby，这回练练手，用ruby写了一个“出数独题”的小程序。抛砖引玉，看看有没有解数独题的算法被引出来 

Table=Array.new(9)

def getNumber(a)
  return nil if a.length==0
  sum=a.length*10
  l=rand(sum)/10
  return a[l]
end

def setTable(i,j)
  if Table[i][j].class==Fixnum
    0.upto(8) {|pos| Table[i][pos].delete(Table[i][j]) if Table[i][pos].class==Array}
    0.upto(8) {|pos| Table[pos][j].delete(Table[i][j]) if Table[pos][j].class==Array}
    i1=6 if i<9
    i1=3 if i<6
    i1=0 if i<3
    j1=6 if j<9
    j1=3 if j<6
    j1=0 if j<3
    i1.upto(i1+2) do |i2|
      j1.upto(j1+2) do |j2|
	Table[i2][j2].delete(Table[i][j]) if Table[i2][j2].class==Array
      end
    end
  end
end

def resetTable
  0.upto(80) do |x|
    i=x/9
    j=x-i*9
    if Table[i][j].class==Array
      Table[i][j]=[1,2,3,4,5,6,7,8,9]
    end
  end
  0.upto(80) do |x|
    i=x/9
    j=x-i*9
    setTable(i,j)
  end
end

def setTableValue(x)
  return true if x>80
  i=x/9
  j=x-i*9
  num=getNumber(Table[i][j])
  tempa=Table[i][j]
  if num==nil
    return false
  else
    Table[i][j]=num
    setTable(i,j)
    if not setTableValue(x+1)
      Table[i][j]=tempa
      resetTable
      tempa.delete(num)
      Table[i][j]=tempa
      return setTableValue(x)
    else
      return true
    end
  end
end

def initTable
  0.upto(8) do |i|
    Table[i]=Array.new(9)
  end
  0.upto(8) do |i|
    0.upto(8) do |j|
     Table[i][j]=[1,2,3,4,5,6,7,8,9]
    end 
  end
  setTableValue(0)  
end

def getStr(num)
  if num.class==Array
    return '-'
  end
  return num.to_s
end

def showTable
  0.upto(8) do |i|
    0.upto(7) do |j|
      print getStr(Table[i][j])+' '
    end
    print getStr(Table[i][8])+"\n"
  end
end

def cutTable (x)
  0.upto(80) do |num|
    i=num/9
    j=num-i*9
    Table[i][j]=Array.new if rand < x
  end
end


initTable
cutTable(0.8)
showTable

评论

25 楼 kim 2007-09-17  

刚接触数读，感觉满有意思的，感觉每一步都靠推算能出来的题设计起来好有难度ki

24 楼 Godlikeme 2007-07-24  

Readonly 写道

老庄，动态语言不是这样写的，你这完全就是披着ruby外衣的java...

其他偶也不多说了，转一行ruby的数独解法代码：

$*.map{|a|(i=a=~/0/)?(v=*?1..?9).fill{|j|v-=[a[j+i-k=i%9],a[k+j*=9],a[j%26+i-i%3-i%27+k]]}+v.map{|k|$*.<<$`<<k<<$'}:p(a)}

将这行代码保存为sudoku.rb，接受的数独题目为从左到右，从上到下的一行字符串（0代表空位），运行：
ruby sudoku.rb 200370009009200007001004002050000800008000900006000040900100500800007600400089001
得出答案：
"284375169639218457571964382152496873348752916796831245967143528813527694425689731"

这样的东西也好叫代码么？

23 楼 suave 2007-07-24  

ruby quiz里面有一个soduku的题目

22 楼 graying 2007-07-24  

想请问一下Readonly：“$*.<<”这个是什么意思啊……

21 楼 hamburg 2007-07-05  

说了这么多，也没有什么牛的，就是人家说好了一道题，叫你用程序实现，这有什么，牛人都去搞数学了，不要搞人家搞完的你在用程序实现？

20 楼 Lich_Ray 2007-07-05  

数独有难易程度之分，一般是先求出一个解，然后去掉其中一部分出题，Readonly说的意思是，这样来做题，只有一个解。
PS: 我觉得上面的程序给出解答的速度已经很快了，用回溯法，是不是就到头了呢？

19 楼 cookoo 2007-06-25  

Readonly 写道

数独的规则是要求只能有一个唯一解，老庄，Eastsun的筛法和raimundox的amb法，都是用随机数来产生，可能会产生多个解的题目，数独是解题容易出题难...

好象更严格的说法是不止只有一个解，而且每一步解法都要能靠逻辑推出来（也就是每一步盘面上至少可以找到一个确定的数字）而不用被迫靠猜的。。。

18 楼 Eastsun 2007-06-25  

庄表伟 写道

Readonly 写道

数独的规则是要求只能有一个唯一解，老庄，Eastsun的筛法和raimundox的amb法，都是用随机数来产生，可能会产生多个解的题目，数独是解题容易出题难...

怎么才能生成只有一个解的数独呢？

目前的零散联想：
1、图的连通性，隐隐约约有点意思。
2、判断逻辑推理是否成立的冗余性，推理的真命题什么的。
3、最笨的办法，自己出题，自己试着穷举解，有多于一个解时，再加一个数，直到只有唯一解为止。

我想是不是可以弄出一个N元一次方程,比较容易看出的是每行每列,每个小九宫的数字和等于45,然后每个数字都属于1~9,
然后看这个方程是不是有唯一解,不过没仔细考虑这个是不是与原题等价,估计还要加其他约束条件.

不过及时把唯一性的弄出来了,这个数独难度的控制似乎也不好办.

17 楼 庄表伟 2007-06-25  

Readonly 写道

数独的规则是要求只能有一个唯一解，老庄，Eastsun的筛法和raimundox的amb法，都是用随机数来产生，可能会产生多个解的题目，数独是解题容易出题难...

怎么才能生成只有一个解的数独呢？

目前的零散联想：
1、图的连通性，隐隐约约有点意思。
2、判断逻辑推理是否成立的冗余性，推理的真命题什么的。
3、最笨的办法，自己出题，自己试着穷举解，有多于一个解时，再加一个数，直到只有唯一解为止。

16 楼 庄表伟 2007-06-25  

deafwolf 写道

我说，数独这东西，拿程序硬上，就没意思了啊

要写，也得写成下面那个flash里面的解法，要么直观法，要么候选数
flash里的是直观法，用来消磨时间相当合适

这个，作为程序员，还是以提供编程技艺为要吧。
单纯的消磨脑力，那很多事情，都能够消磨的，就不必玩编程算法了。

不过，那个flash地址收藏了，

15 楼 simohayha 2007-06-25  

看看这个：

http://perl.abigail.be/Talks/Sudoku/HTML/title.html

14 楼 Readonly 2007-06-25  

数独的规则是要求只能有一个唯一解，老庄，Eastsun的筛法和raimundox的amb法，都是用随机数来产生，可能会产生多个解的题目，数独是解题容易出题难...

13 楼 deafwolf 2007-06-25  

我说，数独这东西，拿程序硬上，就没意思了啊

要写，也得写成下面那个flash里面的解法，要么直观法，要么候选数
flash里的是直观法，用来消磨时间相当合适

12 楼 Eastsun 2007-06-25  

庄表伟 写道

Eastsun 写道

仔细看了一下代码,除了代码写的有点BT外,其算法也没什么特殊的,就是简单的回溯算法.

不像是简单的回溯吧，“j%26+i-i%3-i%27+k”这里面的26，就是个挺奇怪的数字。

这个26是那个ruby版的吧?我不懂ruby,不晓得是不是与java的是同一种算法.

11 楼 Eastsun 2007-06-25  

呵呵,我来给那个JAVA版的做个注释:

/**
* Eastsun注释
*/
class S{
    /**
    * 尝试在b[]的第p-1个位置放置数字
    */
    static void r(char[]b,int p){
        long u=0;     //该long的第k(1至9)位bit代表当前位置是否可以放置数字k(是0否1)
        if(--p<0) System.out.print(b);  //如果p-1<0说明所有位置已经放置好,已经求得一解
        else if(b[p]>48) r(b,p);        //>48,说明该位置是已经填好数字的,不需要尝试
        else{
            for(int i=81;i-->0;)
               u|=
                  // (p-i)%9==0 :就是说p与i是同一列
                  // p/9^i/9==0 :就是说p与i是同一行
                  // p/27^i/27|p%9/3^i%9/3==0: 就是p与i在同一个小九宫
                  // 为什么是这样子?简单的数学题,呵呵.
                  //我来解释一下最后一个,p/27==i/27相当于把大九宫按行分成3下,0~2行,3~5行,6~8行三部分,
                  // 检查p与i是否属于同一个部分
                  // p%9是看p属于那一列,p%9/3是看p属于0~2列,3~5列,6~8列的那一部分
                  // so,p/27^i/27|p%9/3^i%9/3==0时,p与i属于同一小九宫
                  (p-i)%9*(p/9^i/9)*(p/27^i/27|p%9/3^i%9/3)  
                     ==0?
                     1L<<b[i]:         //==0,说明这个位置对当前位置有影响,将u的该位置1
                     0;
            for(b[p]=58;--b[p]>48;)
               if((u>>b[p]&1)<1)       //u>>b[p]&1 <1也就是u>>b[p]&1==0,说明这个b[p]是合理的,
                      r(b,p);          //试探下一个
            //注意这个循环结束条件是 !--b[p]>48,也就是b[p]=='0',最后又将b[p]恢复到'0'不会影响回溯条件.
        }
    }
    public static void main(String[] a){
        //从第80个位置开始试探.
        r(a[0].toCharArray(),81);
    }
}

10 楼 庄表伟 2007-06-25  

Eastsun 写道

仔细看了一下代码,除了代码写的有点BT外,其算法也没什么特殊的,就是简单的回溯算法.

不像是简单的回溯吧，“j%26+i-i%3-i%27+k”这里面的26，就是个挺奇怪的数字。

9 楼 Eastsun 2007-06-24  

仔细看了一下代码,除了代码写的有点BT外,其算法也没什么特殊的,就是简单的回溯算法.

8 楼 Elminster 2007-06-24  

要玩儿算法题，就不要看数独游戏这种鼎鼎有名的东西，早就被无数人用各种方式嚼过无数遍，不管你怎么玩，最后一定都是撞墙。

7 楼 cookoo 2007-06-24  

这也太离谱了吧，one-liner可不是动态语言的风格。

raimundox借助于backtracking库的程序是这类约束问题直观的解法。

6 楼 Eastsun 2007-06-24  

Oh,my god~