Weekly Code Puzzle #2: Results

Welcome back to Bloc's code puzzle challenge! For our second puzzle, we were challenged to complete Sudoku Solver. Here are the results.

“Two Step forward, One step back” Award

For a solution that uses backtracking, Christian Ambriz, AKA Breezy, takes home the award:

function sudoku(puzzle) {  
  return solveSudoku(puzzle, 0, 0);
}
​
function solveSudoku(puzzle, x, y) {  
  if(x == 9) {
    return puzzle;
  }
  if(puzzle[x][y] != 0) {
    if(y == 8){
      return solveSudoku(puzzle, x + 1, 0);
    }
    return solveSudoku(puzzle, x, y + 1);
  }
  var answer;
  var cellOptions = getOptions(puzzle, x, y);
  while (cellOptions.length > 0) {
    var possibleNumber = cellOptions.pop();
    puzzle[x][y] = possibleNumber;
    if(y == 8){
      answer = solveSudoku(puzzle, x + 1, 0);
    } else {
      answer = solveSudoku(puzzle, x, y + 1);
    }
    if(answer != null) {
      return answer;
    }
​
  }
  puzzle[x][y] = 0;
  return null;
}
​
function getOptions(puzzle, x, y) {  
  var cellOptions = [1,2,3,4,5,6,7,8,9];
  for(var xIndex = 0; xIndex < 9; xIndex++) {
    var cellValue = puzzle[xIndex][y];
    if(arrayContains(cellOptions, cellValue)){
      var indexOfNumberAlreadyUsed = getIndex(cellOptions, cellValue);
      cellOptions.splice(indexOfNumberAlreadyUsed,1);
    }
  }
  for(var yIndex = 0; yIndex < 9; yIndex++) {
    var cellValue = puzzle[x][yIndex];
    if(arrayContains(cellOptions, cellValue)){
      var indexOfNumberAlreadyUsed = getIndex(cellOptions, cellValue);
      cellOptions.splice(indexOfNumberAlreadyUsed,1);
    }
  }
  cellOptions = checkBoxOptions(puzzle, cellOptions, x, y);
  return cellOptions;
}
​
function checkBoxOptions(puzzle, cellOptions, x , y) {  
  var xIndex = Math.floor(x / 3) * 3;
  var yIndex = Math.floor(y / 3) * 3;
  var upperXBound = xIndex + 3;
  var upperYBound = yIndex + 3;
  for( xIndex; xIndex < upperXBound; xIndex++) {
    for( yIndex; yIndex < upperYBound; yIndex++) {
      var cellValue = puzzle[xIndex][yIndex];
      if(arrayContains(cellOptions, cellValue)) {
        var indexOfNumberAlreadyUsed = getIndex(cellOptions, cellValue);
        cellOptions.splice(indexOfNumberAlreadyUsed,1);
      }
    }
  }
  return cellOptions;
}
​
function arrayContains(array, value) {  
  for(var index = 0; index < array.length; index++) {
    if(array[index] == value) {
      return true;
    }
  }
  return false;
}
​
function getIndex(array, value){  
  for(var index = 0; index < array.length; index++) {
    if(array[index] == value){
      return index;
    }
  }
}

“Come with me if you want to live!” Award

Matthew Maxwell decided to record 5 hours of himself solving this sudoku puzzle. So, for not only successfully completing the puzzle, but for spending a TON of time and energy exposing his thought process, I present this award to Matthew. His code:

“Swift Coder” Award

Aaron Brager decided one language wasn't enough, so he learned Javascript, completed the puzzle, then completed the puzzle again in Swift. Holy smokes!

So, for that, I'm happy to announce Aaron is the winner of this week's code puzzle challenge, as well as the winner of the "Swift Coder" Award. Way to put us to shame, Aaron.

In Javascript:

