const turtle = new Turtle();
const text = new Text();

// make all types (2x3,2x4,2x5, 3x3, 3x4 etc)
const types = [];
const a = getRange(5);
for(let aa=0;aa<a.length;aa++) {
    for(let bb=0;bb<a.length;bb++) {
        types.push([aa+2, bb+2]);
    }
}

// returns array containing 0...n
function getRange(total) {
    var arr = [];
    for (let i = 0; i < total; ++i) arr.push(i);
    return arr;
}

////////////////////////////////////////////////////////////////
// Sudoku generator + solver. Created by Mark Knol 2020
// https://turtletoy.net/turtle/5098380d82
////////////////////////////////////////////////////////////////
class Sudoku {
    constructor() {
        const type = 6; // min=0, max=23, step=1
        this.type = type;
        const seed = 1; // min=1, max=200, step=1
        this.seed = seed;
        const useLetters = 0; // min=0, max=1, step=1  (No, Yes)
        this.hardMode = useLetters;
        this.gridBlockSize = [types[type][0], types[type][1]];
        this.gridBlockCount = this.gridBlockSize[0] * this.gridBlockSize[1];
        this.gridTotalCount = this.gridBlockCount * this.gridBlockCount;
        //const difficulty = 0.8; // min=0.6, max=0.95, step=0.05
        //this.difficulty = difficulty
        const showSolution = 0; // min=0, max=1, step=1 (No, Yes)
        this.showSolution = showSolution;
        
        this.random = new Random(seed);
        this.grid = [];
        this.letters = (getRange(100).map(v => String.fromCharCode(v + 97)));
        
        // 0...gridBlockCount
        this.checks = getRange(this.gridBlockCount);
        
        this.generate(this.grid);
        this.valid = this.isValidSudoku(this.grid);
    }
    
    // check if row/colum is correct (has 0-9 all once)
    isValidPos(grid, pos, horizontal) {
        const check = this.checks.slice();
        for (let x=0; x<this.gridBlockCount; x++) {
            const value = this.grid[horizontal ? pos * this.gridBlockCount + x : x * this.gridBlockCount + pos];
            const idx = check.indexOf(value)
            if (idx >= 0) {
                check.splice(idx, 1);
            } else {
                return false;
            }
        }
        return true;
    }
    
    // check if block (section of grid) is correct (has 0-9 all once)
    isValidBlock(grid, row, col) {
        const check = this.checks.slice();
        const gridBlockCount = this.gridBlockCount;
        const gridBlockSize = this.gridBlockSize;
        for (let y=0; y<gridBlockSize[1]; y++) {
            for (let x=0; x<gridBlockSize[0]; x++) {
                const value = grid[(y+row*gridBlockSize[1]) * gridBlockCount + (x+col*gridBlockSize[0])];
                const idx = check.indexOf(value)
                if (idx >= 0) {
                    check.splice(idx, 1);
                } else {
                    return false;
                }
            }
        }
        return true;
    }
    
    // validate if grid is valid (rows, columns and grids are all correct)
    isValidSudoku(grid) {
        const gridBlockCount = this.gridBlockCount;
        const gridBlockSize = this.gridBlockSize;
        // check horizontal and vertical rows
        for (let y=0; y<gridBlockCount; y++) {
            if (!this.isValidPos(grid, y, false)) return false;
            for (let x=0; x<gridBlockCount; x++) {
                if (!this.isValidPos(grid, x, true)) return false;
            }
        }
        // validate blocks
        for (let y=0; y<gridBlockSize[1]; y++) {
            for (let x=0; x<gridBlockSize[0]; x++) {
                if (!this.isValidBlock(grid, x, y)) return false;
            }
        }
        return true;
    }
    
