来玩数独吧，抛砖引玉

以前没有学过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

评论

5 楼 庄表伟 2007-06-24  

头撞墙，头自己去撞墙，
头自己头也不回的撞墙去了。。。

经Readonly指点，搜到一个地址：
http://markbyers.com/moinmoin/moin.cgi/ShortestSudokuSolver

楼上的几位，一同去撞墙吧。

4 楼 Readonly 2007-06-24  

老庄，动态语言不是这样写的，你这完全就是披着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"

3 楼 raimundox 2007-06-24  

这个东西用amb最合适了：

class Sudoku
  def initialize
    @square = Array.new(9) { Array.new(9) {0} }
    @amb = Amb.new
  end

  def find_sudoku
    9.times do |row|
       9.times do |col|
          candidate = @amb.choose(*range)
          @square[row][col] = 0
          @amb.assert(count_in_row(row, candidate) == 0)
          @amb.assert(count_in_col(col, candidate) == 0)
          @amb.assert(count_in_sub_square(row, col, candidate) == 0)
          @square[row][col] = candidate
       end
    end
  end

  def range
    result,range = [], [1,2,3,4,5,6,7,8,9]
    9.times do
       result << range[index = rand(range.size)]
       range.delete_at index
    end
    result
  end
 
  def count_in_row row, candidate
    @square[row].inject(0) {|count, num| (num == candidate) ? count + 1 : count}
  end

  def count_in_col col, candidate
    @square.inject(0) {|count, row| (row[col] == candidate) ? count + 1 : count}
  end

  def count_in_sub_square row, col, candidate
    start_row, start_col = row / 3, col / 3
    count = 0
    3.times {|i| 3.times {|j| count += 1 if @square[start_row * 3 + i][start_col * 3 + j] == candidate}}
    count
  end
 
  def create_sudoku number
    find_sudoku    
    number.times { @square[rand(9)][rand(9)] = 0}
  end

  def next
    begin
      @amb.failure
      create_sudoku
    rescue Amb::ExhaustedError
      raise 'no more Sudoku'
    end
  end

  def inspect
    result = ""
    9.times do |row|
       9.times {|col| result << (@square[row][col] == 0 ? '?' : @square[row][col].to_s) << ' '}
       result << "\n"
    end
    result
  end
end

sudoku = Sudoku.new
sudoku.create_sudoku 30
p sudoku

Amb的实现如下(zenspider的实现)

class Amb
  class ExhaustedError < RuntimeError; end

  def initialize
    @fail = proc { fail ExhaustedError, "amb tree exhausted" }
  end

  def choose(*choices)
    prev_fail = @fail
    callcc { |sk|
      choices.each { |choice|
    callcc { |fk|
      @fail = proc {
        @fail = prev_fail
        fk.call(:fail)
      }
      if choice.respond_to? :call
        sk.call(choice.call)
      else
        sk.call(choice)
      end
    }
      }
      @fail.call
    }
  end

  def failure
    choose
  end

  def assert(cond)
    failure unless cond
  end
end

2 楼 Eastsun 2007-06-23  

嘿嘿,偶还是新开个帖吧,赚点积分o(∩_∩)o...哈哈
http://www.iteye.com/post/318866

1 楼 Eastsun 2007-06-23  

嘿嘿,俺来个JAVA版的吧:

public class Solver{
    private static final int SIZE = Puzzler.SIZE;
    private Solver(){
    }
    /**
    * 数独求解
    *@param p 需要求解的数独
    *@return solvable 如果有解,则为true,并且将求得的一个解放置p
    */
    public static boolean solve(Puzzler p){
        int[][]    num =new int[SIZE][SIZE];
        boolean[][] rFlags =new boolean[SIZE][SIZE+1],
                    cFlags =new boolean[SIZE][SIZE+1],
                    zFlags =new boolean[SIZE][SIZE+1];
        for(int r=0;r<SIZE;r++)
            for(int c=0;c<SIZE;c++)
                if(p.isFixed(r,c)){
                    int t =p.getNumber(r,c);
                    num[r][c] =t;
                    rFlags[r][t] =true;
                    cFlags[c][t] =true;
                    zFlags[r/3*3+c/3][t] =true;
                }
                
        int r =0,c =0;
        
outLoop:
        for(;;){//&#
            if(p.isFixed(r,c)){
                c ++;
                if(c>=SIZE){
                    c =0;
                    r ++;
                    if(r>=SIZE) break outLoop;
                }
                continue outLoop;
            } //&#if(p.isFixed())
            int t =SIZE;
            for(c++;;){//&#
                if(t>=SIZE){
                    c --;
                    if(c<0){
                        c =SIZE -1;
                        r --;
                        if(r<0) break outLoop;
                    }
                    if(p.isFixed(r,c)) continue;
                    t =num[r][c];
                    if(t!=0){
                        rFlags[r][t] =false;
                        cFlags[c][t] =false;
                        zFlags[r/3*3+c/3][t] =false;
                        num[r][c] =0;
                    }
                }
                else{
                    t ++;
                    if(!(rFlags[r][t]||
                         cFlags[c][t]||
                         zFlags[r/3*3+c/3][t])
                         ) break;
                }
            }//&#for(c++;;);
            num[r][c] =t;
            rFlags[r][t] =true;
            cFlags[c][t] =true;
            zFlags[r/3*3+c/3][t] =true;   
            c ++;
            if(c>=SIZE){
                c =0;
                r ++;
                if(r>=SIZE) break outLoop;
            } 
        }
        if(r<0) return false;
        for(r=0;r<SIZE;r++)
            for(c=0;c<SIZE;c++)
                if(!p.isFixed(r,c)) p.setNumber(r,c,num[r][c]);
        return true;
    }
    
    public static void main(String[] args){
        Puzzler p =new Puzzler();
        System.out.println(solve(p));
        for(int r =0;r<SIZE;r++){
            for(int c=0;c<SIZE;c++) System.out.print(p.getNumber(r,c)+" ");
            System.out.println();
        }
    }
}