스도쿠 문제 풀이 (오일러프로젝트 E096) :: solving sudoku

sudoku-es6.js

/// 스도쿠의 한칸을 표현하는 클래스
class Vertex {
  constructor(value, order, matrix) {
    this.value = value;
    this.order = order;
    this.availableNumbers = [];
    this.color = (value !== 0) ? "black" : "white";
  }
  reset() {
    this.color = "white";
    this.value = 0;
    this.availableNumbers = [];
  }
}


/** 스도크 매트릭스 **/
class Matrix {
  constructor(numbers){
    this.data = numbers.split('').map((e, i) => new Vertex(parseInt(e), i));
  }

  // 주어진 열번호의 숫자들
  getNumbersAtColumn(column) {
    return [0,1,2,3,4,5,6,7,8].map((e) => this.data[e * 9 + column].value);
  }

  // 주어진 행번호의 숫자들
  getNumbersAtRow(row) {
    return [0,1,2,3,4,5,6,7,8].map((e) => this.data[e + row * 9].value);
  }

  // 주어진 칸의 영역의 숫자들.
  // 영역을 구하기 위한 내부 계산을 추가로 필요로한다.
  getNumbersAtArea(row, col){
    let r = Math.floor(row / 3) * 3;
    let c = Math.floor(col / 3) * 3;
    return [0, 1, 2]
      .map((y) => [0, 1, 2].map((x) => this.data[(y + r) * 9 + (x + c)].value))
      .reduce((x, y)=>x.concat(y));
  }

  // 위 세 메소드를 이용해서
  // 특정 위치에 올 수 있는 후보값들을 찾는다.
  availableNumbersAt(order) {
    let row = Math.floor(order / 9);
    let column = order % 9;
    var cands = [1,2,3,4,5,6,7,8,9];

    return cands.filter((e) => (this.getNumbersAtRow(row).indexOf(e) === -1) &&
        (this.getNumbersAtColumn(column).indexOf(e) === -1) &&
        (this.getNumbersAtArea(row, column).indexOf(e) === -1)
    )
  }

  draw() {
    let numbers = this.data.map((e) => e.value);
    for (var i = 0; i<9;i++){
      console.log(numbers.slice(i*9, (i+1)*9));
    }
    console.log('----');
  }

  // 매트릭스의 초기값에 대해 바로 결정되는 칸의 후보들을 정리한다.
  decreaseUnknown() {
    let seek = true;
    while(seek) {
      seek = false;
      this.data.filter((e) => e.color === 'white').forEach((e)=>{
        let ans = this.availableNumbersAt(e.order);
        if (ans.length === 1){
          e.value = ans[0];
          e.color = "black";
          e.availableNumbers = [];
          seek = true;
        }
      });
    }
    this.data = this.data.filter((e) => e.color === "white")
      .sort((e) => e.availableNumbers.length) + this.data.filter((e) => e.color === "black");
  }

  // 매트릭스 내의 모든 방문하지 않는 칸의 후보들을 업데이트한다.
  // 만약 방문하지 않았는데 후보가 없다면 방금전 세팅한 값이 문제가 있는거다.
  findAvailableNumbers() {
    let i = 0;
    while (i < 81) {
      let v = this.data[i];
      if (v.color === "white") {
        let ans = this.availableNumbersAt(v.order);
        if (ans.length === 0) {
          return false;
        }
        v.availableNumbers = ans;
      }
      i += 1;
    }
    return true;
  }

  // 최적 다음 칸 찾기: 방문하지 않은 칸 중 후보 숫자개수가 적은 칸

  findOptimalNext() {
    let update = this.findAvailableNumbers();
    if(update) {
      var vs = this.data.filter((e) => e.color === "white")[0];
      return vs;
    }
    return null;
  }