    // generate a complete sudoku grid
    // based on <https://gamedev.stackexchange.com/a/138228>
    generate(grid) {
        const gridBlockSize = this.gridBlockSize;
        const gridBlockCount = this.gridBlockCount;
        const options = this.random.shuffle(this.checks.slice());
        
        // generate [1,2,3]. is used to offset a row of block in other blocks
        const shiftsY = this.random.shuffle(getRange(gridBlockSize[0]));
        
        // generate [1,2,3], [4,5,6], [7,8,9] and shuffles per block. is used to offset columns
        const shiftsX = [];
        for (let shift2=0; shift2<gridBlockSize[1]; ++shift2) {
            const values = this.random.shuffle(getRange(gridBlockSize[0]));
            values.forEach(v => shiftsX.push(shift2 * gridBlockSize[0] + v));
        }
        
        // generate [1,2,3], [4,5,6], [7,8,9] and shuffles per block. is used to offset rows
        const shiftsXY = [];
        for (let shift2=0; shift2<gridBlockSize[0]; ++shift2) {
            const values = this.random.shuffle(getRange(gridBlockSize[1]));
            values.forEach(v => shiftsXY.push(shift2 * gridBlockSize[1] + v));
        }
        
        // generate [1,2,3], [4,5,6], [7,8,9] and shuffles per block. is used to offset rows
        const shiftsXY2 = [];
        for (let shift2=0; shift2<gridBlockSize[0]; ++shift2) {
            const values = this.random.shuffle(getRange(gridBlockSize[1]));
            values.forEach(v => shiftsXY2.push(shift2 * gridBlockSize[1] + v));
        }
        
        for (let x=0; x<gridBlockCount; x++) {
            let row = 0;
            for (let shift1=0; shift1<gridBlockSize[0]; ++shift1) {
                for (let shift2=0; shift2<gridBlockSize[1]; ++shift2) {
                    grid[(shiftsXY[row++]) * gridBlockCount + shiftsX[x]] = options[(x + shiftsY[shift1] + shift2*gridBlockSize[0]) % gridBlockCount];
                }
            }
        }
    }
    
    draw(turtle, text, i) {
        const gridBlockSize = this.gridBlockSize;
        const gridBlockCount = this.gridBlockCount;
        const grid = this.grid;
        //const difficulty = this.difficulty;
        const showSolution = this.showSolution;
        if ( this.valid) {
            const x = i % gridBlockCount;
            const y = i / gridBlockCount | 0;
            
            const size = 8/gridBlockCount;
            const dist = size * 10;
            const dist2 = dist*2;
            const pos = [(-gridBlockCount/2 + x) * dist2 + dist, (-gridBlockCount/2 + y) * dist2 + dist];
            
            // sudoku labels
            if (i < this.gridTotalCount) {
                if (grid[i] != -1) {
                    const label = this.hardMode ? this.letters[grid[i]] : `${(grid[i] + 1)}`;
                    turtle.jump(label.length === 1 ? pos[0] : pos[0] - size * 2.5, pos[1]);
                    text.print(turtle, label, size * 0.25);
                }
            }
            
            // title
            if (i === 0) {
                const seedLabel = `${this.seed}`.padStart(3, '0')
                const label = `Sudoku ${gridBlockSize[0]}x${gridBlockSize[1]}  ~  #${seedLabel}`;
                turtle.jump(pos[0] - size, -90);
                text.print(turtle, label, .22);
            }
            pos[0] -= dist * 0.8;
            pos[1] -= dist;
            
            // grid lines
            if (y === 0 && x !== 0) {
                turtle.jump(pos[0], pos[1]);
                turtle.goto(pos[0], pos[1] + (dist2*gridBlockCount));
            }
            if (x === 0 && y !== 0) {
                turtle.jump(pos[0], pos[1]);
                turtle.goto(pos[0] + (dist2*gridBlockCount), pos[1]);
            }
            // double lines
            if (x%gridBlockSize[0]===0 && y %gridBlockSize[1]===0) {
                pos[0] -= 1*size;
                if (y === 0 && x !== 0) {
                    turtle.jump(pos[0], pos[1]);
                    turtle.goto(pos[0], pos[1] + (dist2*gridBlockCount));
                }
                pos[0] += 1*size;
                pos[1] -= 1*size;
                if (x === 0 && y !== 0) {
                    turtle.jump(pos[0], pos[1]);
                    turtle.goto(pos[0] + (dist2*gridBlockCount), pos[1]);
               }
            }
            
            return i < this.gridTotalCount - 1;
        } else {
            turtle.jump(-30,0);
            text.print(turtle, 'invalid', 0.5);
            return false;
        }
    }
}

