suduku solver这道题写代码有点难啊。 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

suduku solver这道题写代码有点难啊。

suduku solver这道题写代码有点难啊。# JobHunting - 待字闺中

g*r2012-11-30 08:11

1 楼

思路就是backtracking,做到bug-free有点难啊。哪位有简洁明了的代码啊？好学习一
下。

l*i2012-11-30 08:11

2 楼

interviewstreet.com has a sudoku competition this Saturday, so you can test
your code for free, and maybe win a prize.

G*o2012-11-30 08:11

3 楼

re

【在 g*******r 的大作中提到】

: 思路就是backtracking,做到bug-free有点难啊。哪位有简洁明了的代码啊？好学习一
: 下。

a*y2012-11-30 08:11

4 楼

public void solveSudoku(char[][] board)
{
// Start typing your Java solution below
// DO NOT write main() function

}

public void tryNextBoard(char[][] board, int row, int column)
{
//System.out.println("row : "+row+"column: "+column);
if(row == board.length && column == 0)
{
//got it you can print it out or store to external array
return ;
}
else if(board[row][column] != '.')
{
int[] next = getNext(board.length,board[0].length,row,column
);
tryNextBoard(board, next[0],next[1]);
}
else
{
for(char i = '1'; i <= '9'; i++)
{
board[row][column] = i ;

if( isValidSudoku( board))
{
int[] next = getNext(board.length,board[0].length,
row,column);
tryNextBoard(board, next[0],next[1]);
}

board[row][column] = '.';
}
}

}
public int[] getNext(int rows, int columns, int row, int column)
{
int[] next = new int[2];
column ++;
if(column == columns)
{
column = 0;
row ++;
}
next[0] = row;
next[1] = column;
return next;
}

【在 g*******r 的大作中提到】

: 思路就是backtracking,做到bug-free有点难啊。哪位有简洁明了的代码啊？好学习一
: 下。

Y*32012-11-30 08:11

5 楼

void BackTrack(vector > &board,int k,bool& bFindOne)
{
if(k>=81)
{
bFindOne=true;//find a solution
return;
}
int row=k/9;
int col=k%9;
if(isdigit(board[row][col]))//already set
BackTrack(board,k+1,bFindOne);
else
{
for(int i=1;i<=9;i++)
{
board[row][col]=i+'0';
if(isValid(board,row,col))
BackTrack(board,k+1,bFindOne);
if(bFindOne)return;
}
board[row][col]='.';//reset this position before trackback
}
}
void solveSudoku(vector > &board)
{
bool bFindOne=false;
BackTrack(board,0,bFindOne);
}
加上sudoku validation 的判断代码，确实太长了