  run(){
    //this.draw();
    //this.decreaseUnknown();
    //this.draw();
    let g = this.data.filter((e) => e.color === "black").length;
    let direction = 1; // 1:순방향, 0: 역방향
    let stack = []; // 방문한 칸들을 집어넣는 스택
    let limit = 81 - g; // 모든 칸을 방문했는지 체크하기 위한 한계값.
    let next; // 방문할 예정칸
    while (true) {
      if (stack.length === limit) { // 모든 칸을 방문하면 출력하고 끝낸다.
        this.draw();
        break;
      } else if(next === undefined) { // 다음 방문 예정지가 없다면? 순방향으로 진행을 시작한다.
        direction = 1;
      }

      if (direction === 1) {
        /// 순방향 진행
        next = this.findOptimalNext()
          if (next != undefined) {
            next.color = "grey";
            [next.value, ...next.availableNumbers] = next.availableNumbers;
            stack.push(next);
          } else {
            /// 다음 진행 예정지를 찾을 수 없었다면 deadend를 만났으므로
            /// 방문 스택의 이전 방문지로 돌아간다. 방향은 역방향이다.
            direction = 0;
            next = stack.pop();
          }
      } else {
        /// 역방향 진행시
        if (next.availableNumbers.length > 0) {
          /// 다시 꺼낸 방문칸의 남은 후보 숫자가 있다면 그 다음 후보숫자를 넣고
          /// 다시 순진행한다.
          direction = 1;
            [next.value, ...next.availableNumbers] = next.availableNumbers;
            stack.push(next);
        } else {
          /// 더 이상 넣을 값이 없으면 이전 칸에서 틀렸다.
          /// 칸을 리셋하고 더 이전으로 후퇴.
          next.reset();
          /// 만약 스택에서 더 꺼낼 게 없다면, 가능한 모든 경우를 상정했지만
          /// 풀 수 없었다는 이야기이므로 답이 존재하지 않는 퍼즐이다.
          if (stack.length === 0) {
            console.log("Fail, this sudoku doesn't have solution.");
            break;
          }
          next = stack.pop();
        }
      }
    }
  }
}

let timeit = (fn, k = undefined) => {
  let e = new Date();
  fn();
  let s = new Date();
  console.log(`${k ? k : ''} - time: ${((s - e) / 1000)}sec.`);
  console.log('');
}


//let sample = "200080300060070084030500209000105408000000000402706000301007040720040060004010003";
//let m = new Matrix(sample);
//m.run();
let samples = `003020600900305001001806400008102900700000008006708200002609500800203009005010300
200080300060070084030500209000105408000000000402706000301007040720040060004010003
000000907000420180000705026100904000050000040000507009920108000034059000507000000
030050040008010500460000012070502080000603000040109030250000098001020600080060020
020810740700003100090002805009040087400208003160030200302700060005600008076051090
100920000524010000000000070050008102000000000402700090060000000000030945000071006
043080250600000000000001094900004070000608000010200003820500000000000005034090710
480006902002008001900370060840010200003704100001060049020085007700900600609200018
000900002050123400030000160908000000070000090000000205091000050007439020400007000
001900003900700160030005007050000009004302600200000070600100030042007006500006800
000125400008400000420800000030000095060902010510000060000003049000007200001298000
062340750100005600570000040000094800400000006005830000030000091006400007059083260
300000000005009000200504000020000700160000058704310600000890100000067080000005437
630000000000500008005674000000020000003401020000000345000007004080300902947100080
000020040008035000000070602031046970200000000000501203049000730000000010800004000
361025900080960010400000057008000471000603000259000800740000005020018060005470329
050807020600010090702540006070020301504000908103080070900076205060090003080103040
080005000000003457000070809060400903007010500408007020901020000842300000000100080
003502900000040000106000305900251008070408030800763001308000104000020000005104800
000000000009805100051907420290401065000000000140508093026709580005103600000000000
020030090000907000900208005004806500607000208003102900800605007000309000030020050
005000006070009020000500107804150000000803000000092805907006000030400010200000600
040000050001943600009000300600050002103000506800020007005000200002436700030000040
004000000000030002390700080400009001209801307600200008010008053900040000000000800
360020089000361000000000000803000602400603007607000108000000000000418000970030014
500400060009000800640020000000001008208000501700500000000090084003000600060003002
007256400400000005010030060000508000008060200000107000030070090200000004006312700
000000000079050180800000007007306800450708096003502700700000005016030420000000000
030000080009000500007509200700105008020090030900402001004207100002000800070000090
200170603050000100000006079000040700000801000009050000310400000005000060906037002
000000080800701040040020030374000900000030000005000321010060050050802006080000000
000000085000210009960080100500800016000000000890006007009070052300054000480000000
608070502050608070002000300500090006040302050800050003005000200010704090409060701
050010040107000602000905000208030501040070020901080406000401000304000709020060010
053000790009753400100000002090080010000907000080030070500000003007641200061000940
006080300049070250000405000600317004007000800100826009000702000075040190003090600
005080700700204005320000084060105040008000500070803010450000091600508007003010600
000900800128006400070800060800430007500000009600079008090004010003600284001007000
000080000270000054095000810009806400020403060006905100017000620460000038000090000
000602000400050001085010620038206710000000000019407350026040530900020007000809000
000900002050123400030000160908000000070000090000000205091000050007439020400007000
380000000000400785009020300060090000800302009000040070001070500495006000000000092
000158000002060800030000040027030510000000000046080790050000080004070100000325000
010500200900001000002008030500030007008000500600080004040100700000700006003004050
080000040000469000400000007005904600070608030008502100900000005000781000060000010
904200007010000000000706500000800090020904060040002000001607000000000030300005702
000700800006000031040002000024070000010030080000060290000800070860000500002006000
001007090590080001030000080000005800050060020004100000080000030100020079020700400
000003017015009008060000000100007000009000200000500004000000020500600340340200000
300200000000107000706030500070009080900020004010800050009040301000702000000008006`;