let sudoku;
let solver;
function walk(i) {
    if (i === 0) {
        sudoku = new Sudoku();
        
        const gridLength = sudoku.grid.length;
        let tests = [
            test(sudoku, "0-n",() => getRange(gridLength)),
            test(sudoku, "random-1",() => new Random(sudoku.seed).shuffle(getRange(gridLength))),
            test(sudoku, "n-0",() => getRange(gridLength).reverse()),
            test(sudoku, "odd-even", () => {
                var arr = [];
                for (var i = 0; i < gridLength; ++i) {
                    arr.push(i / gridLength >= 0.5 ? (i*2)%gridLength : ((i*2)%gridLength) +1);
                }
                return arr;
            }),
            test(sudoku, "odd-even-reversed", () => {
                var arr = [];
                for (var i = 0; i < gridLength; ++i) {
                    arr.push(i / gridLength >= 0.5 ? (i*2)%gridLength : ((i*2)%gridLength) +1);
                }
                return arr.reverse();
            }),
            
            test(sudoku, "odd-even-grid-1", () => {
                var arr = [];
                t=gridLength;
                m = sudoku.gridBlockSize[0];
                for (var i = 0; i < t; ++i) {
                    arr.push(((i * m) % t) + Math.floor(i / t * m));
                }
                return arr;
            }),
            
            test(sudoku, "odd-even-grid-2", () => {
                var arr = [];
                t=gridLength;
                m = sudoku.gridBlockSize[1];
                for (var i = 0; i < t; ++i) {
                    arr.push(((i * m) % t) + Math.floor(i / t * m));
                }
                return arr;
            }),
          
            test(sudoku, "indexOf-lastIndexOf", () => {
                var arr = [];
                t=gridLength;
                m = sudoku.gridBlockSize[1];
                for (var i = 0; i < t; ++i) {
                    arr.push(sudoku.grid.indexOf(i));
                    arr.push(sudoku.grid.lastIndexOf(i));
                }
                for (var i = 0; i < t; ++i) {
                    arr.push(i);
                }
                return arr;
            }),
           
            test(sudoku, "index-weird-0..n", () => {
                var arr1 = [];
                var arr2 = [];
                var grid = sudoku.grid.slice();
                const rr1 = [];
                const rr2 = [];
                let c = 0;
                for (let i = 0; i < gridLength; ++i) {
                    let idx;
                    while((idx = grid.indexOf(i)) >= 0) {
                        (c%2==0 )?arr1.push(idx) : arr2.push(idx);
                        (c%2==0)?rr1.push(i) : rr2.push(i);
                        grid[idx] = -1;
                        c++;
                    }
                }
               // console.log("weird:");
                //console.log( [...rr1, ...rr2])
                //console.log( [...arr1, ...arr2])
                return [...arr1, ...arr2];
            }),
            test(sudoku, "random-2",() => new Random(sudoku.seed*2).shuffle(getRange(gridLength))),
        ];
        let testResult = tests[(sudoku.seed) % (tests.length -1)]();
        console.log("#"+sudoku.seed, "  best: " + testResult.totalRemoved + "/" + sudoku.grid.length + " = " + ((testResult.totalRemoved / sudoku.grid.length * 100 )|0) + "%", "strategy: "+testResult.strategy);
        /*
        testResult.sort((a, b) => b.totalRemoved - a.totalRemoved);
        const best = testResult[0];
        const worst = testResult[testResult.length-1];
        console.log("best: " + best.totalRemoved + "/" + sudoku.grid.length + " = " + ((best.totalRemoved / sudoku.grid.length * 100 )|0) + "%", "strategy: "+best.strategy);
        console.log("worst: " + worst.totalRemoved + "/" + sudoku.grid.length + " = " + ((worst.totalRemoved / sudoku.grid.length * 100 )|0) + "% ", "strategy: "+worst.strategy);
        */
        if (!sudoku.showSolution) {
            sudoku.grid = testResult.grid;
        }
        
    }
    
    return sudoku.draw(turtle, text, i);
}

