# Sudoku Generation

2019-03-23, post № 213

Over two years ago, I wrote a basic 𝟥 ⨉ 𝟥-sudoku solver which uses both fundamental rule-based elimination and guessing to arrive at the solution. Revisiting the topic of computer-aided sudoku manipulation, I wrote a generalized sudoku generator (sudoku-generation.hs).

    | 4
3 |
---------
2 | 1
4 |

./sudoku 5 2

However, to write a generator I first wrote a sudoku solver, both generalized as well as broader — instead of only finding one solution, it (eventually) discovers every valid solution to a given sudoku. Within this design decision lies the generator’s essence — a fully solved, yet pseudo-randomly picked, sudoku which can later be clue-dropped can be found in the set of all solutions to the empty sudoku (bearing in mind performance to some extend, not the entire set is generated and pseudo-randomly sampled, but rather the solving process itself is pseudo-randomly altered).

4 6   |       |
7 8 | 1   9 |     4
1   |       |   8
---------------------
6 4 7 |     5 |
1 | 8     | 5
8   |   6 4 | 7
---------------------
2   |   8 1 | 3
| 3     |     1
|       |   9

./sudoku 17 3

Having acquired a fully solved sudoku, the algorithm proceeds to remove clues whilst maintaining the puzzle’s unique solvability. How many clues are attempted to be removed is determined by the given minimum number of clues. One has to note that the above described algorithm cannot always hit as low a clue number as is possible due to the pseudo-randomly chosen path in which clues are dropped. However, clue-dropping does behave monotonically with regards to solvability, in the sense that a sudoku never loses solutions by removing clues.

          3 | 12        7 |  2 10       |    11  6
9 13 | 15 14  2    |     8  6 11 |     4
5 11  2 12 |          10 |    14  3    |    16  8
4 14 10    |             |             |    12
-----------------------------------------------------
2 12    |        8  4 |  3     7    |          11
8          |     2    12 |     1       |    14     3
7  5 |  6 15       | 10 12     9 |  8    13  2
14  9  3    |    10  7    |  8        2 |
-----------------------------------------------------
16        9 |       13 11 |           8 |  1    14 12
10  6  4    |  5     1 14 |             |    15  7  8
8  1    |     3       | 14  9 13  5 |    10     6
12    13 14 | 10  7     8 |        4    | 16  2  5  9
-----------------------------------------------------
4 |  3 13     1 |  7    16 12 |
5 15    |           9 |        2 10 |  6    16
13     6    |  7        2 |     5  1    | 11       10
7     2 |    16 10  6 |  9 11  8    | 12 13  1

./sudoku 125 4

# Pi Day MMXIX

2019-03-14, post № 212

C, programming, #cyclic quine, #iteration quine