samples.split('\n').forEach((e, i) => timeit(() => { let m = new Matrix(e); m.run(); }, i+1));


/* result of 50 sudokus....
1 - time: 0.186sec.
2 - time: 0.342sec.
3 - time: 3.005sec.
4 - time: 0.437sec.
5 - time: 0.1sec.
6 - time: 20.949sec.
7 - time: 1.814sec.
8 - time: 0.076sec.
9 - time: 40.739sec.
10 - time: 2.399sec.
11 - time: 6.689sec.
12 - time: 0.616sec.
13 - time: 28.22sec.
14 - time: 31.355sec.
15 - time: 1.793sec.
16 - time: 0.075sec.
17 - time: 0.066sec.
18 - time: 2.414sec.
19 - time: 0.382sec.
20 - time: 1.557sec.
21 - time: 0.939sec.
22 - time: 7.438sec.
23 - time: 5.137sec.
24 - time: 1.67sec.
25 - time: 2.586sec.
26 - time: 4.253sec.
27 - time: 2.355sec.
28 - time: 35.299sec.
29 - time: 21.497sec.
30 - time: 1.614sec.
31 - time: 42.477sec.
32 - time: 6.067sec.
33 - time: 0.217sec.
34 - time: 0.54sec.
35 - time: 1.127sec.
36 - time: 0.14sec.
37 - time: 0.698sec.
38 - time: 0.523sec.
39 - time: 0.185sec.
40 - time: 0.154sec.
41 - time: 41.327sec.
42 - time: 2.168sec.
43 - time: 2.509sec.
44 - time: 3.256sec.
45 - time: 21.189sec.
46 - time: 3.293sec.
47 - time: 1.668sec.
48 - time: 64.577sec.
49 - time: 1.075sec.
50 - time: 10.751sec.
*/

sudoku.js

/**
 * Represent a vertex
 * @constructor
 * @param {anyvalue} key : value of vertex
 */
function Vertex(value, order, matrix) {
    var self = this;
    /* declaration of public properties */
    self.color = 'white';
    self.availableNumbers = [];
    self.order = 0;
    self.value = 0;


    init(value, order);
    /** end of initiation **/

    /* internal methods */
    /**
     * initializer
     * @param {Number} value - value of vertex
     * @param {Number} order - order of verrtex in the matrix
     */
    function init(value, order) {
        self.order = order;
        self.value = value;
        if (value !== 0) {
            self.color = 'black';
        }
    }


    /**
     * connect to other vertex
     * @param {Vertex} vert - vertex that is going to be a suceessor
     */
    function _addConnection(vert) {
        self.successors[vert.order] = vert.value;
    }
}



