/* Copyright (C) 2015 by Alexandru Cojocaru */ /* This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see . */ package main import ( "fmt" ) // Used returns true if n is arleady used in row r or column c or the block // from the interception of the two. func used(grid *[9][9]uint8, r, c int, n uint8) bool { for c2 := 0; c2 < 9; c2++ { if c2 == c { continue } if grid[r][c2] == n { return true } } for r2 := 0; r2 < 9; r2++ { if r2 == r { continue } if grid[r2][c] == n { return true } } br := r - r%3 bc := c - c%3 for r2 := br; r2 < br+3; r2++ { for c2 := bc; c2 < bc+3; c2++ { if r2 == r && c2 == c { continue } if grid[r2][c2] == n { return true } } } return false } func solve(grid *[9][9]uint8) bool { r := 0 c := 0 for ; r < 9; r++ { c = 0 for ; c < 9; c++ { if grid[r][c] == 0 { goto b } } } b: if r == 9 { return true } else { var n uint8 = 1 for ; n <= 9; n++ { if !used(grid, r, c, n) { grid[r][c] = n if solve(grid) { return true } grid[r][c] = 0 } } return false } } func main() { var grid = [9][9]uint8{ {7, 0, 0, 1, 0, 0, 0, 0, 0}, {0, 2, 0, 0, 0, 0, 0, 1, 5}, {0, 0, 0, 0, 0, 6, 3, 9, 0}, {2, 0, 0, 0, 1, 8, 0, 0, 0}, {0, 4, 0, 0, 9, 0, 0, 7, 0}, {0, 0, 0, 7, 5, 0, 0, 0, 3}, {0, 7, 8, 5, 0, 0, 0, 0, 0}, {5, 6, 0, 0, 0, 0, 0, 4, 0}, {0, 0, 0, 0, 0, 1, 0, 0, 2}, } fmt.Println(grid) solve(&grid) fmt.Println(grid) }