|
锁定老帖子 主题：来玩数独吧，抛砖引玉
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2007-06-22
以前没有学过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
声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：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();
}
}
}
|
| 返回顶楼 | |
|
发表时间：2007-06-23
嘿嘿,偶还是新开个帖吧,赚点积分o(∩_∩)o...哈哈
http://www.iteye.com/post/318866 |
| 返回顶楼 | |
|
发表时间：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
|
| 返回顶楼 | |
|
发表时间：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" |
| 返回顶楼 | |
|
发表时间：2007-06-24
头撞墙，头自己去撞墙，
头自己头也不回的撞墙去了。。。 经Readonly指点，搜到一个地址： http://markbyers.com/moinmoin/moin.cgi/ShortestSudokuSolver 楼上的几位，一同去撞墙吧。 |
| 返回顶楼 | |
|
发表时间：2007-06-24
Oh,my god~
|
| 返回顶楼 | |
|
发表时间：2007-06-24
这也太离谱了吧，one-liner可不是动态语言的风格。
raimundox借助于backtracking库的程序是这类约束问题直观的解法。 |
| 返回顶楼 | |
|
发表时间：2007-06-24
要玩儿算法题，就不要看数独游戏这种鼎鼎有名的东西，早就被无数人用各种方式嚼过无数遍，不管你怎么玩，最后一定都是撞墙。
|
| 返回顶楼 | |
|
发表时间：2007-06-24
仔细看了一下代码,除了代码写的有点BT外,其算法也没什么特殊的,就是简单的回溯算法.
|
| 返回顶楼 | |