/**
 * Sudoku matrix
 * @constructor
 * @param {String} - numbers
 */
function Matrix(numbers) {
    var self = this;
    init(numbers);

    /**
     * initializer
     * @param {String} - numbers string.
     */
    function init(numbers) {
        self.data = [];
        var l = numbers.length;
        for (var i = 0; i < 81; i++) {
            var newValue = (i >= l ? 0 : parseInt(numbers[i]));
            var newVert = new Vertex(newValue, i);
            self.data.push(newVert);
        }
    }


    /** Public Methods **/

    self.getNumbersAtColumn = _getNumbersAtColumn;
    self.getNumbersAtRow = _getNumbersAtRow;
    self.getNumbersAtArea = _getNumbersAtArea;
    self.availableNumbersAt = availableNumbersAt;
    self.draw = _draw;
    self.run = runBFS;


    /**
     * get numbers array at column
     * @param {Num} column
     * @return {Array}
     */
    function _getNumbersAtColumn(column) {
        var result = [];
        for (var i = 0; i < 9; i++) {
            result.push(self.data[9 * i + (column % 9)].value);
        }
        return result;
    }



    /**
     * get numbers exists at given row
     * @param {Num}
     * @return {Array} - Array of numbers
     */
    function _getNumbersAtRow(row) {
        numbers = self.data.filter(function(e) {
            return row == Math.floor(e.order / 9);
        }).map(function(e) {
            return e.value;
        });
        return numbers;
    }

    /**
     * get numbers exist at given column
     * @param {Num}
     * @return {Array}
     */
    function _getNumbersAtArea(order) {
        function areaFromOrder(o) {
            var row = Math.floor(o / 9);
            var column = o % 9;
            var area = Math.floor(row / 3) + Math.floor(column / 3) * 3;
            return area;
        }
        var area = areaFromOrder(order);

        numbers = self.data.filter(function(e) {
            return areaFromOrder(e.order) === area;
        }).map(function(e) {
            return e.value;
        });
        return numbers;
    }

    /**
     * find all available numbers at given order
     * @param {Num}
     * @return {Array}
     */
    function availableNumbersAt(order) {
        var row = Math.floor(order / 9);
        var column = order % 9;
        var cands = [1, 2, 3, 4, 5, 6, 7, 8, 9];

        var availables = cands.filter(function(e) {
            /* filter by row */
            return self.getNumbersAtRow(row).indexOf(e) == -1;
        }).filter(function(e) {
            /* filter by column */
            return self.getNumbersAtColumn(column).indexOf(e) == -1;
        }).filter(function(e) {
            return self.getNumbersAtArea(order).indexOf(e) == -1;
        });
        return availables;
    }



    /**
     * Draw 9 * 9 grid
     */
    function _draw() {
        numbers = self.data.map(function(e) {
            return e.value;
        });
        for (var i = 0; i < 9; i++) {
            console.log(numbers.slice(i * 9, i * 9 + 9));
        }
    }

    /**
     * Find available numbers for all remain white vertices
     */
    function findAvailableNumbers() {
        var i = 0;
        while (i < 81) {
            var v = self.data[i];
            if (v.color == 'white') {
                var availableNums = self.availableNumbersAt(v.order);
                if (availableNums.length === 0) {
                    return false;
                }
                v.availableNumbers = availableNums;
            }
            i++;
        }
        return true;
    }

    /**
     * Find optimal next vertex.
     * it will be the one that has minimum number of available numbers.
     * if there is any dead end(has no available number), this returns
     * undefined.
     * @return {Vertex} || {undefined}
     */
    function findOptimalNext() {
        var update = findAvailableNumbers();
        if (update) {
            var vs = self.data.slice().sort().filter(function(e) {
                return e.color == 'white';
            })[0];
            return vs;
        }
        return undefined;
    }


    /**
     * run a Depth First Search and solve given sudoku
     */
    function runBFS() {
            //var qeueu = new Queue();

            var direction = 1; // 1: forward, 0: backward.
            var stack = [];

            /** @constant {Num} */
            var limit = 80 - self.data.filter(function(e) {
                return e.color == 'black';
            }).length;
            /** @type {Vertex} */
            var next;
            while (true) {
                if (stack.length == limit) {
                    self.draw();
                    break;
                } else if (next === undefined) {
                    direction = 1;
                }
                if (direction == 1) {
                    /* going forward */
                    next = findOptimalNext();
                    if (next !== undefined) {
                        next.color = 'grey';
                        next.value = next.availableNumbers[0];
                        next.availableNumbers = next.availableNumbers.slice(1, next.availableNumbers.length);
                        stack.push(next);
                    } else {
                        // meet dead end;
                        direction = 0;
                        next = stack.pop();
                    } // end of block - if direction is 1
                } else {
                    /* going backwards */
                    while (next.color == 'black') {
                        next = stack.pop();
                    }
                    if (next.availableNumbers.length > 0) {
                        // if there is one or more available numbers,
                        direction = 1;
                        next.value = next.availableNumbers[0];
                        next.availableNumbers = next.availableNumbers.slice(1, next.availableNumbers.length);
                        stack.push(next);
                    } else {
                        /* go backward one step more */
                        next.value = 0;
                        next.color = 'white';
                        next = stack.pop();
                    }
                } // end of block - goign backward
            } // End of Loop
        } // End of Function
}

