flash on 2010-10-22

/**
 * Copyright uwi ( http://wonderfl.net/user/uwi )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/wh2d
 */

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.events.Event;
    import flash.events.MouseEvent;
    import flash.display.BitmapData;
    import flash.display.Bitmap;
    import flash.geom.Rectangle;
    import com.bit101.components.*;

    public class NQueen extends Sprite {
        private var _tf : TextField;
        private var _stop : PushButton;
        private var _canvas : BitmapData;

        public function NQueen() {
            _W = stage.stageWidth;
            _H = stage.stageHeight;
            _canvas = new BitmapData(_W, _H, false, 0xeeeeee);
            addChild(new Bitmap(_canvas));
            
            _stop = new PushButton(this, 30, 60, "STOP", function(e:MouseEvent) : void {
                removeEventListener(Event.ENTER_FRAME, onEnterFrame);
            });

            _tf = new TextField();
            _tf.width = 100;
            _tf.height = 50;
            addChild(_tf);
            
            solve(12);
        }
        
        private var _cur : Vector.<Number>; // 現在の状態
//        private var _opt : Vector.<Number>; // 最適状態
        private var _curv : Number;
        private var _n : uint;
        
        private var _W : Number;
        private var _H : Number;
        private var _L : Number;
        private var _R : Number;
        private var _T : Number;
        private var _B : Number;
        
        // n*nのn-Queen問題を解いて解をひとつ求める。
        private function solve(n : uint) : void
        {
            _n = n;
            _cur = new Vector.<Number>(n * n);
            var i : uint, j : uint;
            for(i = 0;i < n;i++){
                for(j = 0;j < n;j++){
                    _cur[i*n+j] = 1;
//                    _opt[i*n+j] = 0.5;
                }
            }
            _curv = eval(_cur, n);
            _ll = Math.log(_n) / Math.log(2);
            
            _L = _W / 2 - _W * 0.3;
            _R = _W / 2 + _W * 0.3;
            _T = _H / 2 - _H * 0.3;
            _B = _H / 2 + _H * 0.3;
        
            addEventListener(Event.ENTER_FRAME, onEnterFrame);
        }
        
        private var _ll : Number;
        
        // MCMC
        private function onEnterFrame(e : Event) : void
        {
            for(var i : uint = 0;i < 100;i++){
                step();
            }
//            _tem *= 1.001;
            _tem += 0.003;
            draw();
            if(_curv == 0){
                removeEventListener(Event.ENTER_FRAME, onEnterFrame);
            }
        }
        
        private var _tem : Number = 0.01;
         
        private function draw() : void
        {
            _tf.text = _curv.toString() + "\n" + _tem;
            
            var i : uint, j : uint;
            _canvas.lock();
            _canvas.fillRect(_canvas.rect, 0xeeeeee);
            for(i = 0;i < _n;i++){
                for(j = 0;j < _n;j++){
                    _canvas.fillRect(new Rectangle(
                        _L + (_R - _L) / _n * i,
                        _T + (_B - _T) / _n * j,
                        (_R - _L) / _n,
                        (_B - _T) / _n), 0x100010 + (int(250 * _cur[i*_n+j])<<8)
                        );
                }
            }
            _canvas.unlock();
        }
  
  /*
        private function step() : void
        {
            // 候補づくり
            // ランダムにセルを選んで適当にうつす
            var ind : uint = Math.random() * _n;
            var oc : uint;
            for(var i : uint = 0;i < _n;i++){
                if(_cur[ind*_n+i] == 1){
                    _cur[ind*_n+i] = 0;
                    oc = i;
                    break;
                }
            }

//            _cur[ind] = Math.sin(Math.random() * Math.PI * 2) / 2 + 0.5;
            var nind : uint = int(Math.random() * _n);
            _cur[ind*_n+nind] = 1;
//            _cur[ind] = Math.random() * 3 < 1 ? 1 : 0;
            
            var nextv : Number = eval(_cur, _n);
            // 遷移確率を計算
            var p : Number = Math.exp(-(nextv - _curv) * _tem);
            if(Math.random() < p){
                // 遷移
                _curv = nextv;
            }else{
                // 遷移しない場合
                _cur[ind*_n+nind] = 0;
                _cur[ind*_n+oc] = 1;
            }
        }
        */
        private function step() : void
        {
            // 候補づくり
            // ランダムにセルを選んで適当にうつす
            var ind : uint = Math.random() * _n * _n;
            var oc : Number = _cur[ind];
//            _cur[ind] = Math.random();
//            _cur[ind] = Math.pow(Math.random(), _ll);
            _cur[ind] = Math.sin(Math.random() * Math.PI * 2) / 2 + 0.5;
//            _cur[ind] = Math.random() * _n < 1 ? 1 : 0;
//            _cur[ind] = Math.random() * 3 < 1 ? 1 : 0;
            
            var nextv : Number = eval(_cur, _n);
            // 遷移確率を計算
            var p : Number = Math.exp(-(nextv - _curv) * _tem);
            if(Math.random() < p){
                // 遷移
                _curv = nextv;
            }else{
                // 遷移しない場合
                _cur[ind] = oc;
            }
        }
        
        // 評価値の計算
        private function eval(state : Vector.<Number>, n : uint) : Number
        {
            var i : uint, j : uint;
            var ret : Number = 0;
            // 右上向き対角線
            var diagsumP : Vector.<Number> = new Vector.<Number>(2*n);
            // 左上向き対角線
            var diagsumM : Vector.<Number> = new Vector.<Number>(2*n);
            for(i = 0;i < 2 * n;i++){
                diagsumP[i] = 0;
                diagsumM[i] = 0;
            }
            var x : Number;

            for(i = 0;i < n;i++){
                var sum : Number;
                
                // rowsum
                sum = -1;
                for(j = 0;j < n;j++){
                    sum += state[i*n+j];
                }
                ret += Math.sqrt(Math.abs(sum)) * 1;
                
                // colsum
                sum = -1;
                for(j = 0;j < n;j++){
                    sum += state[j*n+i];
                }
                ret += Math.abs(sum) * 1;
 
                for(j = 0;j < n;j++){
                    diagsumP[i+j] += state[i*n+j];
                    diagsumM[i-j+n] += state[i*n+j];
                    x = 0.5 - Math.abs(state[i*n+j] - 0.5);
                    ret += 1.5 * Math.sqrt(x) / n;
                }
            }
            for(i = 0;i < 2 * n;i++){
                if(diagsumP[i] > 0.5){
                    ret += Math.sqrt(Math.abs(diagsumP[i] - 1));
                }else{
                    ret += Math.sqrt(Math.abs(diagsumP[i]));
                }
                if(diagsumM[i] > 0.5){
                    ret += Math.sqrt(Math.abs(diagsumM[i] - 1));
                }else{
                    ret += Math.sqrt(Math.abs(diagsumM[i]));
                }
            }
            
            return ret;
        }

        private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
        }
    }
}