w=0;b(){w>27&&puts("",w=0);}
p(c){b();putchar(c),b(++w);}
main(){int/**/N=0,D[][85]={{
0,1048320,4194272,8372472,1,
16646172,33030158,33030150,1
,33030144,16252928,16252928,
3932160,1,1966080,983040,1,1
,229376,57344,14336,7168,1,1
,134219520,1,1,1,1,67109312,
133169264,1,67108860,1,1,1,1
,33554431,-1},{3670016,1,1,1
,3932160,1835008,917504,1,1,
917504,458752,491520,229376,
114688,122880,57344,28672,1,
28672,14336,15360,7168,7680,
3840,1792,1920,960,448,-1},{
0,134217712,134217720,1,1,1,
62914620,31457294,31457286,1
,15728640,7340032,7864320,1,
3932160,1966080,1966080,1,1,
983040,1015808,491520,245760
,245760,122880,61440,61440,1
,30720,15360,-1},{0,0,0,0,0,
0,0,0,0,0,2097088,2097088,0,
0,0,0,0,0,0,0,0,0,-1},{0,0,0
,0,0,1048064,8259552,1,1,1,1
,16515576,15729144,504,504,1
,985024,1048320,1008,504,252
,25166332,29360632,7342064,1
,2097024,0,0,-1},},*d,C[]={1
,119,61,48,59,98,40,41,123,1
,119,62,50,55,38,38,112,117,
116,115,40,34,34,44,119,61,1
,48,41,59,125,112,40,99,41,1
,123,98,40,41,59,112,117,116
,99,104,97,114,40,99,41,44,1
,98,40,43,43,119,41,59,125,1
,109,97,105,110,40,41,123,1,
105,110,116,47,42,42,47,78,1
,61,48,44,68,91,93,91,56,53,
93,61,123,2,125,44,42,100,44
,67,91,93,61,123,3,48,125,44
,42,99,61,67,44,106,59,67,91
,56,48,93,61,40,67,91,56,48,
93,45,52,55,41,37,55,43,52,1
,56,59,105,102,40,78,60,54,1
,41,102,111,114,40,100,61,68
,91,78,63,78,45,49,58,48,93,
59,42,100,43,49,59,42,100,43
,43,45,49,38,38,112,117,116,
115,40,34,34,41,41,105,102,1
,40,42,100,45,49,41,102,111,
114,40,106,61,42,100,59,106,
59,106,47,61,50,41,112,117,1
,116,99,104,97,114,40,51,50,
43,106,37,50,42,49,53,41,59,
59,59,102,111,114,40,59,42,1
,99,59,99,43,43,41,123,105,1
,102,40,42,99,61,61,50,41,1,
102,111,114,40,106,61,48,59,
106,60,53,59,106,43,43,41,1,
123,112,40,49,50,51,41,59,59
,59,102,111,114,40,100,61,68
,91,106,93,59,42,100,43,1,49
,59,112,40,52,52,41,41,1,119
,43,61,112,114,105,110,1,116
,102,40,34,37,100,34,44,1,42
,100,43,43,41,59,112,40,1,52
,53,41,59,112,40,52,57,41,59
,112,40,49,50,53,41,59,1,112
,40,52,52,41,59,125,101,108,
115,101,32,105,102,40,1,42,1
,99,61,61,51,41,102,111,1,1,
114,40,100,61,67,59,42,100,1
,59,112,40,52,52,41,41,119,1
,43,61,112,114,105,110,116,1
,102,40,34,37,100,34,44,42,1
,100,43,43,41,59,1,101,108,1
,115,101,32,105,102,40,42,99
,62,49,41,112,40,42,99,41,59
,125,102,111,114,40,106,61,1
,53,59,45,1,45,106,59,112,40
,53,57,41,1,41,59,1,1,1,125,
0},*c=C,j;C[80]=(C[80]-47)%7
+48;if(N<6)for(d=D[N?N-1:0];
*d+1;*d++-1&&puts(""))if(*d-
1)for(j=*d;j;j/=2)putchar(32
+j%2*15);;;for(;*c;c++){if(*
c==2)for(j=0;j<5;j++){p(123)
;;;for(d=D[j];*d+1;p(44))w+=
printf("%d",*d++);p(45);p(49
);p(125);p(44);}else if(*c==
3)for(d=C;*d;p(44))w+=printf
("%d",*d++);else if(*c>1)p(*
c);}for(j=5;--j;p(59));};;;;

Try it online. Happy pi day.

# Lichen, Extraterrestrials, Diodes #1

2019-02-23, post № 211

art, #LED, #photography

# Kickboy #0

2019-01-26, post № 210

art, #stop motion

Kickboy.

# Foam Cube Puzzle

2018-12-29, post № 209

programming, Python, #brute-force, #solver

After having solved the puzzle shown below a few times by combining six foam pieces to construct a hollow cube, I wondered if it had a unique solution. A simple brute-force search reveals it does.
Source code: foam-cube-puzzle.py

All six foam pieces.

As a first step, I digitalized all pieces seen above. Having an internal representation, I wrote a script which tries all possible rotations and reflections (as three-dimensional rotations can imply two-dimensional reflection) to try and construct a three-dimensional cube from the given pieces. Using short-circuit evaluation to not bother with already impossible solutions, the search space is narrow enough to not require any considerable computing time. The resulting unique solution modulo rotation is shown above; the top face is placed on the bottom right.

# Winter MMXVIII

2018-12-24, post № 208

art, C, programming, #fir, #quine, #tree

                                         I