//var sample = "003020600900305001001806400008102900700000008006708200002609500800203009005010300";
var sample = "200080300060070084030500209000105408000000000402706000301007040720040060004010003";
samples = "003020600900305001001806400008102900700000008006708200002609500800203009005010300
200080300060070084030500209000105408000000000402706000301007040720040060004010003
000000907000420180000705026100904000050000040000507009920108000034059000507000000
030050040008010500460000012070502080000603000040109030250000098001020600080060020
020810740700003100090002805009040087400208003160030200302700060005600008076051090
100920000524010000000000070050008102000000000402700090060000000000030945000071006
043080250600000000000001094900004070000608000010200003820500000000000005034090710
480006902002008001900370060840010200003704100001060049020085007700900600609200018
000900002050123400030000160908000000070000090000000205091000050007439020400007000
001900003900700160030005007050000009004302600200000070600100030042007006500006800
000125400008400000420800000030000095060902010510000060000003049000007200001298000
062340750100005600570000040000094800400000006005830000030000091006400007059083260
300000000005009000200504000020000700160000058704310600000890100000067080000005437
630000000000500008005674000000020000003401020000000345000007004080300902947100080
000020040008035000000070602031046970200000000000501203049000730000000010800004000
361025900080960010400000057008000471000603000259000800740000005020018060005470329
050807020600010090702540006070020301504000908103080070900076205060090003080103040
080005000000003457000070809060400903007010500408007020901020000842300000000100080
003502900000040000106000305900251008070408030800763001308000104000020000005104800
000000000009805100051907420290401065000000000140508093026709580005103600000000000
020030090000907000900208005004806500607000208003102900800605007000309000030020050
005000006070009020000500107804150000000803000000092805907006000030400010200000600
040000050001943600009000300600050002103000506800020007005000200002436700030000040
004000000000030002390700080400009001209801307600200008010008053900040000000000800
360020089000361000000000000803000602400603007607000108000000000000418000970030014
500400060009000800640020000000001008208000501700500000000090084003000600060003002
007256400400000005010030060000508000008060200000107000030070090200000004006312700
000000000079050180800000007007306800450708096003502700700000005016030420000000000
030000080009000500007509200700105008020090030900402001004207100002000800070000090
200170603050000100000006079000040700000801000009050000310400000005000060906037002
000000080800701040040020030374000900000030000005000321010060050050802006080000000
000000085000210009960080100500800016000000000890006007009070052300054000480000000
608070502050608070002000300500090006040302050800050003005000200010704090409060701
050010040107000602000905000208030501040070020901080406000401000304000709020060010
053000790009753400100000002090080010000907000080030070500000003007641200061000940
006080300049070250000405000600317004007000800100826009000702000075040190003090600
005080700700204005320000084060105040008000500070803010450000091600508007003010600
000900800128006400070800060800430007500000009600079008090004010003600284001007000
000080000270000054095000810009806400020403060006905100017000620460000038000090000
000602000400050001085010620038206710000000000019407350026040530900020007000809000
000900002050123400030000160908000000070000090000000205091000050007439020400007000
380000000000400785009020300060090000800302009000040070001070500495006000000000092
000158000002060800030000040027030510000000000046080790050000080004070100000325000
010500200900001000002008030500030007008000500600080004040100700000700006003004050
080000040000469000400000007005904600070608030008502100900000005000781000060000010
904200007010000000000706500000800090020904060040002000001607000000000030300005702
000700800006000031040002000024070000010030080000060290000800070860000500002006000
001007090590080001030000080000005800050060020004100000080000030100020079020700400
000003017015009008060000000100007000009000200000500004000000020500600340340200000
300200000000107000706030500070009080900020004010800050009040301000702000000008006";

