LightsOut Solver

forked:2
favorite:7
lines:201
license : MIT License
modified : 2010-03-20 16:43:43

Embed: Tweet

// 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");
        }
    }
}

Code Fullscreen

Preview Fullscreen