数独求解

• OC版本

- (instancetype)initWithArray:(NSArray *)array
{
    self = [super init];
    if (self) {
        _array = [NSMutableArray array];
        for (NSArray *sub in array) {
            [_array addObject:[NSMutableArray arrayWithArray:sub]];
        }
    }
    return self;
}

//求解数独
- (BOOL)solve
{
    Item *item = [self nextFreeCell];
    
    if (!item) {
        if ([self validateSolution]) {
            return YES;
        }else{
            return NO;
        }
    }
    
    for (int v = 1; v <= 9; v++) {
        self.array[item.y][item.x] = @(v);
        if ([self validateSolution]) {
            if ([self solve]) {
                return YES;
            }
        }
    }
    self.array[item.y][item.x] = @0;
    
    return NO;
}

- (Item *)nextFreeCell{
    
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if ([self.array[i][j] integerValue] == 0) {
                Item *item = [Item new];
                item.x = j;
                item.y = i;
                return item;
            }
        }
    }
    
    return nil;
}
    
- (BOOL)validateSolution
{
    BOOL res = YES;
    
    for (int i = 0; i < 9; i++) {
        if (![self validSlice:[self getRow:i]]) {
            res = NO;
            break;
        }
        
        if (![self validSlice:[self getCol:i]]) {
            res = NO;
            break;
        }

        NSInteger y = i / 3 * 3;
        NSInteger x = i % 3 * 3;
        
        if (![self validBlock:[self getBlock:x y:y]]) {
            res = NO;
            break;
        }
    }
    return res;
}

- (BOOL)validSlice:(NSArray *)s
{
    NSMutableDictionary *d = [NSMutableDictionary dictionary];
    
    for (NSNumber *v in s) {
        NSNumber *r = [d valueForKey:v.stringValue];
        d[v.stringValue] = @(r.integerValue + 1);
    }

    for (NSString *k in d.allKeys) {
        NSNumber *v = d[k];
        
        if (k.integerValue != 0 && v.integerValue > 1) {
            return NO;
        }
    }
    return YES;
}

- (BOOL)validBlock:(NSArray *)bl
{
    NSMutableArray *s = [NSMutableArray array];
    
    int i = 0;
    for (NSArray *v in bl) {
        for (NSNumber *j in v) {
            s[i] = j;
            i++;
        }
    }
    return [self validSlice:s];
}

- (NSArray *)getRow:(int)y
{
    return self.array[y];
}

- (NSArray *)getCol:(int)x {
    NSMutableArray *c = [NSMutableArray array];

    for (int k = 0; k < 9; k++) {
        NSArray *v = self.array[k];
        c[k] = v[x];
    }
    return c;
}

- (NSArray *)getBlock:(NSInteger)x y:(NSInteger)y
{
    x = x / 3 * 3;
    y = y / 3 * 3;
    
    NSMutableArray *res = [NSMutableArray array];

    for (int i = 0; i < 3; i++) {
        NSMutableArray *sub = [NSMutableArray arrayWithArray:@[@0,@0,@0]];
        [res addObject:sub];
    }
    
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            res[i][j] = self.array[i+y][j+x];
        }
    }

    return res;
}

• Go版本

func (s *Sudoku) Solve() bool {
    x, y, err := s.nextFreeCell()

    //fmt.Println(s)

    if err != nil {
        if s.validateSolution() {
            return true
        }
        return false
    }

    for v := 1; v <= 9; v++ {
        s.m[y][x] = v
        if s.validateSolution() {
            if s.Solve() {
                return true
            }
        }
    }
    s.m[y][x] = 0
    return false
}

func (s *Sudoku) nextFreeCell() (int, int, error) {
    for i := 0; i < len(s.m); i++ {
        for j := 0; j < len(s.m[0]); j++ {
            if s.m[i][j] == 0 {
                return j, i, nil
            }
        }
    }
    return 0, 0, errors.New("Could not found free cell")
}

type Sudoku struct {
    m [][]int
}

// Создание нового класса Sudoku
func NewSudoku(m [][]int) *Sudoku {
    s := new(Sudoku)
    s.m = m
    return s
}

// Проверка всего поля.
// Входные: полне
// Выходные: ложь или истина
func (s *Sudoku) validateSolution() (res bool) {
    res = true
    for i := 0; i < len(s.m); i++ {
        if !validSlice(s.getRow(i)) {
            res = false
            break
        }
        if !validSlice(s.getCol(i)) {
            res = false
            break
        }
        y := i / 3 * 3
        x := i % 3 * 3
        if !validBlock(s.getBlock(x, y)) {
            res = false
            break
        }
    }
    return
}

// Получение строки.
// Входные: поле, y координата.
// Выходные: слайс содержащий строку
func (s *Sudoku) getRow(y int) []int {
    return s.m[y]
}

// Получить колонку.
// Входные параметры: поле, х координата.
// Выходные: слайс содержащий колонку
func (s *Sudoku) getCol(x int) []int {
    c := make([]int, len(s.m))
    for k, v := range s.m {
        c[k] = v[x]
    }
    return c
}

// Получить блок.
// Входные: поле, x и y координаты любой точки на поле
// Выходные: квадратное поле, в котором находится данная точка
func (s *Sudoku) getBlock(x, y int) [][]int {
    x = x / 3 * 3
    y = y / 3 * 3
    res := make([][]int, 3)

    for i := 0; i < 3; i++ {
        res[i] = make([]int, 3)
    }

    for i := 0; i < 3; i++ {
        for j := 0; j < 3; j++ {
            res[i][j] = s.m[i+y][j+x]
        }
    }

    return res
}

// Проверка валидности слайса. Слайс не должен содержать одинаковых цифр, кроме нуля (нули - пустые места в случае нерешённого поля)
func validSlice(s []int) bool {
    // создаём словарь значений
    d := make(map[int]int, len(s))

    // проходим по всему массиву считая каждое число, встреченное в массиве
    for _, v := range s {
        d[v]++
    }

    // проверяем нет ли повторов любых цифр, кроме нуля
    for k, v := range d {
        if k != 0 && v > 1 {
            return false
        }
    }
    return true
}

// Проверка валидности блока.
// Входные: блок 3x3
// Выходные: истина, если блок валидный, ложь, если нет.
func validBlock(bl [][]int) bool {
    s := make([]int, len(bl)*len(bl[0]))
    var i int
    for _, v := range bl {
        for _, j := range v {
            s[i] = j
            i++
        }
    }
    return validSlice(s)
}

func (s *Sudoku) String() string {
    var res string
    res = "┌───────┬───────┬───────┐\n"
    for k, v := range s.m {
        res = res + "│"
        for i := 0; i < len(v); i += 3 {
            res = res + fmt.Sprintf(" %d %d %d │", v[i], v[i+1], v[i+2])
        }
        res = res + "\n"
        if k == 2 || k == 5 {
            res = res + "├───────┼───────┼───────┤\n"
        }
    }
    res = res + "└───────┴───────┴───────┘"
    return res
}