LightsOut Solver
/**
* Copyright uwi ( http://wonderfl.net/user/uwi )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/cF16
*/
// forked from uwi's LightsOut Solver
package {
import flash.display.*;
import flash.events.*;
import flash.text.TextField;
import com.bit101.components.*;
public class LightsOutSolver extends Sprite {
private var _tf : TextField;
private var _nrow : uint;
private var _ncol : uint;
private var _lights : Array;
private var _sliderC : HSlider;
private var _sliderR : VSlider;
private var _solved : Label;
private var _ansLayer : Shape;
private const FILLCOLOR : uint = 0xaa55aa;
private const ANSCOLOR : uint = 0x99ffff;
public function LightsOutSolver() {
/*
_tf = new TextField();
_tf.width = 465;
_tf.height = 465;
addChild(_tf);
*/
_sliderC = new HSlider(this, 20, 260, redraw);
_sliderR = new VSlider(this, 260, 20, redraw);
_sliderC.maximum = 10; _sliderC.value = 5; _sliderC.minimum = 3;
_sliderR.maximum = 10; _sliderR.value = 5; _sliderR.minimum = 3;
_sliderC.setSize(200, 20);
_sliderR.setSize(20, 200);
redraw();
var solve : PushButton = new PushButton(this, 60, 330, "solve", onSolveClick);
var fill : PushButton = new PushButton(this, 60, 370, "fill", onFillClick);
var clear : PushButton = new PushButton(this, 60, 410, "clear", onClearClick);
_solved = new Label(this, 60, 310);
stage.addEventListener(MouseEvent.CLICK, onClick);
_ansLayer = new Shape();
_ansLayer.x = 230; _ansLayer.y = 230;
addChild(_ansLayer);
}
private function onSolveClick(e : MouseEvent) : void
{
var ans : Array = solveLightsOut(_nrow, _ncol, _lights);
if(ans != null){
_solved.text = "Solved!";
var g : Graphics = _ansLayer.graphics;
g.clear();
g.lineStyle(2, 0x000000);
var i : uint;
for(i = 0;i <= _ncol;i++){
g.moveTo(20 + 200 / _ncol * i, 20);
g.lineTo(20 + 200 / _ncol * i, 220);
}
for(i = 0;i <= _nrow;i++){
g.moveTo(20, 20 + 200 / _nrow * i);
g.lineTo(220, 20 + 200 / _nrow * i);
}
var r : uint, c : uint;
for(r = 0;r < _nrow;r++){
for(c = 0;c < _ncol;c++){
if(ans[r*_ncol+c] == 1){
g.beginFill(ANSCOLOR);
g.drawRect(
20 + 200 * c / _ncol,
20 + 200 * r / _nrow,
200 / _ncol,
200 / _nrow
);
g.endFill();
}
}
}
}else{
_solved.text = "Insoluble!";
}
}
private function onFillClick(e : MouseEvent) : void
{
for(var r : uint = 0;r < _nrow;r++){
for(var c : uint = 0;c < _ncol;c++){
_lights[r * _ncol + c] = 1;
paint(r, c, FILLCOLOR);
}
}
}
private function onClearClick(e : MouseEvent) : void
{
for(var r : uint = 0;r < _nrow;r++){
for(var c : uint = 0;c < _ncol;c++){
_lights[r * _ncol + c] = 0;
paint(r, c, 0xffffff);
}
}
}
private function onClick(e : MouseEvent) : void
{
var r : int = (stage.mouseY - 20) / 200 * _nrow;
var c : int = (stage.mouseX - 20) / 200 * _ncol;
if(r < 0 || r >= _nrow || c < 0 || c >= _ncol)return;
_lights[r * _ncol + c] = 1 - _lights[r * _ncol + c];
paint(r, c, _lights[r * _ncol + c] == 1 ? FILLCOLOR : 0xffffff);
}
private function paint(r : uint, c : uint, color : uint) : void
{
graphics.beginFill(color);
graphics.drawRect(
20 + 200 * c / _ncol,
20 + 200 * r / _nrow,
200 / _ncol,
200 / _nrow
);
graphics.endFill();
}
private function redraw(e : Event = null) : void
{
_nrow = _sliderR.value;
_ncol = _sliderC.value;
graphics.clear();
graphics.lineStyle(2, 0x000000);
var i : uint;
for(i = 0;i <= _ncol;i++){
graphics.moveTo(20 + 200 / _ncol * i, 20);
graphics.lineTo(20 + 200 / _ncol * i, 220);
}
for(i = 0;i <= _nrow;i++){
graphics.moveTo(20, 20 + 200 / _nrow * i);
graphics.lineTo(220, 20 + 200 / _nrow * i);
}
_lights = new Array(_nrow * _ncol);
for(i = 0;i < _lights.length;i++)_lights[i] = 0;
}
// solve simultaneous equations modulo 2.
private function solveLightsOut(r : uint, c : uint, ptn : Array) : Array
{
if(ptn.length != r * c)return null;
var ret : Array = ptn.concat();
var mat : Array = [];
var i : uint, j : uint, k : uint;
var N : uint = r * c;
for(i = 0;i < N;i++){
var row : Array = new Array(N);
for(j = 0;j < N;j++)row[j] = 0;
row[i] = 1;
if(i % c > 0)row[i-1] = 1;
if(i % c < c - 1)row[i+1] = 1;
if(i >= c)row[i-c] = 1;
if(i < c * (r - 1))row[i+c] = 1;
mat.push(row);
}
// forward elimination
for(i = 0;i < N;i++){
for(j = i;j < N;j++){
if(mat[j][i] == 1)break;
}
if(j == N)break;
if(i != j){
for(k = 0;k < N;k++){
var dd : uint = mat[i][k];
mat[i][k] = mat[j][k];
mat[j][k] = dd;
}
dd = ret[i];
ret[i] = ret[j];
ret[j] = dd;
}
for(j = i + 1;j < N;j++){
if(mat[j][i] == 1){
for(k = 0;k < N;k++){
mat[j][k] ^= mat[i][k];
}
ret[j] ^= ret[i];
}
}
}
// determine whether solvable or not.
var valid : int = i;
for(i = N - 1;i > valid;i--){
if(ret[i] == 1){
return null;
}
}
var limMinus : uint = 1 << (N - i);
var minrep : Array = null;
var minct : uint = 9999999;
// Considering DOF, returns minimum solution.
for(var code : uint = 0;code < limMinus;code++){
var rep : Array = ret.concat();
for(i = code, k = N - i;i > 0;i >>= 1, k--){
rep[k] = i & 1;
}
// backward substitution
for(i = N - 1;i >= 1;i--){
for(j = 0;j < i;j++){
if(mat[j][i] == 1){
rep[j] ^= rep[i];
}
}
}
var ct : uint = 0;
for each(i in rep)ct += i;
if(ct < minct){
minct = ct;
minrep = rep;
}
}
return minrep;
}
private function tr(...o : Array) : void
{
_tf.appendText(o + "\n");
}
}
}