Sudoku Solver
問題作成と初等的なソルバしかなかったので
/**
* Copyright uwi ( http://wonderfl.net/user/uwi )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/3uck
*/
// 問題作成と初等的なソルバしかなかったので
package {
import flash.display.Sprite;
import flash.text.TextField;
import flash.events.MouseEvent;
import com.bit101.components.*;
public class SudokuSolver extends Sprite {
private var _tf : TextField;
private var _f : Array;
private var _solve : PushButton;
private var _area : TextArea;
private var _unique : CheckBox;
private var _logger : TextArea;
private const DEFQ : String = "1..23....\n..8.6.5..\n.....5..8\n..3....29\n...5..4..\n9....4.3.\n.6.......\n..16...7.\n8...7...4";
private const TMAP : Object = {
1:1, 2:2, 4:3, 8:4, 16:5, 32:6, 64:7, 128:8, 256:9
}
public function SudokuSolver() {
_tf = new TextField();
_tf.width = 465;
_tf.height = 300;
_tf.x = 250;
_tf.y = 150;
// addChild(_tf);
var panel : Panel = new Panel(this, 10, 10);
panel.setSize(114, 186);
panel.scaleX = 2;
panel.scaleY = 2;
var i : uint, j : uint;
_f = [];
for(i = 0;i < 9;i++){
var row : Array = [];
for(j = 0;j < 9;j++){
var cell : Text = new Text(panel, j * 12 + (int(j / 3)) * 3, i * 20 + (int(i / 3)) * 3, "");
cell.setSize(12, 20);
row.push(cell);
}
_f.push(row);
}
var l1 : Label = new Label(this, 250, 40, "Input"); l1.setSize(30, 20);
_area = new TextArea(this, 280, 40, DEFQ);
_area.setSize(170, 150);
_logger = new TextArea(this, 250, 200);
_logger.setSize(200, 200);
_logger.editable = false;
_solve = new PushButton(this, 270, 10, "Solve it!", onSolveClick);
_unique = new CheckBox(this, 390, 13, "Unique");
_unique.selected = true;
}
private function onSolveClick(e : MouseEvent) : void
{
var a : Vector.<Vector.<uint>> = makeField();
var i : uint, j : uint;
if(_area.text.length >= 81){
var str : String = _area.text.replace(/[\r\n]/g, "");
for(i = 0;i < 9;i++){
for(j = 0;j < 9;j++){
var cc : uint = str.charCodeAt(i*9+j);
if(cc >= 0x31 && cc <= 0x39){
a[i][j] = cc - 0x30;
}else{
a[i][j] = 0;
}
}
}
}else{
for(i = 0;i < 9;i++){
for(j = 0;j < 9;j++){
var t : uint = uint(_f[i][j].text);
if(t < 0 || t > 9)return;
a[i][j] = t;
}
}
}
var ret : Object = solve(a, _unique.selected);
_logger.text += ["Solved!", "Conflicted!", "Multiple Solutions!"][ret.state] + "\n";
for(i = 0;i < 9;i++){
for(j = 0;j < 9;j++){
if(ret.field[i][j] == 0){
_f[i][j].text = "";
}else{
_f[i][j].text = "" + ret.field[i][j];
}
}
}
}
private function solve(a : Vector.<Vector.<uint>>, unique : Boolean) : Object
{
// コードの設定
var c : Vector.<Vector.<uint>> = makeField(); // candidates
var i : uint, j : uint, k : uint, v : uint;
for(i = 0;i < 9;i++){
for(j = 0;j < 9;j++){
if(a[i][j] > 0){
c[i][j] = 1 << (a[i][j] - 1);
}else{
c[i][j] = (1 << 9) - 1;
}
}
}
// 再帰
var ret : Object = rec(c, unique);
// 確定数字に変換
for(i = 0;i < 9;i++){
for(j = 0;j < 9;j++){
ret.field[i][j] = TMAP[ret.field[i][j]] || 0;
}
}
return ret;
}
// 再帰
private function rec(c : Vector.<Vector.<uint>>, unique : Boolean) : Object
{
// ナイーブな解き方で解けなくなるまでループ
while(true){
if(!isValid(c))return {state : 1, field : c};
if(!step(c))break;
}
if(isEnded(c))return {state : 0, field : c};
// 候補数が少ないセルを選ぶ
var i : uint, j : uint;
var min : uint = 10;
var mini : uint, minj : uint;
for(i = 0;i < 9;i++){
for(j = 0;j < 9;j++){
var bc : uint = bitcount(c[i][j]);
if(bc > 1 && bc < min){
min = bc;
mini = i;
minj = j;
}
}
}
// セルの値を仮定して次へ
var ret : Object = null;
for(i = 0;i < 9;i++){
if(c[mini][minj] & (1 << i)){
var nc : Vector.<Vector.<uint>> = copyField(c);
nc[mini][minj] = 1 << i;
erase(nc, mini, minj);
var res : Object = rec(nc, unique);
if(unique){
if(ret)return {state : 2, field : c};
if(res.state != 1)ret = res;
}else{
if(res.state == 0)return res;
}
}
}
return ret || {state : 1, field : c};
}
// ナイーブな解き方の1ステップ
private function step(c : Vector.<Vector.<uint>>) : Boolean
{
var found : Boolean = false;
var i : uint, j : uint, k : uint, v : uint;
var rr : uint, cc : uint;
// 各列、行、ブロック内で数字が候補になっているセルが一つしかない場合、それを確定させる。
var lfound : Boolean = true;
for(i = 0;i < 9;i++){
if(lfound)clean(c);
lfound = false;
var ur : Vector.<int> = new Vector.<int>(9);
var uc : Vector.<int> = new Vector.<int>(9);
var us : Vector.<int> = new Vector.<int>(9);
for(j = 0;j < 9;j++){
ur[j] = -1;
uc[j] = -1;
us[j] = -1;
}
for(j = 0;j < 9;j++){
if(c[i][j] & (c[i][j] - 1)){
for(k = 0, v = c[i][j];v > 0;k++, v >>= 1){
if(v & 1)ur[k] = ur[k] == -1 ? j : -2;
}
}
if(c[j][i] & (c[j][i] - 1)){
for(k = 0, v = c[j][i];v > 0;k++, v >>= 1){
if(v & 1)uc[k] = uc[k] == -1 ? j : -2;
}
}
rr = uint(i/3)*3 + uint(j/3);
cc = (i%3)*3 + (j%3);
if(c[rr][cc] & (c[rr][cc] - 1)){
for(k = 0, v = c[rr][cc];v > 0;k++, v >>= 1){
if(v & 1)us[k] = us[k] == -1 ? j : -2;
}
}
}
for(j = 0;j < 9;j++){
if(ur[j] >= 0){
c[i][ur[j]] = 1 << j;
lfound = true;
}
if(uc[j] >= 0){
c[uc[j]][i] = 1 << j;
lfound = true;
}
if(us[j] >= 0){
rr = uint(i/3)*3 + uint(us[j] / 3);
cc = (i%3)*3 + (us[j] % 3);
c[rr][cc] = 1 << j;
lfound = true;
}
}
if(lfound)found = true;
}
return found;
}
// 確定している数字があったら周辺の候補を除去。
// これを除去できなくなるまで行う。
private function clean(c : Vector.<Vector.<uint>>) : void
{
var i : uint, j : uint;
var pct : uint = 0;
while(true){
var ct : uint = 0;
for(i = 0;i < 9;i++){
for(j = 0;j < 9;j++){
if(!(c[i][j] & (c[i][j] - 1))){
erase(c, i, j);
ct++;
}
}
}
if(pct == ct)break;
pct = ct;
}
}
// i行j列目を基準にして周辺の候補を消去
private function erase(c : Vector.<Vector.<uint>>, i : uint, j : uint) : void
{
var k : uint;
var br : uint = i - (i % 3);
var bc : uint = j - (j % 3);
var ind : uint = (i % 3) * 3 + (j % 3);
for(k = 0;k < 9;k++){
if(k != i)c[k][j] &= ~c[i][j]; // col
if(k != j)c[i][k] &= ~c[i][j]; // row
if(k != ind)c[br+int(k/3)][bc+(k%3)] &= ~c[i][j]; // square
}
}
// 無効なセルがないか
private function isValid(c : Vector.<Vector.<uint>>) : Boolean
{
var i : uint, j : uint;
for(i = 0;i < 9;i++){
for(j = 0;j < 9;j++){
if(c[i][j] == 0){
return false;
}
}
}
return true;
}
// 終了しているかどうか
private function isEnded(c : Vector.<Vector.<uint>>) : Boolean
{
var i : uint, j : uint;
for(i = 0;i < 9;i++){
for(j = 0;j < 9;j++){
if(c[i][j] & (c[i][j] - 1)){
return false;
}
}
}
return true;
}
// 9*9の空Vectorを生成
private function makeField() : Vector.<Vector.<uint>>
{
var ret : Vector.<Vector.<uint>> = new Vector.<Vector.<uint>>();
for(var i : uint = 0;i < 9;i++){
ret[i] = new Vector.<uint>(9);
for(var j : uint = 0;j < 9;j++){
ret[i][j] = 0;
}
}
return ret;
}
// 9*9のVectorをコピー
private function copyField(src : Vector.<Vector.<uint>>) : Vector.<Vector.<uint>>
{
var dst : Vector.<Vector.<uint>> = new Vector.<Vector.<uint>>(9);
for(var i : uint = 0;i < 9;i++){
dst[i] = src[i].concat();
}
return dst;
}
// ビット数カウント
private function bitcount(x : uint) : uint
{
x = ((x >> 1) & 0x5555) + (x & 0x5555);
x = ((x >> 2) & 0x3333) + (x & 0x3333);
x = ((x >> 4) & 0x0f0f) + (x & 0x0f0f);
x = ((x >> 8) & 0x00ff) + (x & 0x00ff);
return x;
}
// マップ表示用
private function print(x : Vector.<Vector.<uint>>) : void
{
var i : uint;
for(i = 0;i < 9;i++){
tr(x[i].join(","));
}
}
private function tr(...o : Array) : void
{
_tf.appendText(o + "\n");
}
}
}