Nonomino Sudoku w/ Concurrency

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

// forked from codeonwort's Nonomino Sudoku
/**
 * Copyright codeonwort ( http://wonderfl.net/user/codeonwort )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/3Z8w
 */

package {
    import com.bit101.components.HRangeSlider;
    
    import flash.display.Graphics;
    import flash.display.Sprite;
    import flash.events.Event;
    import flash.system.MessageChannel;
    import flash.system.Worker;
    import flash.system.WorkerDomain;
    import flash.text.TextField;
    import flash.text.TextFormat;
    
    public class NonominoSudokuTest extends Sprite 
    {
        public static const MAXPROGRESS:String = "maxProgress";
        public static const PROGRESS:String = "progress";
        public static const RENDER:String = "render";
        public static const COMPLETE:String = "complete";
        public static const FAILED:String = "failed";
        
        private var progress:HRangeSlider;
        
        private var table:Array;
        private var texts:Array = [];
        private var canvas:Sprite;
        
        private var colorMap:Array;
        private var colorFunction:Array;
        private var pieceMap:Vector.<Vector.<Cell>>;
        
        private var validationLineX:Array, validationLineY:Array;
        
        private var debug:TextField;
        
        private var worker:Worker;
        private var fromBack:MessageChannel;
        private var fromMain:MessageChannel;
        
        public function NonominoSudokuTest() 
        {
            if(Worker.current.isPrimordial)
            {
                initView();
                initMain();
            }
            else
            {
                initWorker();
            }
        }
        
        private function initView():void
        {
            progress = new HRangeSlider(this, 10, 35);
            progress.width = 370;
        }
        
        private function initMain():void
        {
            worker = WorkerDomain.current.createWorker(this.loaderInfo.bytes);
            fromBack = worker.createMessageChannel(Worker.current);
            fromMain = Worker.current.createMessageChannel(worker);
            
            worker.setSharedProperty("btm", fromBack);
            worker.setSharedProperty("mtb", fromMain);
            
            fromBack.addEventListener(Event.CHANNEL_MESSAGE, onBackToMain);
            
            worker.start();
        }
        
        
        private function onBackToMain(event:Event):void
        {
            if(fromBack.messageAvailable)
            {
                var header:String = fromBack.receive();
                if(header == RENDER)
                {
                    colorMap = fromBack.receive();
                    colorFunction = fromBack.receive();
                    
                    canvas = new Sprite();
                    canvas.x = canvas.y = 60;
                    addChild(canvas);
                    
                    addChild(debug = new TextField());
                    debug.y = 10;
                    debug.autoSize = "left";
                    debug.text = "Solving...";
                    
                    render(40);
                }
                else if(header == COMPLETE)
                {
                    removeChild(progress);
                    debug.text = "Solved!";
                    table = fromBack.receive();
                    addSolution(40);
                }
                else if(header == PROGRESS)
                {
                    progress.lowValue = int(fromBack.receive() * 100);
                }
                else if(header == MAXPROGRESS)
                {
                    progress.highValue = int(fromBack.receive() * 100);
                }
                else if(header == FAILED)
                {
                    removeChild(progress);
                    debug.text = "No Solution Found!";
                }
            }
        }
        
        private function render(cellSize:Number):void 
        {
            var g:Graphics = canvas.graphics;
            g.clear();
            g.lineStyle(0, 0x0);
            for(var i:int=0; i<9; i++)
            {
                for(var j:int=0; j<9; j++)
                {
                    g.beginFill(colorFunction[colorMap[i][j]-1], 0.75);
                    g.drawRect(j*cellSize, i*cellSize, cellSize, cellSize);
                    g.endFill();
                }
            }
            
            g.lineStyle(4, 0x0);
            g.drawRect(0, 0, cellSize * 9, cellSize * 9);
            g.lineStyle();
        }
        
        private function addSolution(cellSize:Number):void
        {
            for each(var tf:TextField in texts)
            {
                removeChild(tf);
            }
            for(var i:int=0; i<9; i++)
            {
                for(var j:int=0; j<9; j++)
                {
                    tf = new TextField();
                    tf.autoSize = "left";
                    tf.defaultTextFormat = new TextFormat(null, 20);
                    tf.text = table[i][j] + "";
                    tf.x = j * cellSize + cellSize/2 - tf.width/2;
                    tf.y = i * cellSize + cellSize/2 - tf.height/2;
                    canvas.addChild(tf);
                    texts.push(tf);
                }
            }
        }
        
        //////////
        //  WORKER
        //////////
        
        private function initWorker():void 
        {
            fromBack = Worker.current.getSharedProperty("btm");
            fromMain = Worker.current.getSharedProperty("mtb");
            
            fromMain.addEventListener(Event.CHANNEL_MESSAGE, onMainToBack);
            
            colorMap = [
                [1,1,1,2,2,2,3,3,3],
                [1,1,1,2,2,2,3,3,3],
                [1,1,1,2,2,2,3,3,3],
                [4,4,4,5,5,5,6,6,6],
                [4,4,4,5,5,5,6,6,6],
                [4,4,4,5,5,5,6,6,6],
                [7,7,7,8,8,8,9,9,9],
                [7,7,7,8,8,8,9,9,9],
                [7,7,7,8,8,8,9,9,9]];
            colorFunction = [0xff0000, 0xff8800, 0xffff00, 0x00ff00, 0x00ffff, 0x0000ff, 0xff00ff, 0x8000ff, 0x0b173b];
            
            generate();
        }
        
        private function onMainToBack(event:Event):void
        {
            if(fromMain.messageAvailable)
            {
                var header:String = fromMain.receive();
                // Handle messages here...  not sure if we need any.
            }
        }
        
        private function generate():void 
        {
            var i:int, j:int, c:int;
            
            validationLineX = [];
            validationLineY = [];
            
            for(i=0; i<100; i++)
                rotate(2 + Math.random() * 6, 2 + Math.random() * 6);
            
            pieceMap = new Vector.<Vector.<Cell>>();
            for(i=0; i<9; i++) pieceMap[i] = new Vector.<Cell>();
            for(i=0; i<9; i++)
            {
                for(j=0; j<9; j++)
                {
                    c = colorMap[i][j] - 1;
                    pieceMap[c].push(new Cell(i, j));
                }
            }
            
            fromBack.send(RENDER);
            fromBack.send(colorMap);
            fromBack.send(colorFunction);
            
            solve();
            
            fromBack.send(COMPLETE);
            fromBack.send(table);
        }
        
        // top-left corner: (0, 0)
        // bottom-right corner: (9, 9)
        // valid range: cx, cy ∈ [2, 7]
        private function rotate(cx:int, cy:int):void 
        {
            if(cx < 2 || cx > 7) 
                return;
            if(cy < 2 || cy > 7) 
                return;
            var xlist:Array = [cx-2, cx-1, cx, cx+1, cx+1, cx+1, cx+1, cx, cx-1, cx-2, cx-2, cx-2];
            var ylist:Array = [cy-2, cy-2, cy-2, cy-2, cy-1, cy, cy+1, cy+1, cy+1, cy+1, cy, cy-1];
            var i:int, j:int, cand:Array = [];
            for(i=0; i<9; i++) 
                cand[i] = colorMap[i].concat();
            var first:int = cand[ylist[0]][xlist[0]];
            for(i=0; i<11; i++)
            {
                cand[ylist[i]][xlist[i]] = cand[ylist[i+1]][xlist[i+1]];
            }
            cand[ylist[11]][xlist[11]] = first;
            
            var valid:Boolean = true;
            var visited:Array = [];
            for(i=0; i<9; i++){
                visited[i] = [];
                for(j=0; j<9; j++) 
                    visited[i][j] = false;
            }
            var size:uint;
            for(i=0; i<9; i++)
            {
                for(j=0;j<9;j++)
                {
                    if(visited[i][j] == false)
                    {
                        size = getPieceSize(i, j);
                        if(size != 9)
                        {
                            valid = false;
                            break;
                        }
                    }
                }
            }
            if(valid){
                colorMap = cand;
            }
            function getPieceSize(i:int, j:int):uint 
            {
                var n:uint = 1;
                if(i<0 || i>=9 || j<0 || j>=9 || visited[i][j]) 
                    return 0;
                visited[i][j] = true;
                if(i>0 && cand[i][j] == cand[i-1][j]) 
                    n += getPieceSize(i-1, j);
                if(i<8 && cand[i][j] == cand[i+1][j]) 
                    n += getPieceSize(i+1, j);
                if(j>0 && cand[i][j] == cand[i][j-1]) 
                    n += getPieceSize(i, j-1);
                if(j<8 && cand[i][j] == cand[i][j+1]) 
                    n += getPieceSize(i, j+1);
                return n;
            }
        }
        
        private function solve():void 
        {
            var i:int, j:int;
            
            // clear the table
            table = [];
            for(i=0; i<9; i++)
            {
                table[i] = [];
                for(j=0; j<9; j++)
                {
                    table[i][j] = 0;
                }
            }
            
            // fill one color area
            var flood_count:int = 1;
            floodFill(0, 0);
            function floodFill(i:int, j:int):void 
            {
                table[i][j] = flood_count;
                flood_count += 1;
                if(i>0 && table[i-1][j] == 0 && colorMap[i][j] == colorMap[i-1][j]) 
                    floodFill(i-1, j);
                if(i<8 && table[i+1][j] == 0 && colorMap[i][j] == colorMap[i+1][j]) 
                    floodFill(i+1, j);
                if(j>0 && table[i][j-1] == 0 && colorMap[i][j] == colorMap[i][j-1]) 
                    floodFill(i, j-1);
                if(j<8 && table[i][j+1] == 0 && colorMap[i][j] == colorMap[i][j+1]) 
                    floodFill(i, j+1);
            }
            
            // backtracking
            backtrack();
        }
        
        private function backtrack():void 
        {
            var cells:Vector.<Cell> = getEmptyCells();
            var cell:Cell;
            var idx:int = 0, cellValue:int;
            var solutionFound:Boolean;
            
            var maxIdx:int=0;
            
            while(true)
            {
                cell = cells[idx];
                if(table[cell.i][cell.j] >= 9)
                {
                    // have to backtrack
                    table[cell.i][cell.j] = 0;
                    idx --;
                    
                    fromBack.send(PROGRESS);
                    fromBack.send(idx / cells.length);
                    
                    if(idx == -1)
                    {
                        // no solution
                        fromBack.send(FAILED);
                        solutionFound = false;
                        break;
                    }
                    continue;
                }
                table[cell.i][cell.j] += 1;
                if(validSoFar(cell.i, cell.j))
                {
                    // go next cell
                    idx++;
                    
                    fromBack.send(PROGRESS);
                    fromBack.send(idx / cells.length);
                    
                    if(idx > maxIdx) {
                        maxIdx = idx;
                        
                        fromBack.send(MAXPROGRESS);
                        fromBack.send(maxIdx / cells.length);
                    }
                    if(idx == cells.length)
                    {
                        solutionFound = true;
                        break;
                    }
                }
            }
            //debug.text = "loop iter: " + cnt + "      max idx: " + maxIdx
        }
        
        private function validSoFar(candI:int, candJ:int):Boolean 
        {
            var i:int, color:int, num:int;
            var piece:Vector.<Cell>;
            
            color = colorMap[candI][candJ] - 1;
            piece = pieceMap[color];
            for(i=0; i<9; i++) 
                validationLineX[i] = false;
            for(i=0; i<9; i++)
            {
                num = table[piece[i].i][piece[i].j] - 1;
                if(num == -1) 
                    continue;
                if(validationLineX[num]) 
                    return false;
                validationLineX[num] = true;
            }
            // check cross line centered at (candX, candY)
            for(i=0; i<9; i++) 
                validationLineX[i] = validationLineY[i] = false;
            for(i=0; i<9; i++)
            {
                num = table[candI][i] - 1;
                if(num == -1) 
                    continue;
                if(validationLineX[num]) 
                    return false;
                validationLineX[num] = true;
            }
            for(i=0; i<9; i++)
            {
                num = table[i][candJ] - 1;
                if(num == -1) 
                    continue;
                if(validationLineY[num]) 
                    return false;
                validationLineY[num] = true;
            }
            return true;
        }
                
        private function getEmptyCells():Vector.<Cell> 
        {
            var cells:Vector.<Cell> = new Vector.<Cell>();
            for(var i:int=0; i<9; i++)
            {
                for(var j:int=0; j<9; j++)
                {
                    if(table[i][j] == 0)
                    {
                        cells.push(new Cell(i, j));
                    }
                }
            }
            return cells;
        }
        
    }
    
}

class Cell 
{
    public var i:int, j:int;
    public function Cell(ic:int, jc:int) 
    {
        i = ic;
        j = jc;
    }
}