Golang数独算法不起作用
I'm very new to Golang, I'm trying to do a sudoku with backtracking algorithm. But when I run my program, there are no errors but it only displays the grid not complete, with empty cases here is my code :
package main
import "fmt"
var sudoku = [9][9]int{
{9, 0, 0, 1, 0, 0, 0, 0, 5},
{0, 0, 5, 0, 9, 0, 2, 0, 1},
{8, 0, 0, 0, 4, 0, 0, 0, 0},
{0, 0, 0, 0, 8, 0, 0, 0, 0},
{0, 0, 0, 7, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 2, 6, 0, 0, 9},
{2, 0, 0, 3, 0, 0, 0, 0, 6},
{0, 0, 0, 2, 0, 0, 9, 0, 0},
{0, 0, 1, 9, 0, 4, 5, 7, 0},
}
func main(){
IsValid(sudoku, 0)
Display(sudoku)
}
func Display(sudoku[9][9] int){
var x, y int
for x = 0; x < 9; x++ {
fmt.Println("")
if(x == 3 || x == 6){
fmt.Println(" ")
}
for y = 0; y < 9; y++ {
if(y == 3 || y == 6){
fmt.Print("|")
}
fmt.Print(sudoku[x][y])
}
}
}
func AbsentOnLine(k int, sudoku [9][9]int, x int) bool {
var y int
for y=0; y < 9; y++ {
if (sudoku[x][y] == k){
return false
}
}
return true
}
func AbsentOnRow(k int, sudoku [9][9]int, y int) bool {
var x int
for x=0; x < 9; x++{
if (sudoku[x][y] == k){
return false;
}
}
return true;
}
func AbsentOnBloc(k int, sudoku [9][9]int, x int, y int) bool {
var firstX, firstY int;
firstX = x-(x%3)
firstY = y-(y%3)
for x = firstX; x < firstX+3; x++ {
for y = firstY; y < firstY+3; y++ {
if (sudoku[x][y] == k){
return false;
}
}
}
return true;
}
func IsValid(sudoku [9][9]int, position int) bool {
if (position == 9*9){
return true;
}
var x, y, k int
x = position/9
y = position%9
if (sudoku[x][y] != 0){
return IsValid(sudoku, position+1);
}
for k=1; k <= 9; k++ {
if (AbsentOnLine(k,sudoku,x) && AbsentOnRow(k,sudoku,y) && AbsentOnBloc(k,sudoku,x,y)){
sudoku[x][y] = k;
if (IsValid(sudoku, position+1)){
return true;
}
}
}
sudoku[x][y] = 0;
return false;
}
I'm getting this in the console :
900|100|005
005|090|201
800|040|000
000|080|000
000|700|000
000|026|009
200|300|006
000|200|900
001|904|570
I don't understand why it's not completing the grid, has anyone any ideas ?
Your IsValid function changes the contents of the sudoku. The problem is, it actually, in your code as is, changes only a copy of the sudoku. You need to pass it as a pointer if it should change the actual variable.
Here are the changes that you need in your code, it is only five characters:
func main() {
IsValid(&sudoku, 0)
Display(sudoku)
}
// ...
func IsValid(sudoku *[9][9]int, position int) bool {
// ...
if AbsentOnLine(k, *sudoku, x) && AbsentOnRow(k, *sudoku, y) && AbsentOnBloc(k, *sudoku, x, y) {
I don't know Golang, but I have written a sudoku solving algorithm using backtracking.
Your code only iterates the board once. You start with position=0, your code than iterates over the board ,if a position has the value zero you try values 1-9 and if that doesn't work you go to the next position. When position=81, your code stops.
You added new values to the board with your Isvalid function, but you are not iterating over the new board again to see if those new values help your AbsentOn... function to return a new value that is different than the previous iteration. You have to iterate your board again and again until you are sure that there are no 0 valued cells.
That is the reason you have to many 0 on the board at the end of your program. Your program iterated only once, at It is can not solve your example sudoku on it's first try. It has to add new values to the board and make the sudoku board easier with every iteration.
Another problem is your code does not give a feedback. For example it gives 1 to an empty cell. That seems okey at first, but It doesn't mean that the final value of that cell has to be 1. It may change because in your next iterations you realize that there is another cell that can only take the value 1, so now you have to change back to your initial cell and find a new value other than 1. Your code also fails to do that. That's why humans put some possible values near a cell when they are not sure.
It looks like your problem is with the algorithm. You have to understand the backtracking algorithm. You can try it in another language that you know well first and then migrate it to golang(I wrote mine in C++). Other than that your golang code is easy to read and I don't see any golang related problems.