,O;
main(
){char*
Q,_[]={73
,44,79,59,2
,109,97,105,2
,110,40,41,123,
99,104,97,114,42,
81,44,95,91,93,61,2
,123,1,48,125,44,42,2
,74,59,102,111,114,40,2
,81,61,95,44,73,61,79,61,
48,59,42,81,59,43,43,81,41,
123,105,102,40,42,81,60,50,41
,102,111,114,40,74,61,95,59,42,
74,59,74,43,43,41,73,60,49,38,38,
112,114,105,110,116,102,40,34,37,42
,99,34,44,52,50,45,79,47,50,45,49,44,
51,50,41,44,73,43,61,112,114,105,110,2,
116,102,40,34,37,100,34,44,42,74,41,44,73
,62,79,63,73,61,48,44,79,43,61,50,44,112,2,
117,116,115,40,34,34,41,58,48,44,73,43,43,60,
49,63,112,114,105,110,116,102,40,34,37,42,99,34
,44,52,50,45,79,47,50,44,52,52,41,58,112,117,116,
99,104,97,114,40,52,52,41,44,73,62,79,63,73,61,48,2
,44,79,43,61,50,44,112,117,116,115,40,34,34,41,58,48,
59,105,102,40,42,81,62,50,41,73,43,43,60,49,63,112,114,
105,110,116,102,40,34,37,42,99,34,44,52,50,45,79,47,50,44
,42,81,41,58,112,117,116,99,104,97,114,40,42,81,41,44,73,62
,79,63,73,61,48,44,79,43,61,50,44,112,117,116,115,40,34,34,41
,58,48,59,125,102,111,114,40,73,61,48,59,73,43,43,60,49,55,59,2
,112,117,116,99,104,97,114,40,52,55,41,41,59,102,111,114,40,73,61
,112,117,116,115,40,34,34,41,59,73,43,43,60,53,59,112,117,116,115,2
,40,34,34,41,41,123,112,114,105,110,116,102,40,34,37,42,99,34,44,51,2
,50,44,52,55,41,59,102,111,114,40,74,61,48,59,74,43,43,60,50,48,59,41,2
,2,112,117,2,116,99,2,2,104,2,97,2,114,2,40,52,2,55,41,2,59,125,2,2,125,2
,2,0},*J;for(Q=_,I=O=0;*Q;++Q){if(*Q<2)for(J=_;*J;J++)I<1&&printf("%*c",42-
O/2-1,32),I+=printf("%d",*J),I>O?I=0,O+=2,puts(""):0,I++<1?printf("%*c",42-O/
2,44):putchar(44),I>O?I=0,O+=2,puts(""):0;if(*Q>2)I++<1?printf("%*c",42-O/2,*Q)
:putchar(*Q),I>O?I=0,O+=2,puts(""):0;}for(I=0;I++<17;putchar(47));for(I=puts("");
I++<5;puts("")){printf("%*c",32,47);for(J=0;J++<20;)putchar(47);}}/////////////////
/////////////////////
/////////////////////
/////////////////////
/////////////////////

Try it online.

# Symbolic Closed-Form Fibonacci

2018-12-01, post № 207

## Theoretical Framework

Let $V:=\{(a_j)_{j\in\mathbb{N}}\subset\mathbb{C}|a_n=a_{n-1}+a_{n-2}\forall n>1\}$ be the two-dimensional complex vector space of sequences adhering to the Fibonacci recurrence relation with basis $B:=((0,1,\dots),(1,0,\dots))$.
Let furthermore $f:V\to V,(a_j)_{j\in\mathbb{N}}\mapsto(a_{j+1})_{j\in\mathbb{N}}$ be the sequence shift endomorphism represented by the transformation matrix

By iteratively applying the sequence shift a closed-form solution for the standard Fibonacci sequence follows.

Diagonalizing $A$ leads to eigenvalues $\varphi=\frac{1+\sqrt{5}}{2}$, $\psi=\frac{1-\sqrt{5}}{2}$ and a diagonalization

Using said diagonalization, one deduces

Therefore,

Thus, a closed-form expression not involving any higher-dimensional matrices is found.

To avoid precision errors, I implemented a basic symbolic expression simplifier (fib.hs) — using $\sqrt[\star]{n}:=\text{sgn}(n)\cdot\sqrt{|n|}\,\forall n\in\mathbb{Z}$ as a negative-capable root, a symbolic expression is modeled as follows.

data Expr = Sqrt Int
| Neg Expr
| Expr :+ Expr
| Expr :* Expr
| Expr :/ Expr
| Expr :- Expr
| Expr :^ Int
deriving Eq

Said model is capable of representing the above derived formula.

phi   = (Sqrt 1 :+ Sqrt 5) :/ Sqrt 4
psi   = (Sqrt 1 :- Sqrt 5) :/ Sqrt 4
fib n = (Sqrt 1 :/ Sqrt 5) :* (phi :^ n :- psi :^ n)

Using this implementation to calculate the sequence should be possible (assuming the simplifier does not get stuck at any occurring expression), yet takes its sweet time — $F_6$ takes half a minute on my 4 GHz machine.

*Main> simplify $fib 6 \sqrt{64} ## More Efficient Fibonacci Calculations Quicker sequence calculation methods include a brute-force A^n approach, e. g. import Data.List (transpose) a *@* b = [[sum . map (uncurry (*))$ zip ar bc
| bc <- transpose b] | ar <- a]

a *^* 0 = [[1, 0], [0, 1]]
a *^* n = a *@* (a *^* (n-1))

fib = (!! 0) . (!! 0) . ([[1, 1], [1, 0]] *^*)

as well as using lazy evaluation to construct the whole infinite sequence.

# Snippet #2

2018-09-22, post № 203

programming, #bash

cat /dev/urandom > /dev/null