// creates a solver, attempt to remove with given order until solver isnt valid anymore
function test(sudoku, strategy, removeOrderFn) {
    return () => {
        const solver = new Solver(sudoku.gridBlockSize);
        const removeOrder = removeOrderFn();
        const testGrid = sudoku.grid.slice();
        let totalRemoved = 0;
        while (removeOrder.length) {
            let index = removeOrder.pop();
            if (testGrid[index] != -1) {
                const testSolution = testGrid.map((v, i) => i != -1 && i != index ? [v] : getRange(sudoku.gridBlockCount));
                solver.solve(testSolution);
                if (solver.isAllSingle(testSolution)) {
                    // grid is still valid with this mutation, write open possibility in testGrid
                    testGrid[index] = -1;
                    totalRemoved ++;
                } 
            }
        }
        return { totalRemoved, strategy, grid: testGrid };
    }
}

// Solver. Folds a possibility grid until all possibility items have one item left
class Solver {
	constructor(gridBlockSize) {
	    this.gridBlockSize = gridBlockSize;
	    this.gridBlockCount = gridBlockSize[0] * this.gridBlockSize[1];
	}
	
	format(arr) {
		let s = [];
		let c = 0;
		for(let v of arr) {
			s.push( "[" + v.join(",") + "]" + (++c % (this.gridBlockCount) == 0 ? "\n":"") );
		}
		return s.join(", ");
	}
	
	solve(possibilities, count = 0) {
		if (count == 100 || this.isAllSingle(possibilities)) {
			// console.log("stopped after " + count, this.isAllSingle(possibilities));
			return;
		}
		let hasReduced = false;
		
		// filter on singles, sort on with most length, then reduce
		var p = possibilities.filter(v => this.isSingle(v));
		p.sort((a,b) => b.length - a.length);
		p.forEach(p => { if (this.reduceAt(possibilities, possibilities.indexOf(p))) { hasReduced = true }});
		
		if (hasReduced) {
		    // recurse
		    this.solve(possibilities, count + 1);
		} 
	}
	
	isSingle(possibility) {
	    return possibility.length === 1;
	}
	
	isAllSingle(possibilities = []) {
		for (let possibility of possibilities) {
			if (!this.isSingle(possibility)) {
				return false;
			}
		}
		return true;
	}
	
	reduceAt(possibilities, i) {
		let value = possibilities[i][0];
		if (value < 0) return false;
		
		let hasReduced = false;
		let x1 = i % this.gridBlockCount;
		let y1 = i / this.gridBlockCount | 0;
		//console.log(`reduce "${value}" [x=${x1},y=${y1}]`);
		// remove from col/row
		for (let c=0; c<this.gridBlockCount; c++) {
		    // reduce possibilities from value in rows
			{
				let j = x1 + c*this.gridBlockCount;
				if (j !== i) {
					//let x2 = j % this.gridBlockCount;
					//let y2 = j / this.gridBlockCount | 0;
					//console.log(`  remove row "${value}" at [x=${x2},y=${y2}]`);
				    if (this.remove(possibilities[j],value)) {
			            hasReduced = true;
				    }
				}
			}
			
			// reduce possibilities from value in  cols
			{
				let j = c + y1*this.gridBlockCount;
				if (j !== i) {
					//let x2 = j % this.gridBlockCount;
					//let y2 = j / this.gridBlockCount | 0;
				    // console.log(`  remove col "${value}" at [x=${x2},y=${y2}]`);
				    if (this.remove(possibilities[j],value)) {
					    hasReduced = true;
				    }
				}
			}
		}
		
		let thisBlock = [];
		
		// remove possibilities from block
		{
            const gbsx = this.gridBlockSize[0];
            const gbsy = this.gridBlockSize[1];
            for(let y2=0;y2<gbsy;++y2) {
                for(let x2=0;x2<gbsx;++x2) {
                    let x3=x2+ (x1/gbsx|0) * gbsx;
                    let y3=y2+(y1/gbsy|0)*gbsy;
                    let j=x3+y3*this.gridBlockCount;
                	if (i !== j) {
                	    if (this.remove(possibilities[j], value)) {
                	        hasReduced = true;
                	    }
                	}
					thisBlock.push(possibilities[j]);
                }
            }
        }
		
		// 1. check if current value is only available on 
		//if (
		
		return hasReduced;
	}
	
