3行数独ソルバー

Perlで書かれた三行の数独ソルバーと、その解説。


なるほど、完全に探索だけで解決している。

以下、ソースの解読：

@A = split //, <>;

入力は81文字の数字。インデックスと数独上の位置関係は、フラットに横に並べたものとして扱っている。0は空のセル。それをひとつづつ分けて配列@Aに入れている。

sub R {
    for $i ( 0 .. 80 ) {

ソルバー関数Rはセルをすべてなぞる。

        next if $A[$i];

セルが0でない場合はパス。

        my %t = map {
                 $_ / 9 == $i / 9
              || $_ % 9 == $i % 9
              || $_ / 27 == $i / 27 && $_ % 9 / 3 == $i % 9 / 3
              ? $A[$_]
              : 0 => 1
        } 0 .. 80;

この$i番目のセルと同じ、横列($i / 9)、縦列($i % 9)、小ブロック（$i / 27 かつ $i % 9 / 3）にあるセルに入っている値を、すべて集めたセットが%t。

        R( $A[$i] = $_ ) for grep { !$t{$_} } 1 .. 9;

%tに入ってない値を順に(初期値に0が入っていた)セルにセットし、再帰的に探索。
この文は、 for my $v (grep {!$t{$_}} (1..9)) { $A[$i] = $v; R(); } と同じ。

        return $A[$i] = 0;

失敗したのでそのセルを0にクリアして、リターン。重要なのは$A[$i]を元にもどしてから、このセルの処理を終えること。このセルで解となる可能性がないことが判明したので、$iをこれ以上進めず、ひとつセルを戻して次の候補を選ばせることになる。この文は、処理を1文で済ますためにリターンで代入しており、このリターン値は計算には関係なし。

    }
    die @A;

ループが終わったときは、すべてのセルが0でない、つまり答えが見つかったとき。
dieによって、結果を表示し、終了する(結果のあとにエラー文も出力されるけど)。

}
R

ソルバーを実行。


ほぼ8クイーンと同じバックトラックを使ったやり方、つまりひとつづつ、セットしてみて、進めていき、失敗したら戻る、というもの。
表示にdieではなく、printにすれば、全パターンを表示させられる(重複は出ない)。

3行数独ソルバーと同じアルゴリズムをJavaScriptで書いてみる

id:bellbind:20060712:1152692054 入れ替えで、ただしdataは81個のフラットな配列で

var solver = function (data) {
  for (var i = 0; i < 81; i += 1) {
    if (data[i] != 0) continue;
    var t = [false,false,false,false,false,false,false,false,false,false];
    var iDivOs = div(i, 9);
    var iModOs = i % 9;
    var iDivOsIs = div(i, 27);
    var iModOsDivIs = div(i % 9, 3); 
    for (var j = 0; j < 81; j += 1) {
      if (div(j, 9) == iDivOs ||
          j % 9 == iModOs ||
          (div(j, 27) == iDivOsIs && div(j % 9, 3) == iModOsDivIs)) {
        t[data[j]] = true;
      }
    };
    for (var j = 1; j <= 9; j += 1) {
      if (t[j]) continue;
      data[i] = j;
      solver(data);
    }
    data[i] = 0;
    return;
  }
  showResult(data);
};

昨日のに比べてすごく短い。

solver関数の擬似コードは、

  • すべてのセル捜査、各空セルについて
    • この空セルと同じ行、列、グループに入っている数値を全部集める
    • その数値に「ない」各値を、この空セルに順に(仮に)入れる
      • 仮に入れた状態でsolverを再帰的実行
    • 仮に入れた値を空セルにもどし、関数は終了
  • 捜査がおわったっ場合はすべてのセルが埋まっているということなのでこれが解、表示して終了


ついでにHTML全文:

