Backtracking is too slow this flash crashes sometimes due to execution time limit. Anyone have a idea to improve search performance or other nonomino sudoku generation algorithms?
Take a look at my prime number app with concurrency. http://wonderfl.net/c/jszZ
If you generate your puzzle on a separate thread you can keep your main thread alive and even showing progress without crashing the Flash Player.
Yeah, the solve algorithm needs some re-working... I set up a worker thread with visible progress bar and sometimes it seems like it's NEVER going to finish.
http://wonderfl.net/c/3Z8w
I do not know If there is a bug in my backtracking or It just takes a very long time to get finished.
I have not thought about concurrency programming. I'll first go tutorials for concurrency. Thanks to your proposal.
+ Maybe there is some color arrangements that have no solution and such boards may take very long time to assure you cannot find proper number assignment.
Well I'm just thinking it can be optimized. Right now you are checking every diget in every spot. That is, even if there is a 1 already in that row and group, you still check if a 1 works.
In other words, you are checking all permutations with repetitions rather then without. That's a difference of 9^81to 9*9!
9*9! = 3,265,920 which is big, but manageable for the computer.
9^81 = 1.966e77 which isn't manageable by anything.
Before starting backtracking only red area is filled and 72 empty cells are filled one by one, I thought holding possible numbers for each empty cell would not speed-up the backtracking so much.
After reading your comment I am thinking 'what about whenever I put a number in a empty cell, remove that number for same colored, same row, same column empty cells' possible candidates.'
I hope this additional prunning will overcome the overhead of dynamically adding/removing candidates and greatly speed-up the generation time. It's worth to try. thanks.
Yeah. I was thinking maybe having 9 arrays already filled with 1 through 9 and then just sorting those arrays till they fit. That is, never change a value, instead move that value to a different position.
It's no effective to dynamically adding/removing candidates for future empty cells, at least for my implementation. My only remaining option is to rearrange empty cell vector in a order that will prune more future cells. But as I already tried, rearranging empty cells in color order or random order didn't work.
Just 72 cells is too many.
I came back to this problem again today. It's not 9*9! possible arrangements... it's 9!*9! which is 131,681,894,400 (a little bit bigger). Still, that's much better overall. I'm still working out how to program this though.
I gived up to use backtracking and generated nonomino board another way. But I'm still wondering If a clever backtrakcing can fill nonomino boards in reasonable time.
I was considering trying a method to do a random fill (still with only 1-9 in each color) and then applying a simple sort algorithm of some kind to it and see if that could speed up the solution (while still giving us something a little more random). Because while there are some 131 billion possible combinations, there are also going to me millions of possible solutions. So we just need to figure out what those look like and try to jump close to one from the start.
Embed
/**
* 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
}
}