function sudoku(puzzle) {  
    while (!isSolved(puzzle)) {
        for (x = 0; x < 9; x++) {
            for (y = 0; y < 9; y++) {
                puzzle[y][x] = digit(puzzle, x, y);
            }
        }
    }
​
    return puzzle;
}
​
function digit(puzzle, x, y) {  
    if (puzzle[y][x] !== 0) return puzzle[y][x];
​
    var row = puzzle[y];
    var column = columnArray(puzzle, x);
    var grid = gridArray(puzzle, x, y);

    var knowns = row.concat(column, grid);

    var possibilities = [1, 2, 3, 4, 5, 6, 7, 8, 9].filter(function(item) { return knowns.indexOf(item) === -1; });
​
    return possibilities.length == 1 ? possibilities[0] : 0;
}
​
function columnArray(puzzle, idx) {  
    return puzzle.map(function(row) { return row[idx]; });
}
​
function gridArray(puzzle, x, y) {  
    x = Math.floor(x / 3) * 3;
    y = Math.floor(y / 3) * 3;

    var arr = [];

    for (i = x; i < x + 3; i++) {
        for (j = y; j < y + 3; j++) {
            arr.push(puzzle[j][i]);
        }
    }

    return arr;
}
​
function sum(arr) {  
    return arr.reduce(function(a, n) { return a + n; }, 0);
}
​
function winningRow(arr) {  
    return sum(arr.map(function(num) { return Math.pow(2, num - 1); })) == 511;
}
​
function isSolved(puzzle) {  
    return puzzle.filter(function (row) { return !winningRow(row); }).length === 0;
}

In Swift:

//: Brute force Sudoku solver in Swift
import Foundation  
// storage
struct Puzzle {  
    var array: [[Int]]
}
// accessors and a setter
extension Puzzle {  
    subscript(x: Int, y: Int) -> Int {
        get { return array[y][x] }
        set(newValue) { array[y][x] = newValue }
    }

    func row(row: Int) -> [Int] {
        return array[row]
    }

    func column(column: Int) -> [Int] {
        return array.map { $0[column] }
    }

    func subgrid(var x x: Int, var y: Int) -> [Int] {
        var arr = [Int]()

        x = x / 3 * 3
        y = y / 3 * 3
        for i in x..<x+3 {
            for j in y..<y+3 {
                arr.append(self[i, j])
            }
        }

        return arr
    }
}
// solution-related methods
extension Puzzle {  
    var isSolved: Bool {
        for row in array where !winningRow(row) {
            return false
        }
        return true
    }
    func winningRow(arr : [Int]) -> Bool {
        return 511 == arr.map { Int(pow(2.0, Double($0 - 1))) }.reduce(0, combine: +)
    }

    mutating func solveDigit(x x: Int, y: Int) {
        guard self[x, y] == 0 else { return }

        let knowns = Set(self.row(y) + self.column(x) + self.subgrid(x: x, y: y))
        let possibilities = Set([1, 2, 3, 4, 5, 6, 7, 8, 9]).subtract(knowns)

        if possibilities.count == 1 {
            self[x, y] = possibilities.first!
        }
    }
}
// keep trying until it's solved
func sudoku(var puzzle: Puzzle) -> Puzzle {  
    while (!puzzle.isSolved) {
        for x in 0..<9 {
            for y in 0..<9 {
                puzzle.solveDigit(x: x, y: y)
            }
        }
    }

    return puzzle
}
// Usage
// Create a Puzzle by passing a 2D array to the initializer
let puzzle = Puzzle(array:  
    [[5,3,0,0,7,0,0,0,0],
     [6,0,0,1,9,5,0,0,0],
     [0,9,8,0,0,0,0,6,0],

     [8,0,0,0,6,0,0,0,3],
     [4,0,0,8,0,3,0,0,1],
     [7,0,0,0,2,0,0,0,6],

     [0,6,0,0,0,0,2,8,0],
     [0,0,0,4,1,9,0,0,5],
     [0,0,0,0,8,0,0,7,9]])
// Print the solution
print(sudoku(puzzle))  

Next week

The next puzzle has been posted! Thanks to Christian Schlensker for organizing.