<html>
<head>
<script language="JavaScript">
//<!--
Array.prototype.indexOf = function (value) {
  for (var i = 0; i < this.length; i += 1) {
    if (this[i] == value) return i;
  }
  return -1;
};
Array.prototype.remove = function (value) {
  var index = this.indexOf(value);
  if (index < 0) return false;
  this.splice(index, 1);
  return true;
};
Array.prototype.deepcopy = function () {
  var other = [];
  for (var i = 0; i < this.length; i += 1) {
    var v = this[i];
    if (v.constructor == Array) {
      other[i] = v.deepcopy();
    } else {
      other[i] = v;
    }
  }
  return other;
};

var div = function (a, b) {
  return (a - (a % b)) / b;
};

var init = function () {
  initInput();
  initSample();
};

var initInput = function () {
  var sourceDiv = document.getElementById("source");
  var questionId = "question";
  var questionTable = createSudokuTable(questionId);
  sourceDiv.appendChild(questionTable);
  for (var i = 0; i < 9; i += 1) {
    for (var j = 0; j < 9; j += 1) {
      var cid = questionId + i + "" + j;
      var cell = document.getElementById(cid);
      var iid = "source" + i + "" + j;
      var input = document.createElement("input");
      input.id = iid;
      input.size = 1;
      cell.appendChild(input);
    }
  }
  
};

var initSample = function () {
  var sample = [
    [8,0,7,
     0,6,0,
     5,0,1],
    [0,0,1,
     0,0,0,
     2,7,0],
    [0,0,3,
     0,9,0,
     6,0,0],
    
    [0,0,3,
     6,0,2,
     1,5,0],
    [5,0,0,
     0,0,8,
     3,0,0],
    [0,0,0,
     0,1,0,
     2,0,0],
    
    [9,0,0,
     0,0,0,
     4,7,0],
    [1,3,0,
     0,0,4,
     0,8,5],
    [8,0,6,
     9,5,7,
     0,0,2]
  ];
  setSample(sample);
};

var clearSample = function () {
  var sample = [
    [0,0,0,
     0,0,0,
     0,0,0],
    [0,0,0,
     0,0,0,
     0,0,0],
    [0,0,0,
     0,0,0,
     0,0,0],
    
    [0,0,0,
     0,0,0,
     0,0,0],
    [0,0,0,
     0,0,0,
     0,0,0],
    [0,0,0,
     0,0,0,
     0,0,0],
    
    [0,0,0,
     0,0,0,
     0,0,0],
    [0,0,0,
     0,0,0,
     0,0,0],
    [0,0,0,
     0,0,0,
     0,0,0]
  ];
  setSample(sample);
};

var setSample = function (sample) {
  var id = "source";
  for (var i = 0; i < 9; i += 1) {
    for (var j = 0; j < 9; j += 1) {
      var value = sample[i][j];
      var iid = id + i + "" + j;
      var input = document.getElementById(iid);
      if (value == 0) {
        input.value = "";
      } else {
        input.value = "" + value;
      }
    }
  }
};

var createSudokuTable = function (id) {
  var outTable = document.createElement("table");
  outTable.id = id;
  outTable.border = "1";
  var indexO = 0;
  for (var oRow = 0; oRow < 3; oRow += 1) {
    var outRow = outTable.insertRow(oRow);
    for (var oCol = 0; oCol < 3; oCol += 1) {
      var outCol = outRow.insertCell(oCol);
      var inTable = document.createElement("table");
      inTable.id = id + indexO;
      inTable.border = "1";
      var indexI = 0;
      for (var iRow = 0; iRow < 3; iRow += 1) {
        var inRow = inTable.insertRow(iRow);
        for (var iCol = 0; iCol < 3; iCol += 1) {
          var inCol = inRow.insertCell(iCol);
          var inDiv = document.createElement("div");
          inCol.appendChild(inDiv);
          inDiv.id = id + indexO + "" + indexI;
          //inDiv.innerHTML = "0";
          indexI += 1;
        }
      }
      outCol.appendChild(inTable);
      indexO += 1;
    }
  }
  return outTable;
};