	// returns true if removed something
	remove(arr, value) {
		let idx = arr.indexOf(value);
		if (idx >= 0) {
			arr.splice(idx, 1);
			return true;
		}
		return false;
	}
}


////////////////////////////////////////////////////////////////
// Text utility code. Created by Reinder Nijhoff 2019
// https://turtletoy.net/turtle/1713ddbe99
////////////////////////////////////////////////////////////////

function Text() {
    class Text {
        print (t, str, scale) {
            t.radians();
            let pos = [t.x(), t.y()], h = t.h(), o = pos;
            str.split('').map(c => {
                const i = c.charCodeAt(0) - 32;
                if (i < 0 ) {
                    pos = o = this.rotAdd([0, 48*scale], o, h);
                } else if (i > 96 ) {
                    pos = this.rotAdd([16*scale, 0], o, h);
                } else {
                    const d = dat[i], lt = d[0]*scale, rt = d[1]*scale, paths = d[2];
                    paths.map( p => {
                        t.up();
                    	p.map( s=> {
                        	t.goto(this.rotAdd([s[0]*scale - lt, s[1]*scale], pos, h));
                        	t.down();
                        });
                    });
                    pos = this.rotAdd([rt - lt, 0], pos, h);
                }
            });
        }
        rotAdd (a, b, h) {
            return [Math.cos(h)*a[0] - Math.sin(h)*a[1] + b[0], 
                    Math.cos(h)*a[1] + Math.sin(h)*a[0] + b[1]];
        }
    }
    
const dat = ('br>eoj^jl<jqirjskrjq>brf^fe<n^ne>`ukZdz<qZjz<dgrg<cmqm>`thZhw<lZlw<qao_l^h^e_caccdeefg'+
'gmiojpkqmqporlshsercp>^vs^as<f^h`hbgdeeceacaab_d^f^h_k`n`q_s^<olmmlolqnspsrrspsnqlol>]wtgtfsereqfph'+
'nmlpjrhsdsbraq`o`makbjifjekckaj_h^f_eaecffhimporqssstrtq>eoj`i_j^k_kajcid>cqnZl\\j_hcghglhqjulxnz>c'+
'qfZh\\j_lcmhmllqjuhxfz>brjdjp<egom<ogem>]wjajs<ajsj>fnkojpiojnkokqis>]wajsj>fnjniojpkojn>_usZaz>`ti'+
'^f_dbcgcjdofrisksnrpoqjqgpbn_k^i^>`tfbhak^ks>`tdcdbe`f_h^l^n_o`pbpdofmicsqs>`te^p^jfmfogphqkqmppnrk'+
'shserdqco>`tm^clrl<m^ms>`to^e^dgefhekenfphqkqmppnrkshserdqco>`tpao_l^j^g_ebdgdlepgrjsksnrppqmqlping'+
'kfjfggeidl>`tq^gs<c^q^>`th^e_dadceegfkgnhpjqlqopqorlshserdqcocldjfhigmfoepcpao_l^h^>`tpeohmjjkikfjd'+
'hcecddaf_i^j^m_oapepjoomrjshserdp>fnjgihjikhjg<jniojpkojn>fnjgihjikhjg<kojpiojnkokqis>^vrabjrs>]wag'+
'sg<amsm>^vbarjbs>asdcdbe`f_h^l^n_o`pbpdofngjijl<jqirjskrjq>]xofndlcicgdfeehekfmhnknmmnk<icgefhfkgmh'+
'n<ocnknmpnrntluiugtdsbq`o_l^i^f_d`bbad`g`jambodqfrislsorqqrp<pcokompn>asj^bs<j^rs<elol>_tc^cs<c^l^o'+
'_p`qbqdpfoglh<chlhoipjqlqopqorlscs>`urcqao_m^i^g_eadccfckdnepgrismsorqprn>_tc^cs<c^j^m_oapcqfqkpnop'+
'mrjscs>`sd^ds<d^q^<dhlh<dsqs>`rd^ds<d^q^<dhlh>`urcqao_m^i^g_eadccfckdnepgrismsorqprnrk<mkrk>_uc^cs<'+
'q^qs<chqh>fnj^js>brn^nnmqlrjshsfreqdndl>_tc^cs<q^cl<hgqs>`qd^ds<dsps>^vb^bs<b^js<r^js<r^rs>_uc^cs<c'+
'^qs<q^qs>_uh^f_daccbfbkcndpfrhslsnrppqnrkrfqcpan_l^h^>_tc^cs<c^l^o_p`qbqepgohlici>_uh^f_daccbfbkcnd'+
'pfrhslsnrppqnrkrfqcpan_l^h^<koqu>_tc^cs<c^l^o_p`qbqdpfoglhch<jhqs>`tqao_l^h^e_caccdeefggmiojpkqmqpo'+
'rlshsercp>brj^js<c^q^>_uc^cmdpfrisksnrppqmq^>asb^js<r^js>^v`^es<j^es<j^os<t^os>`tc^qs<q^cs>asb^jhjs'+
'<r^jh>`tq^cs<c^q^<csqs>cqgZgz<hZhz<gZnZ<gznz>cqc^qv>cqlZlz<mZmz<fZmZ<fzmz>brj\\bj<j\\rj>asazsz>fnkc'+
'ieigjhkgjfig>atpeps<phnfleiegfehdkdmepgrislsnrpp>`sd^ds<dhffhekemfohpkpmopmrkshsfrdp>asphnfleiegfeh'+
'dkdmepgrislsnrpp>atp^ps<phnfleiegfehdkdmepgrislsnrpp>asdkpkpiognfleiegfehdkdmepgrislsnrpp>eqo^m^k_j'+
'bjs<gene>atpepuoxnylzizgy<phnfleiegfehdkdmepgrislsnrpp>ate^es<eihfjemeofpips>fni^j_k^j]i^<jejs>eoj^'+
'k_l^k]j^<kekvjyhzfz>are^es<oeeo<ikps>fnj^js>[y_e_s<_ibfdegeifjijs<jimfoeretfuius>ateees<eihfjemeofp'+
'ips>atiegfehdkdmepgrislsnrppqmqkphnfleie>`sdedz<dhffhekemfohpkpmopmrkshsfrdp>atpepz<phnfleiegfehdkd'+
'mepgrislsnrpp>cpgegs<gkhhjfleoe>bsphofleieffehfjhkmlompopporlsisfrep>eqj^jokrmsos<gene>ateeeofrhsks'+
'mrpo<peps>brdejs<pejs>_ubefs<jefs<jens<rens>bseeps<pees>brdejs<pejshwfydzcz>bspees<eepe<esps>cqlZj['+
'i\\h^h`ibjckekgii<j[i]i_jakbldlfkhgjkllnlpkrjsiuiwjy<ikkmkojqirhthvixjylz>fnjZjz>cqhZj[k\\l^l`kbjci'+
'eigki<j[k]k_jaibhdhfihmjilhnhpirjskukwjy<kkimiojqkrltlvkxjyhz>^vamakbhdgfghhlknlplrksi<akbidhfhhill'+
'nmpmrlsisg>brb^bscsc^d^dsese^f^fsgsg^h^hsisi^j^jsksk^l^lsmsm^n^nsoso^p^psqsq^r^rs').split('>').map(
    r=> { return [r.charCodeAt(0)-106,r.charCodeAt(1)-106, r.substr(2).split('<').map(a => {const ret 
    = []; for (let i=0; i<a.length; i+=2) {ret.push(a.substr(i, 2).split('').map(b => b.charCodeAt(0)
    -106));} return ret; })]; });

    return new Text();
}


// Seeded random - Mulberry32
function Random(seed) {
    class Random {
        constructor(seed) { 
            this.seed = seed;
        }
        next() { 
            var t = this.seed += 0x6D2B79F5;
            t = Math.imul(t ^ t >>> 15, t | 1);
            t ^= t + Math.imul(t ^ t >>> 7, t | 61);
            return ((t ^ t >>> 14) >>> 0) / 4294967296;
        }
        shuffle(arr) {
            for (let i = arr.length - 1; i > 0; i--) {
                const j = Math.floor(this.next() * (i + 1));
                [arr[i], arr[j]] = [arr[j], arr[i]];
            }
            return arr;
        }
    }
    return new Random(seed);
}