/**
* Copyright codeonwort ( http://wonderfl.net/user/codeonwort )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/9J1R
*/
package {
import flash.text.TextFormat;
import flash.text.TextField;
import flash.display.Graphics;
import flash.display.Sprite;
public class NonominoSudokuTest extends Sprite {
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
public function NonominoSudokuTest() {
// write as3 code here..
/*table = [
[1,2,3,4,5,6,7,8,9],
[7,8,9,1,2,3,4,5,6],
[4,5,6,7,8,9,1,2,3],
[3,1,2,6,4,5,9,7,8],
[9,7,8,3,1,2,6,4,5],
[6,4,5,9,7,8,3,1,2],
[2,3,1,5,6,4,8,9,7],
[8,9,7,2,3,1,5,6,4],
[5,6,4,8,9,7,2,3,1]]*/
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]
canvas = new Sprite
canvas.x = canvas.y = 30
addChild(canvas)
addChild(debug = new TextField)
debug.y = 10
debug.autoSize = "left"
debug.text = "debug: no log"
generate()
render(canvas, 40)
}
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))
}
}
solve()
}
private function render(canvas:Sprite, 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()
for each(var tf:TextField in texts){
removeChild(tf)
}
for(i=0; i<9; i++){
for(j=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)
}
}
}
// 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 cnt:int = 0, 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 --
if(idx == -1){
// no solution
solutionFound = false
break
}
continue
}
table[cell.i][cell.j] += 1
if(validSoFar(cell.i, cell.j)){
// go next cell
idx++
if(idx > maxIdx) maxIdx = idx
if(idx == cells.length){
solutionFound = true
break
}
}
cnt ++
}
//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
/* do not check all cells, just cells related with current candidate cell.
// check pieces
var color:int, num:int
for(var i:int=0; i<9; i++){
for(var j:int=0; j<9; j++){
validationTable[i][j] = false
}
}
for(i=0; i<9; i++){
for(j=0; j<9; j++){
color = colorMap[i][j] - 1;
num = table[i][j] - 1;
if(num == -1) continue
if(validationTable[color][num]) return false;
validationTable[color][num] = true;
}
}
// check lines
for(i=0; i<9; i++){
for(j=0; j<9; j++) validationLineX[j] = validationLineY[j] = false;
for(j=0; j<9; j++){
num = table[i][j] - 1;
if(num == -1) continue
if(validationLineX[num]) return false;
validationLineX[num] = true;
}
for(j=0; j<9; j++){
num = table[j][i] - 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
}
}