var solve = function () {
  clearResult();
  var data = [];
  
  var id = "source";
  for (var i = 0; i < 9; i += 1) {
    for (var j = 0; j < 9; j += 1) {
      var iid = id + i + "" + j;
      var input = document.getElementById(iid);
      var value = 0;
      if (input.value.length > 0) {
        value = parseInt(input.value);
      }
      var x = (i % 3) * 3 + j % 3;
      var y = (div(i, 3)) * 3 + div(j, 3);
      var index = y * 9 + x;
      data[index] = value;
    }
  }
  solver(data);
};

var solver = function (data) {
  for (var i = 0; i < 81; i += 1) {
    if (data[i] != 0) continue;
    var t = [false,false,false,false,false,false,false,false,false,false];
    var iDivOs = div(i, 9);
    var iModOs = i % 9;
    var iDivOsIs = div(i, 27);
    var iModOsDivIs = div(i % 9, 3); 
    for (var j = 0; j < 81; j += 1) {
      if (div(j, 9) == iDivOs ||
          j % 9 == iModOs ||
          (div(j, 27) == iDivOsIs && div(j % 9, 3) == iModOsDivIs)) {
        t[data[j]] = true;
      }
    };
    for (var j = 1; j <= 9; j += 1) {
      if (t[j]) continue;
      data[i] = j;
      solver(data);
    }
    data[i] = 0;
    return;
  }
  showResult(data);
};

var resultCount = 0;

var showResult = function (data) {
  var resultDiv = document.getElementById("result");
  resultCount += 1;
  var resultId = "solution" + resultCount + "th";
  var resultTable = createSudokuTable(resultId);
  resultDiv.appendChild(resultTable);
  
  for (var i = 0; i < 81; i += 1) {
    var x = i % 9;
    var y = div(i, 9);
    var n = div(y, 3) * 3 + div(x, 3);
    var m = (y % 3) * 3 + x % 3;
    
    var cid = resultId + n + "" + m;
    var cell = document.getElementById(cid);
    var cellDiv = document.createElement("div");
    cellDiv.innerHTML = "" + data[i];
    cell.appendChild(cellDiv);
  }
};

var clearResult = function () {
  resultCount = 0;
  var resultDiv = document.getElementById("result");
  resultDiv.innerHTML = "";
};
  //-->
</script>
</head>
<body onload="init()">
  <form id="input">
    <div id="source">
      
    </div>
    <input type="button" id="" value="solve" onclick="solve()" />
    <input type="button" id="" value="clear" onclick="clearSample()" />
  </form>
  <div id="result">
  </div>
</body>
</html>

当事者の目的のための手段と、その手段のための関係者と

のコメント欄を見て思ったこと。半ば議論のメタ考察であるけれど。


「利益」について語るのであれば、当事者とその目的が達成されるかどうかで考えるべきであり、現状の手段を遂行する人の目的というはその従属要素でしかないだろう。現状、著作権ビジネスの流れは作品の作者とはあまりにも違うところが大きすぎる。つまり電通、テレビ局、流通のことであり、彼らは作品発展の仕組みに寄生しているものである。本来の当事者というのは、作者・作品であり、その直接の対象である読者である。


相互発展のための手段と構造、つまりプラットフォームの分析・設計では、この違いは明確に分離して考えるべきだろう。それはつまり、寄生者サイドが当事者ぶりするべきではないし、当事者サイドが寄生者の代弁をするべきでもない。


もし新手段を設計するのであれば、手段の寄生者の利益は一度白紙にして、その利益は当事者効果の面だけから考察するべきであろう。しかしいまの著作権システムでは、当事者が明らかに力関係で弱い現状があり、その状況の中では、公の問いかけや議論によって最適化させられるというのは無理だろう。そうなると当事者の戦略として、現状の手段が変化する状況は流しつつ分析して、それに見合った手段を構築していく、というのが普通に行われていったとしてもなんら不思議ではない。


で、自分の感想としては、新たな手段ができるかもしれないような状況で、古い手段の寄生者がそれにしがみつくだけが理由として、その手段を消すために現状手段に固執するという解を出すというのは、まったく議論にはなっていない、と思うのである。その手段の寄生状態によって一番利益を得ているのであればそれ自体が最適解になっているというのは明白だろう。