数独ソルバー
やばい､SAMPLE[9]が解けない･･･
問題入力をキャンセルできるようにした｡
数独を解きます｡ ソースきたない｡
//やばい､SAMPLE[9]が解けない･･･
//問題入力をキャンセルできるようにした｡
//数独を解きます｡ ソースきたない｡
package
{
//import events.AllSolvedEvent;
//import events.UnsolvableEvent;
import flash.display.Graphics;
import flash.display.SimpleButton;
import flash.display.Sprite;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.events.TimerEvent;
import flash.text.TextField;
import flash.text.TextFieldAutoSize;
import flash.text.TextFormat;
import flash.utils.Timer;
import org.libspark.betweenas3.BetweenAS3;
import org.libspark.betweenas3.easing.Linear;
import org.libspark.betweenas3.tweens.ITween;
//import sudoku.AbstractDisplayedCell;
//import sudoku.Manager;
//import sudoku.SudokuQueue;
/**
* 「ブッ解く」と心の中で思ったならッ！ その時スデに解答は終わっているんだッ！
* ...
* @author @kndys
*/
[SWF(width="465",height="465",backgroundColor="0xffffff",frameRate="30")]
public class Sudoku extends Sprite
{
private const SAMPLE: Array = [
"200008000643000500000001006000081000020009050070000000503040000001300000000068020",
"071000000000003050005000206030065700000000301004000090000000002020400590900070000",
"087004000000005600006000200006720000090000100400000080000049050082000006001000090",
"270000030094508000000010000006800900000000000005007200000040000000602170060000038",
"000000006600500000482090000007200000013000840000006500000030514000009007100000000",
"104000000003000006000020000025090360000702000098060510000050000900000800000000407",
"400000007007900300002000600005000030001504600080000700001000200002008400900000005",
"600000700000001000420003000260408000050000030000091068000800015000700000005000009",
"070042000800000030204500000020500900005000704000093000000051000900000000807400000",
"000800060000903205000004070400070300000000000008010009010500000306802000020003000",
"008000300090500000004000200070400000080310000506009000003000100200000960070100008",
"001030000070000040300070000800050200000103000004060009000060007050000080000010200",
"080007020100400000906000000004000100050000090003000600000000305000002004010800070",
"003000207006000800040003000004000500003000200006000900000100080004000500609000100",
"008700060000500300400009000020000510000000000064000030000900005004008000020007100",
"410000600000050800080040020000007500005060009001008000982000000000010040000607000"
];
private var manager:Manager;
private var queue:SudokuQueue;
private var cells:Vector.<AbstractDisplayedCell>;
private var timer:Timer;
private var inputButtons:Sprite;
private var inputtingCell:uint;
private var useSample:Boolean;
private var isPlaying:Boolean;
public function Sudoku():void
{
if (stage) init();
else addEventListener(Event.ADDED_TO_STAGE, init);
}
private function init(e:Event = null):void
{
removeEventListener(Event.ADDED_TO_STAGE, init);
manager = Manager.getInstance();
queue = SudokuQueue.getInstance();
cells = new Vector.<AbstractDisplayedCell>();
makeInput();
useSample = true;
isPlaying = false;
var q:String = SAMPLE[int(SAMPLE.length*Math.random())];
var cell:AbstractDisplayedCell;
var i:int;
var myself:Sprite = this;
for (i = 0; i < 81; i++)
{
cell = new BasicCell();
cell.index = i;
cell.x = cell.width * ( 3 * (uint(i / 9) % 3) + i % 3) + 10;
cell.y = cell.height * (3 * uint(i / 27) + uint(i / 3) % 3) + 10;
cell.addEventListener(MouseEvent.CLICK, function(e:MouseEvent):void {
var c:AbstractDisplayedCell;
if (!isPlaying)
{
if (!(myself.contains(inputButtons)))
{
c = AbstractDisplayedCell(e.currentTarget);
inputtingCell = c.index;
inputButtons.scaleX = inputButtons.scaleY = 0;
myself.addChild(inputButtons);
inputButtons.x = c.x + 22.5;
inputButtons.y = c.y + 22.5;
BetweenAS3.to(inputButtons, {
scaleX:1.0, scaleY:1.0, x:(c.x - 7.5), y:(c.y - 7.5)
}, 0.4, Linear.linear).play();
}
else
{
c = cells[inputtingCell];
var tw:ITween = BetweenAS3.to(inputButtons, {
scaleX:0.0, scaleY:0.0, x:(inputButtons.x + 30), y:(inputButtons.y + 30)
}, 0.4, Linear.linear);
tw.onPlay = function():void {
c.initialize();
}
tw.onComplete = function():void{
myself.removeChild(inputButtons);
}
tw.play();
}
}
});
addChild(cell);
cells.push(cell);
}
var lines:Sprite = new Sprite();
var gra:Graphics = lines.graphics;
gra.lineStyle(2, 0);
for (i = 0; i < 4; i++ )
{
gra.moveTo(10, cell.height * 3 * i + 10);
gra.lineTo(cell.width * 9 + 10, cell.height * 3 * i + 10);
gra.moveTo(cell.width * 3 * i + 10, 10);
gra.lineTo(cell.width * 3 * i + 10, cell.height * 9 + 10);
}
addChild(lines);
var startButton:TextField = new TextField();
startButton.selectable = false;
startButton.autoSize = TextFieldAutoSize.CENTER;
startButton.text = "START";
startButton.x = 10;
startButton.y = cell.height * 9 + 20;
startButton.border = true;
startButton.borderColor = 0x0;
addChild(startButton);
startButton.addEventListener(MouseEvent.CLICK, start);
var pauseButton:TextField = new TextField();
pauseButton.selectable = false;
pauseButton.autoSize = TextFieldAutoSize.CENTER;
pauseButton.text = "PAUSE";
pauseButton.x = startButton.x + startButton.width + 20;
pauseButton.y = cell.height * 9 + 20;
pauseButton.border = true;
pauseButton.borderColor = 0x0;
addChild(pauseButton);
pauseButton.addEventListener(MouseEvent.CLICK, pause);
var resetButton:TextField = new TextField();
resetButton.selectable = false;
resetButton.autoSize = TextFieldAutoSize.CENTER;
resetButton.text = "RESET";
resetButton.x = pauseButton.x + pauseButton.width + 20;
resetButton.y = cell.height * 9 + 20;
resetButton.border = true;
resetButton.borderColor = 0x0;
addChild(resetButton);
resetButton.addEventListener(MouseEvent.CLICK, reset);
queue.addEventListener(UnsolvableEvent.TYPE, unsolved);
queue.addEventListener(AllSolvedEvent.TYPE, allSolved);
timer = new Timer(25);
timer.addEventListener(TimerEvent.TIMER, queue.shift);
}
private function makeInput():void
{
inputButtons = new Sprite();
inputButtons.alpha = 0.8;
inputButtons.graphics.beginFill(0xffffff);
inputButtons.graphics.drawRect(0, 0, 60, 60);
inputButtons.graphics.endFill();
var tf:TextFormat = new TextFormat(null, 18);
for (var i:int = 0; i < 9; i++)
{
var numeric:TextField = new TextField();
numeric.selectable = false;
numeric.x = 20 * (i % 3);
numeric.y = 20 * int(i / 3);
numeric.width = 20;
numeric.height = 20;
numeric.text = String(i + 1);
numeric.setTextFormat(tf);
inputButtons.addChild(numeric);
}
var myself:Sprite = this;
inputButtons.addEventListener(MouseEvent.CLICK, function(e:Event):void {
if (myself.contains(inputButtons) && !isPlaying)
{
var n:uint = (inputButtons.mouseX / 20 >> 0) +(inputButtons.mouseY / 20 >> 0) * 3;
var c:AbstractDisplayedCell = cells[inputtingCell];
c.initialize(n + 1);
c.decide(n + 1);
inputButtons.x = c.x - 7.5;
inputButtons.y = c.y - 7.5;
var tw:ITween = BetweenAS3.to(inputButtons, {
scaleX:0.0, scaleY:0.0, x:(c.x + 22.5), y:(c.y + 22.5)
}, 0.4, Linear.linear);
tw.onComplete = function():void {
myself.removeChild(inputButtons);
}
tw.play();
useSample = false;
}
});
}
private function unsolved(e:Event):void
{
/*解けない問題だったときのイベント*/
trace(e);
trace(queue);
timer.stop();
}
private function allSolved(e:Event):void
{
/*最後まで解けたときのイベント*/
trace(e);
trace(queue);
timer.stop();
}
private function start(e:Event = null):void
{
if (!isPlaying)
{
if (this.contains(inputButtons))
{
var c:AbstractDisplayedCell = cells[inputtingCell];
inputButtons.x = c.x - 7.5;
inputButtons.y = c.y - 7.5;
var tw:ITween = BetweenAS3.to(inputButtons, {
scaleX:0.0, scaleY:0.0, x:(c.x + 22.5), y:(c.y + 22.5)
}, 0.4, Linear.linear);
var myself:Sprite = this;
tw.onComplete = function():void {
myself.removeChild(inputButtons);
}
tw.play();
}
if(useSample)
{
var q:String = SAMPLE[int(SAMPLE.length * Math.random())];
for (var i:int = 0; i < 81; i++)
{
cells[i].initialize(parseInt(q.charAt(i)));
}
}
manager.init(cells);
manager.solve();
isPlaying = true;
}
if(!timer.running) timer.start();
}
private function pause(e:Event = null):void
{
if (isPlaying && timer.running) timer.stop();
}
private function reset(e:Event = null):void
{
if (timer.running) timer.stop();
queue.flush();
BetweenAS3.delay(BetweenAS3.func(function():void{
for (var i:int = 0; i < 81; i++)
{
cells[i].initialize();
}
}), 0.5).play();
isPlaying = false;
}
}
}
import flash.display.Sprite;
import flash.display.Graphics;
import flash.display.Shape;
import flash.events.Event;
import flash.events.EventDispatcher;
import flash.text.TextField;
import flash.text.TextFormat;
import flash.text.TextFormatAlign;
import flash.utils.Dictionary;
import org.libspark.betweenas3.BetweenAS3;
import org.libspark.betweenas3.easing.Linear;
import org.libspark.betweenas3.tweens.ITween;
import org.libspark.betweenas3.tweens.ITweenGroup;
//package sudoku
//{
//import events.UnsolvableEvent;
//import flash.display.Sprite;
class AbstractDisplayedCell extends Sprite
{
public var index:uint;
protected var _decided: Boolean;
protected var _answer:uint;
/**
* 1..9の初期値を与えると解答済みになるように｡
* @param n
*/
public function AbstractDisplayedCell(n:uint = 0)
{
super();
initialize(n);
}
/**
* セル初期化
* @param n
*/
public function initialize(n:uint = 0):void
{
_decided = (n <= 9) && (n >= 1);
if ( _decided )
{
_answer = n;
}
else
{
_answer = 0;
}
}
/**
* 初期状態で決定済みのセル
*/
public function get initiallyDecided():Boolean
{
return _decided;
}
/**
* 初期状態で与えられた解答
*/
public function get initialAnswer():uint
{
return _answer;
}
/**
* セル選択時の動作
*/
public function selectCell():void { }
public function unselectCell():void { }
/**
* 選択セルの候補を1つ選択する動作
* @param n 選択候補(1..9)
*/
public function selectSubject(n:uint):void { }
public function unselectSubject(n:uint):void { }
/**
* 選択セルの候補を一つ削除する動作
* @param n (1..9)
*/
public function removeSubject(n:uint):void { }
/**
* セル参照時の動作
*/
public function referCell():void { }
public function unreferCell():void { }
/**
* 参照セルの候補を確認する動作
* @param n (1..9)
*/
public function checkSubject(n:uint):void { }
/**
* マス目に入る数字を決定する動作
* @param n 解答(1..9)
*/
public function decide(n:uint):void { }
/**
* エラー発生時
*/
public function error():void { }
}
//}
//package
//{
//import sudoku.AbstractDisplayedCell;
class BasicCell extends AbstractDisplayedCell
{
private var subjects:Vector.<TextField>;
private var bg:Shape;
private static var tf:TextFormat;
public function BasicCell(n:uint = 0)
{
super(n);
bg = new Shape();
addChildAt(bg, 0);
var g:Graphics = this.graphics;
g.clear();
g.lineStyle(1, 0xcccccc);
g.beginFill(0xffffff, 1);
g.drawRect(0, 0, 45, 45);
g.endFill();
}
override public function initialize(n:uint = 0):void
{
super.initialize(n);
if(bg) bg.graphics.clear();
if (tf == null)
{
tf = new TextFormat(null, 10, 0x808080, true, false, false, null, null, TextFormatAlign.CENTER, 0, 0, 0, 0);
}
var sub:TextField;
for each (sub in subjects)
{
if (contains(sub)) removeChild(sub);
}
subjects = new Vector.<TextField>();
for (var i:int = 0; i < 9; i++)
{
sub = new TextField();
sub.selectable = false;
sub.x = 15 * (i % 3);
sub.y = 15 * int(i / 3);
sub.width = 15;
sub.height = 15;
sub.text = String(i + 1);
sub.setTextFormat(tf);
this.addChild(sub);
subjects.push(sub);
}
}
override public function selectCell():void
{
bg.alpha = 0;
var g:Graphics = bg.graphics;
g.clear();
g.lineStyle(1, 0xff0000);
g.beginFill(0xff8080);
g.drawRect(0, 0, 45, 45);
g.endFill();
var tw:ITween = BetweenAS3.tween(bg, { alpha:1.0 }, { alpha:0.0 }, 0.4, Linear.linear);
tw.play();
}
override public function unselectCell():void
{
var tw:ITween = BetweenAS3.tween(bg, { alpha:0.0 }, { alpha:1.0 }, 0.2, Linear.linear);
tw.onComplete = function():void {
bg.graphics.clear();
}
tw.play();
}
override public function referCell():void
{
bg.alpha = 0;
var g:Graphics = bg.graphics;
g.clear();
g.lineStyle(1, 0x00ff00);
g.beginFill(0xffff80);
g.drawRect(0, 0, 45, 45);
g.endFill();
var tw:ITween = BetweenAS3.to(bg, { alpha:1.0 }, 0.2, Linear.linear);
tw.play();
}
override public function unreferCell():void
{
var tw:ITween = BetweenAS3.to(bg, { alpha:0.0 }, 0.1, Linear.linear);
tw.onComplete = function():void {
bg.graphics.clear();
}
tw.play();
}
override public function selectSubject(n:uint):void
{
var tw:ITween = BetweenAS3.to(subjects[n -1], { textColor: 0xff }, 0.1, Linear.linear);
tw.play();
}
override public function unselectSubject(n:uint):void
{
var tw:ITween = BetweenAS3.to(subjects[n -1], { textColor : 0x808080 }, 0.1, Linear.linear);
tw.play();
}
override public function removeSubject(n:uint):void
{
var sub:TextField = subjects[n - 1];
var tw:ITween = BetweenAS3.to(sub, { alpha :0.0 }, 0.2, Linear.linear);
tw.onComplete = function():void {
if (contains(sub))
{
removeChild(sub);
}
}
tw.play();
}
override public function checkSubject(n:uint):void
{
var tw:ITween = BetweenAS3.tween(subjects[n -1], { alpha: 1.0 }, { alpha: 0.2 }, 0.05, Linear.linear);
tw = BetweenAS3.repeat(tw, 2);
tw.play();
}
override public function decide(n:uint):void
{
var idx:int = n -1;
var tweens:Array = [];
var i:int;
for (i = 0; i < 9; i++)
{
if (i == idx)
{
continue;
}
tweens.push(BetweenAS3.to(subjects[i], { alpha:0.0 }, 0.4, Linear.linear));
}
var sub:TextField = subjects[idx];
if (_decided)
{
tweens.push(BetweenAS3.to(sub, { scaleX:3.0, scaleY:3.0, x:0, y:0}, 0.4, Linear.linear));
}
else
{
tweens.push(BetweenAS3.to(sub, { scaleX:3.0, scaleY:3.0, x:0, y:0, textColor:0 }, 0.4, Linear.linear));
}
var tw:ITween = BetweenAS3.parallelTweens(tweens);
tw.onComplete = function():void {
for (i = 0; i < 9; i++)
{
if (i == idx || !contains(subjects[i]))
{
continue;
}
removeChild(subjects[i]);
}
}
tw.play();
}
override public function error():void
{
var tweens:Array = [];
for (var i:int = 0; i < 9; i++)
{
tweens.push(BetweenAS3.to(subjects[i], { alpha:0.3 }, 1.0, Linear.linear));
}
bg.alpha = 0;
var g:Graphics = bg.graphics;
g.clear();
g.lineStyle(1, 0x0);
g.beginFill(0x404040);
g.drawRect(0, 0, 45, 45);
g.endFill();
tweens.push(BetweenAS3.to(bg, { alpha:1.0 }, 1.0, Linear.linear));
var tw:ITween = BetweenAS3.parallelTweens(tweens);
tw.play();
}
}
//}
//package sudoku
//{
//import events.AllSolvedEvent;
//import events.UnsolvableEvent;
//import utils.TermaryConverter;
class Manager
{
private static var QUE:SudokuQueue;
private static var instance:Manager;
private var cells:Vector.<SudokuCell>;
private var cellsSets:Vector.<CellsSet>;
private var allSolved:Boolean;
public function Manager()
{
if (QUE == null)
{
QUE = SudokuQueue.getInstance();
}
}
/**
* シングルトンなインスタンスを得る
* @return
*/
public static function getInstance():Manager
{
if (instance == null)
{
instance = new Manager();
}
return instance;
}
/**
* セルのセット群を初期化する
* @param dCells 画面に表示されるセルのVector
* @return
*/
public function init(dCells:Vector.<AbstractDisplayedCell>):Boolean
{
if (dCells == null || dCells.length < 81)
{
return false;
}
//表示セルを元に新しいセル群を作成する
cells = new Vector.<SudokuCell>();
var i:int;
var m:uint;
var n:uint;
for (i = 0; i < 81; i++)
{
cells.push(new SudokuCell(dCells[i]));
}
/*
* 縦･横･箱型のセル9個セットにどのように格納するか｡
* 0..80 のインデックスがあるが､これを3進法に直すと
* 0000..2222 と表せることを利用する｡
*/
var conv:Function = TermaryConverter.convertFromDigits;
cellsSets = new Vector.<CellsSet>();
for (i = 0; i < 9; i++)
{
m = i / 3;
n = i % 3;
//1行9個入りセット9行
cellsSets.push(new CellsSet(
cells[conv(m, 0, n, 0)], cells[conv(m, 0, n, 1)], cells[conv(m, 0, n, 2)],
cells[conv(m, 1, n, 0)], cells[conv(m, 1, n, 1)], cells[conv(m, 1, n, 2)],
cells[conv(m, 2, n, 0)], cells[conv(m, 2, n, 1)], cells[conv(m, 2, n, 2)]
));
//1列9個入りセット9列
cellsSets.push(new CellsSet(
cells[conv(0, m, 0, n)], cells[conv(0, m, 1, n)], cells[conv(0, m, 2, n)],
cells[conv(1, m, 0, n)], cells[conv(1, m, 1, n)], cells[conv(1, m, 2, n)],
cells[conv(2, m, 0, n)], cells[conv(2, m, 1, n)], cells[conv(2, m, 2, n)]
));
//1箱9個入りセット9箱
cellsSets.push(new CellsSet(
cells[conv(m, n, 0, 0)], cells[conv(m, n, 0, 1)], cells[conv(m, n, 0, 2)],
cells[conv(m, n, 1, 0)], cells[conv(m, n, 1, 1)], cells[conv(m, n, 1, 2)],
cells[conv(m, n, 2, 0)], cells[conv(m, n, 2, 1)], cells[conv(m, n, 2, 2)]
));
}
allSolved = false;
return true;
}
/**
* ここでかなりの回数の演算を行って先に数独は解いてしまう｡
* その後遅れてqueueが順に実行されることになる｡
* @return
*/
public function solve():void {
while (!allSolved)
{
if (!standardCycle())
{
if (!nextCycle())
{
if (!alternativeCylce())
{
QUE.push(QUE.dispatchEvent, new UnsolvableEvent());
trace("今回の問題､解けませんのであしからず｡");
return;
}
}
}
}
trace("解けた｡");
QUE.push(QUE.dispatchEvent, new AllSolvedEvent());
}
private function standardCycle():Boolean
{
var cs: CellsSet;
var bool:Boolean = false;
allSolved = true;
for each(cs in cellsSets)
{
bool = cs.standardCheck() || bool;
allSolved = allSolved && cs.isCompleted;
}
return bool || allSolved;
}
private function nextCycle():Boolean
{
var cs: CellsSet;
allSolved = true;
for each(cs in cellsSets)
{
allSolved = allSolved && cs.isCompleted;
if (cs.nextCheck()) {
return true;
}
}
return allSolved;
}
private function alternativeCylce():Boolean
{
var cs: CellsSet;
allSolved = true;
for each(cs in cellsSets)
{
allSolved = allSolved && cs.isCompleted;
if (cs.alternativeCheck()) {
return true;
}
}
return allSolved;
}
}
//}
//package sudoku
//{
//import events.UnsolvableEvent;
//import flash.events.EventDispatcher;
/**
* 9個のセルからなるセット
* 含まれるセルの確認と操作を行うことにする｡
*/
class CellsSet
{
private var hasCompleted:Boolean;
private var vector: Vector.<SudokuCell>;
private var decidedCell:uint;
/**
* コンストラクタに管理させたい9個組のセルを渡す
*
* @param cell0
* @param cell1
* @param cell2
* @param cell3
* @param cell4
* @param cell5
* @param cell6
* @param cell7
* @param cell8
*/
public function CellsSet(
cell0:SudokuCell, cell1:SudokuCell, cell2:SudokuCell,
cell3:SudokuCell, cell4:SudokuCell, cell5:SudokuCell,
cell6:SudokuCell, cell7:SudokuCell, cell8:SudokuCell)
{
vector = new Vector.<SudokuCell>;
vector.push(cell0, cell1, cell2, cell3, cell4, cell5, cell6, cell7, cell8);
hasCompleted = false;
decidedCell = 0;
}
/**
* 基本的なチェック方法
* 未決定セルを順に選択し､決定セルの数字を候補から削除する｡
* @return 決定セルが増えたかどうか｡
*/
public function standardCheck():Boolean
{
if (decidedCell == 9)
{
return false;
}
var nowDecided:int = 0;
for each (var c:SudokuCell in vector)
{
if (c.isFixed)
{
nowDecided++;
}
}
if (nowDecided == decidedCell)
{
return false;
}
var bool:Boolean = false;
var selected: SudokuCell;
var refered: SudokuCell;
var newDecided:Boolean = false;
SELECT:
for each( selected in vector)
{
if (selected.isFixed)
{
continue SELECT;
}
selected.selectCell();
REFER:
for each( refered in vector)
{
if (selected == refered || !refered.isFixed || selected.checkedCells[refered] === true )
{
continue REFER;
}
//選択セルが未決定なら候補の削除(候補が残ってるかどうかには関わらず)
refered.referCell();
var n: uint = refered.answer;
bool = selected.remove(n) || bool;
selected.checkedCells[refered] = true;
//未決定→決定の変化があったら
if (selected.isFixed)
{
refered.unreferCell(); //参照解除
newDecided = true;
checkOverlap(selected);
break REFER;
}
refered.unreferCell();
}
selected.unselectCell();
}
if (newDecided) standardCheck();
decidedCell = 0;
for each (c in vector)
{
if (c.isFixed)
{
decidedCell++;
}
}
return bool;
}
private function checkOverlap(selected:SudokuCell):void {
if (!selected.isFixed)
{
return;
}
for each(var cell:SudokuCell in vector)
{
if (cell == selected)
{
continue;
}
//解答の重複チェック
if (cell.isFixed && selected.answer == cell.answer)
{
cell.referCell();
selected.error();//queueにはイベント発生タスクが挿入される｡
}
}
}
/**
* ある数字候補を一つのセルだけが持っていた場合､そのセルは決定｡
* @return
*/
public function nextCheck():Boolean {
if (decidedCell == 9)
{
return false;
}
var bool:Boolean = false;
var refered: SudokuCell;
var has:uint;
var holder:SudokuCell;
//var newDecided:Boolean = false;
for (var n:int = 1; n <= 9; n++)
{
has = 0;
holder = null;
REFER:
for each( refered in vector)
{
if (refered.isFixed)
{
continue REFER;
}
if (refered.hasSubject(n))
{
if (has == 0)
{
holder = refered;
has++;
}
else if (has >= 1)
{
holder = null;
has++;
break REFER;
}
}
}
if (has==1)
{
for each(refered in vector)
{
if (refered != holder)
{
refered.referCell();
}
}
holder.selectCell();
holder.removeOthers(n);
checkOverlap(holder);
holder.unselectCell();
for each(refered in vector)
{
if (refered != holder)
{
refered.unreferCell();
}
}
bool = true;
}
}
decidedCell = 0;
for each (var c:SudokuCell in vector)
{
if (c.isFixed)
{
decidedCell++;
}
}
return bool;
}
/**
* 最後の解法｡だいたいの問題はこの方法を使えば解ける｡
* @return 決定セルの数に変化があったか
*/
public function alternativeCheck():Boolean {
if (decidedCell == 9)
{
return false;
}
var bool:Boolean = false;
var referedA: SudokuCell;
var referedB: SudokuCell;
var hash:uint = 0;
var selected:SudokuCell;
var newDecided:Boolean = false;
REFER_A:
for each( referedA in vector)
{
if (referedA.isFixed || referedA.leftSubjects != 2)
{
continue REFER_A;
}
REFER_B:
for each( referedB in vector)
{
if (referedA == referedB || referedB.isFixed || referedB.leftSubjects != 2)
{
continue REFER_B;
}
referedA.referCell();
referedB.referCell();
//残りの候補数が2で､かつ同じ候補を残す2マスを探す
if (referedA.hash == referedB.hash)
{
hash = referedA.hash;
SELECT:
for each(selected in vector)
{
if (selected == referedA || selected == referedB)
{
continue SELECT;
}
else
{
selected.selectCell();
bool = selected.removeByHash(hash) || bool;
if (selected.isFixed)
{
newDecided = true;
}
selected.unselectCell();
}
}
}
referedB.unreferCell();
referedA.unreferCell();
}
}
if (newDecided) standardCheck();
decidedCell = 0;
for each (var c:SudokuCell in vector)
{
if (c.isFixed)
{
decidedCell++;
}
}
return bool;
}
/**
* このセットが全て解答済みかどうか
*/
public function get isCompleted():Boolean
{
return decidedCell == 9;
}
}
//}
//package sudoku
//{
//import events.UnsolvableEvent;
//import flash.utils.Dictionary;
/**
* 単体セルのコントロール部分｡
* 他のセルの参照などは避ける｡
* 基本的に選択対象は未決定セル､参照対象は決定セル｡
* ただし第二相では未決定セルも参照する｡
*/
class SudokuCell
{
private static var QUE:SudokuQueue;
private var displayed:AbstractDisplayedCell;
private var subjects:Vector.<Boolean>; //現在の候補
private var selectedSubject:uint;
private var left:uint; //残り候補の数
private var fixedNumber: int; //解答
private const fixedHash:Vector.<uint> = Vector.<uint>([1, 2, 4, 8, 16, 32, 64, 128, 256]); //解答の判別に使用するハッシュ数列
private var isSelected:Boolean;
private var isRefered:Boolean;
public var checkedCells:Dictionary;
public function SudokuCell(cell:AbstractDisplayedCell)
{
if (QUE == null)
{
QUE = SudokuQueue.getInstance();
}
subjects = new Vector.<Boolean>();
for (var i:int = 0; i < 9; i++)
{
subjects[i] = true;
}
left = 9;
displayed = cell;
isSelected = false;
isRefered = false;
checkedCells = new Dictionary();
if (displayed.initiallyDecided)
{
setQuestion();
}
}
private function setQuestion():void
{
selectCell();
//初期条件として決定済みのセルかどうか
var ans:int = displayed.initialAnswer;
var idx:int = ans - 1;
for (var i:int = 0; i < 9; i++)
{
if (i != idx)
{
subjects[i] = false;
}
}
fixedNumber = ans;
left = 1;
decide(ans);
unselectCell();
}
/**
* 候補の数字を一つ削除する
* @param n 削除する候補(1..9)
*/
public function remove(n:int):Boolean {
if (!isSelected) throw Error("候補の削除はセル選択時のみ有効");
if (fixedNumber > 0) return false; //既に決定済みなら終了
if (n < 1) return false;
if (n > 10) return false;
if (!subjects[n - 1]) return false; //既に削除されていたら終了
selectSubject(n);
subjects[n - 1] = false;
removeSubject(n);
left--;
if (left == 1) {
//var h:uint = hash;
for (var i:int = 0; i < 9; i++)
{
if (subjects[i])//if (h == fixedHash[i])
{
var ans:int = i + 1;
fixedNumber = ans;
decide(ans);
}
}
}
return true;
}
/**
* ある候補を残して他を削除
* @param n
*/
public function removeOthers(n:int):Boolean
{
if (!isSelected) throw Error("候補の削除はセル選択時のみ有効");
if (fixedNumber > 0) return false; //既に決定済みなら終了
if (n < 1) return false;
if (n > 10) return false;
var idx:int = n - 1;
if (!subjects[idx]) return false; //既に削除されていたら終了
for (var i:int = 0; i < 9; i++)
{
if (i != idx)
{
subjects[i] = false;
}
}
fixedNumber = n;
left = 1;
decide(n);
return true;
}
/**
* 残りの候補が同じかどうかを示すハッシュ値(2進数)
*/
public function get hash():uint {
if (!(isSelected || isRefered)) throw Error("ハッシュ値の呼び出しはセル選択または参照時にのみ有効");
var hash:uint = 0;
var bit:uint = 1;
for (var i:int = 0; i < 9; i++)
{
if (subjects[i])
{
var n:int = i + 1;
selectSubject(n);
checkSubject(n);
unselectSubject(n);
hash += bit;
}
bit <<= 1;
}
return hash;
}
/**
* ハッシュの値を利用して重複する候補を削除する｡
* 強力で危険｡
* @param hash
*/
public function removeByHash(hash:uint):Boolean
{
if (!isSelected) throw Error("候補の削除はセル選択時のみ有効");
if (fixedNumber > 0) return false; //既に決定済みなら終了
var bool:Boolean = false;
for (var i:int = 0; i < 9; i++)
{
if ((hash & 1) == 1)
{
if (subjects[i])
{
var n:int = i + 1;
bool = remove(n) || bool;
}
}
hash >>>= 1;
}
return bool;
}
/**
* マス目に入る数字が決まったかどうか｡
*/
public function get isFixed(): Boolean
{
return (left == 1) && (fixedNumber != 0);
}
/**
* マス目に入る解答｡未決定なら0｡
*/
public function get answer(): uint
{
return fixedNumber;
}
/**
* 残りの候補の数
*/
public function get leftSubjects(): uint
{
return left;
}
/**
* 候補を持っているかどうか
*/
public function hasSubject(n:uint):Boolean
{
return subjects[n - 1];
}
/**
* セル選択時の動作
*/
public function selectCell():void
{
if (!isSelected)
{
isSelected = true;
QUE.push(displayed.selectCell);
}
}
public function unselectCell():void
{
if (isSelected)
{
isSelected = false;
QUE.push(displayed.unselectCell);
}
}
/**
* 選択セルの候補を1つ選択する動作
* @param n 選択候補
*/
private function selectSubject(n:uint):void
{
if (isSelected && selectedSubject == 0)
{
selectedSubject = n;
QUE.push(displayed.selectSubject, n);
}
}
private function unselectSubject(n:uint):void
{
if (isSelected && selectedSubject == n)
{
selectedSubject = 0;
QUE.push(displayed.unselectSubject, n);
}
}
/**
* 選択セルの候補を一つ削除する動作
* @param n
*/
private function removeSubject(n:uint):void
{
if (isSelected)
{
if (selectedSubject == n)
{
unselectSubject(n);
}
QUE.push(displayed.removeSubject, n);
}
}
/**
* セル参照時の動作
*/
public function referCell():void
{
if (!(isRefered || isSelected))
{
isRefered = true;
QUE.push(displayed.referCell);
}
}
public function unreferCell():void
{
if (isRefered)
{
isRefered = false;
QUE.push(displayed.unreferCell);
}
}
/**
* 選択または参照セルの候補を確認する動作
* @param n
*/
private function checkSubject(n:uint):void
{
if (isSelected || isRefered)
{
QUE.push(displayed.checkSubject, n);
}
}
/**
* マス目に入る数字を決定する動作
* @param n 解答
*/
private function decide(n:uint):void
{
if (isSelected)
{
QUE.push(displayed.decide, n);
}
}
/**
* エラー発生時
*/
public function error():void
{
if (isSelected)
{
QUE.push(displayed.error);
QUE.push(QUE.dispatchEvent, new UnsolvableEvent());
}
}
public function toString():String
{
return this.answer.toString();
}
}
//}
//package sudoku
//{
//import flash.events.Event;
//import flash.events.EventDispatcher;
/**
* セルの表示に関するFIFOなキュースタック｡
* shift()と同時に関数を実行する｡
*/
class SudokuQueue extends EventDispatcher
{
private static var instance:SudokuQueue; //Singleton
private var queue:Vector.<Task>
public function SudokuQueue()
{
queue = new Vector.<Task>();
}
/**
* シングルトンを取得する方法
* @return
*/
public static function getInstance():SudokuQueue
{
if (instance == null)
{
instance = new SudokuQueue();
}
return instance;
}
/**
* 新しいタスクの追加
* @param cell 対象表示セル
* @param func 実行関数
* @param arg 対象となる候補
*/
public function push(func:Function, arg:* = null):void
{
queue.push(new Task(func, arg));
}
/**
* Vectorの先頭Taskを削除し､同時に実行する｡
*/
public function shift(e:Event=null):void
{
if (queue.length == 0)
{
return;
}
var t:Task = queue.shift();
t.call();
}
/**
* flush
* @return
*/
public function flush():void
{
queue = new Vector.<Task>();
}
override public function toString():String
{
return "left tasks: " + queue.length;
}
}
//}
//import sudoku.AbstractDisplayedCell;
class Task
{
private var _func:Function;
private var _arg:* ;
public function Task(func:Function, arg:* = null)
{
_func = func;
_arg = arg;
}
public function call():void {
if (_arg == null)
{
_func.call();
}
else
{
_func.call(null, _arg);
}
}
}
//package utils
//{
class TermaryConverter
{
public function TermaryConverter()
{
}
/**
* 3進数に表した時の任意の桁の数字(0..2)を返す
* @param n 変換する符号なし整数値
* @param digit 対象とする桁数
* @return
*/
public static function getDigitOfUnsignedInt(n:uint, digit:uint):int
{
if (digit != 0)
{
n %= Math.pow(3, digit);
}
n %= 3;
return n;
}
public static function convertFromDigits(...digits):uint
{
var result:uint = 0;
var len:int = digits.length;
var pos:int = len;
for (var i:int = 0; i < len; i++)
{
pos--;
result += uint(digits[i]) * Math.pow(3, pos);
}
return result;
}
}
//}
//package events
//{
//import flash.events.Event;
class AllSolvedEvent extends Event
{
public static const TYPE:String = "All Solved";
public function AllSolvedEvent(type:String = TYPE, bubbles:Boolean=false, cancelable:Boolean=false)
{
super(type, bubbles, cancelable);
}
public override function clone():Event
{
return new AllSolvedEvent(type, bubbles, cancelable);
}
public override function toString():String
{
return formatToString("AllSolvedEvent", "type", "bubbles", "cancelable", "eventPhase");
}
}
//}
//package events
//{
import flash.events.Event;
class UnsolvableEvent extends Event
{
public static const TYPE:String = "unsolvable";
public function UnsolvableEvent(type:String = TYPE , bubbles:Boolean=false, cancelable:Boolean=false)
{
super(type, bubbles, cancelable);
}
public override function clone():Event
{
return new UnsolvableEvent(type, bubbles, cancelable);
}
public override function toString():String
{
return formatToString("Unsolvable", "type", "bubbles", "cancelable", "eventPhase");
}
}
//}