//var m = new Matrix(sample);
//m.run();
matrices = samples.split('\n');
for(var i=0;i<matrices.length;i++){
    var m = new Matrix(matrices[i]);
    m.run();
}

sudoku.ls

class Node
    (@order, @value) ->
        @availables = []

class Grid
    (data) ->
        @size = 9
        @data = [0 til @size**2].map ->
            new Node it, parseInt data[it]

    position-by-order: (order) ~>
        row = Math.floor <| order / @size
        col = order % @size
        area = 3 * (Math.floor <| row / 3) + (Math.floor <| col / 3)
        return row: row, col: col, area: area

    numbers-at-row: (row) ~>
        @data[row*@size til (row+1)*@size].map (.value)

    numbers-at-col: (col) ~>
        @data[col to @size**2 by @size].map (.value)

    numbers-at-area: (area) ~>
        orders = [til @size**2].filter ~>
            @position-by-order it
            .area == area
        return orders.map ~> @data[it].value

    availables-at: (order) ~>
        {row:row, col:col, area:area} = @position-by-order order
        [1 to 9].filter ~>
            it not in @numbers-at-row row
        .filter ~>
            it not in @numbers-at-col col
        .filter ~>
            it not in @numbers-at-area area

    check: ~>
        @data.filter (.value == 0)
        .length > 0

    draw: !~>
        for i in [til @size]
            @data[i*@size til (i+1)*@size]
                .map (.value)
                .join ", "
            |> console.log
        console.log ""

    solve: !~>
        stack = []
        direction = 1
        g = void
        while @check!
            if direction is 1 then
                g = @data.filter (.value == 0) .[0]
                g.availables = @availables-at g.order
                if g.availables.length is 0 then
                    g.value = 0
                    direction = 0
                    continue
                g.value = g.availables.pop!
                stack.push g
            else
                if stack.length is 0 then
                    console.error "Mallformed Sudoku."
                    break
                g = stack.pop!
                if g.availables.length is 0 then 
                    g.value = 0
                    continue
                g.value = g.availables.pop!
                stack.push g
                direction = 1
                continue
        @draw!

d = \003020600900305001001806400008102900700000008006708200002609500800203009005010300
g = new Grid d
g.solve!

sudoku.py

from typing import List, Optional, Tuple, Set


class Node:
    def __init__(self, order: int, value: str):
        self.order: int = order
        self.value: int = int(value)
        self.avaiables: Optional[List[int]] = None


class Grid:
    def __init__(self, data: str):
        self.data = [Node(*v) for v in enumerate(data[:81])]

    def position_by_order(self, order: int) -> Tuple[int, int, int]:
        row = order // 9
        col = order % 9
        area = 3 * (row // 3) + col // 3
        return (row, col, area)

    def numbers_at_row(self, row: int) -> Set[int]:
        return set(x.value for x in self.data[row * 9 : row * 9 + 9])

    def numbers_at_col(self, col: int) -> Set[int]:
        return set(x.value for x in self.data[col::9])

    def numbers_in_same_area(self, area: int) -> Set[int]:
        return set(
            x.value for x in self.data if self.position_by_order(x.order)[2] == area
        )

    def avaiables_at(self, order: int) -> Set[int]:
        row, col, area = self.position_by_order(order)
        s = (
            self.numbers_at_row(row)
            | self.numbers_at_col(col)
            | self.numbers_in_same_area(area)
        )
        return set(range(1, 10)) - s

    def check(self) -> bool:
        return sum(1 for x in self.data if x.value == 0) > 0

    def solve(self):
        direction = 1
        stack = []
        while self.check():
            if direction:
                g: Node = [x for x in self.data if x.value == 0][0]
                g.avaiables = sorted(self.avaiables_at(g.order))
                if not g.avaiables:
                    direction = 0
                    continue
                g.value = g.avaiables.pop()
                stack.append(g)
            else:
                if not stack:
                    raise ValueError("Malformed Sudoku!!!")
                g = stack.pop()
                if not g.avaiables:
                    g.value = 0
                    continue
                g.value = g.avaiables.pop()
                stack.append(g)
                direction = 1
        self.draw()

    def draw(self):
        print("-" * 35)
        for i in range(9):
            print("|".join(f"{x.value:^3}" for x in self.data[i * 9 : (i + 1) * 9]))
            if i % 3 == 2:
                print("-" * 35)


if __name__ == "__main__":
    d = "003020600900305001001806400008102900700000008006708200002609500800203009005010300"
    g = Grid(d)
g.solve()

sudoku.swift

class Node {
    let order: Int
    var value: Int
    var availables = Array<Int>()

    init(order:Int, value:Int) {
        self.order = order
        self.value = value
    }
}

class Grid {
    var data:Array<Node>

    init(data:String){
        let numbers = data.utf8.map{ Int($0) - 48 }
        self.data = numbers.enumerate().map{ Node(order:$0.0, value:$0.1) }
    }

    func positionByOrder(order:Int) -> (row:Int, col:Int, area:Int) {
        let row = order / 9
        let col = order % 9
        let area = 3 * (row / 3) + (col / 3)
        return (row, col, area)
    }

    func numbersAtRow(row:Int) -> Set<Int> {
        let s = Set(row*9..<(row+1)*9)
        return Set(s.map{ self.data[$0].value})
    }

    func numbersAtColumn(col:Int) -> Set<Int> {
        return Set(col.stride(to:81, by:9).map{ self.data[$0].value })
    }

    func numbersAtArea(area:Int) -> Set<Int> {
        let areas = self.data.filter{
            positionByOrder($0.order).area == area
        }.map{ $0.value}
        return Set(areas)
    }

    func availablesAt(order:Int) -> [Int] {
        let (row, col, area) = self.positionByOrder(order)
        let s = Set(1...9)
                .subtract(self.numbersAtRow(row)
                .union(self.numbersAtColumn(col)
                .union(self.numbersAtArea(area))))
        return Array(s)
    }

    func check() -> Bool {
        return self.data.filter{ $0.value == 0 }.count > 0
    }

    func draw() {
        for i in 0..<9 {
            let line = self.data[i*9..<(i+1)*9]
                .map{ String($0.value) }
                .joinWithSeparator(",")
            print(line)
        }
        print("\n")
    }
    
    func solve() {
        var stack = [Node]()
        var direction = 1
        var g:Node!
        while check() {
            if direction == 1 {
                g = self.data.filter{ $0.value == 0 }[0]
                g.availables = availablesAt(g.order)
                guard g.availables.count > 0 else {
                    g.value = 0
                    direction = 0
                    continue
                }
                g.value = g.availables.removeLast()
                stack.append(g)
            } else {
                guard stack.count > 0 else {
                    print("Malformed Sudoku")
                    break
                }
                g = stack.removeLast()
                guard g.availables.count > 0 else {
                    g.value = 0
                    continue
                }
                g.value = g.availables.removeLast()
                stack.append(g)
                direction = 1
            }
        }
        draw()
    }
}


func timeit(@noescape f:()->()) {
    let s = NSDate()
    f()
    let e = NSDate().timeIntervalSinceDate(s)
    print("time: \(e * 1000) ms")
}

timeit{
    let d:String = "003020600900305001001806400008102900700000008006708200002609500800203009005010300"
    let g = Grid(data:d)
    g.solve()
}