This Puzzle Does Not Exist
First of all, credit where is credit is due. As with many deep learning projects, nothing is possible without the work of real, talented humans beforehand.
Therefore I would like to thank Tuesday Quest with their Hungry Cat Nonogram (Android, iOS). Especially shoutout to Sev_4Game for her incredibly beautiful artworks. As we will see, the rules can be learned, but what makes a beautiful pixel is not possible.
Please check out their work and suscribe to their games!
This model is loosely based of the dcgan_14 jupyter notebook on GANs.
import pathlib
import numpy as np
from lxml import objectify
from PIL import Image
import pickle
dataset = []
filenames = []
for filename in filenames:
root = objectify.parse(open(filename, "r")).getroot()
width, height = len(root.column), len(root.line)
if width != 10 or height != 15:
continue
data = np.zeros((150), dtype="float")
data_color = np.zeros((150,3), dtype="uint8")
for color_index, color in enumerate(root.colors):
r, g, b = [int(float(color.get(x))*255) for x in ["r","g","b"]]
indexes = [int(x) for x in color.slots.text.split(",")[:-1]]
for index in indexes:
data[index] = color_index / 4.0
data_color[index] = (r,g,b)
data = data.reshape((15,10))
dataset.append(data)
data_color = data_color.reshape((15,10,3))
Image.fromarray(data_color).save(filename.with_suffix(".png"))
with open("dataset_full.pkl", "wb") as datafile:
pickle.dump(dataset, datafile, protocol=2)
This will give us a pickle file that contains all the information we want. We export it a data of shape (numpuzzle, 15, 10). Let’s see how big is this package.
pathlib.Path("dataset_full.pkl").stat().st_size
5 Megabytes, not bad. Should be easy enough to work with.
Loading the data
Let’s dive in the actual deep learning program. This program is heavily adapted from dcgan presented in the tensorflow tutorial.
We start by loading everything in a tensor:
import pickle
with open("dataset_full.pkl", "rb") as datafile:
train_images = np.array(pickle.load(datafile))
train_images = train_images.reshape(train_images.shape[0], 15, 10, 1).astype('float32')
#train_images = (train_images/0.75 - 0.5)*2 #gives -1, -0.33, 0.33, 1
train_images = train_images * 2 - 0.75 #gives -0.75, -0.25, 0.25, 0.75
train_images.shape
We have 3571 example pictures. We tried to remap to -1..1 with a 0.66 interval but in the end the -0.75..0.75 with a 0.5 interval gave better result. We think that maybe allowing values to get over 0.75 a little bit helped, whereas with 1 the behaviour would change.
We will also ‘augment’ a little bit the data. We can see that the puzzle are identical to a Y-axis mirror. Let’s just do that. In retrospective, it should be also allowed to mirror along the X-axis as we will not produce real ‘pictures’. However we can see that the network kind of learn the structure of top/bottom.
augment_data = True
if augment_data:
train_images = np.concatenate((train_images, np.flip(train_images, 2)))
print(train_images.shape)
We now have 7142 images which is enough for our purposes. We will work with batches of size 64.
BUFFER_SIZE = train_images.shape[0]
BATCH_SIZE = 64
We will now shuffle the dataset in order not to have the same pictures grouped together.
train_dataset = tf.data.Dataset.from_tensor_slices(train_images).shuffle(BUFFER_SIZE).batch(BATCH_SIZE)
Creating the model
Let’s dig into the interesting stuff! We want to create a model of what our puzzle is. Well, in fact, two models: one that is responsible to say from this number(s), I can create this puzzle, and one that is responsible to say this puzzle looks like a valid puzzle to me. The first one is the generator, the second one is the discriminator
The base of the generator model is pretty simple: since a puzzle is a 15x10x4 matrix, we will first create a seed of 5x5, then expand it to the actual size of 15x10. For the 4 bits representing the value, we use the following values:
-0.75, -0.25, 0.25, 0.75
Each value is approximately one color. This allows the network to have fuzzy pictures while still being able to consolidate data afterwards.
def make_generator_model():
model = tf.keras.Sequential()
model.add(tf.keras.layers.Dense(5*5*256, use_bias=False, input_shape=(100,)))
model.add(tf.keras.layers.BatchNormalization())
model.add(tf.keras.layers.LeakyReLU())
model.add(tf.keras.layers.Reshape((5, 5, 256)))
assert model.output_shape == (None, 5, 5, 256) # Note: None is the batch size
model.add(tf.keras.layers.Conv2DTranspose(1, (5, 5), strides=(3, 2), padding='same', use_bias=False))
assert model.output_shape == (None, 15, 10, 1)
model.add(tf.keras.layers.BatchNormalization())
model.add(tf.keras.layers.LeakyReLU())
model.add(tf.keras.layers.Conv2DTranspose(1, (5, 5), strides=(1, 1), padding='same', use_bias=False))
assert model.output_shape == (None, 15, 10, 1)
model.add(tf.keras.layers.BatchNormalization())
model.add(tf.keras.layers.LeakyReLU())
model.add(tf.keras.layers.Conv2DTranspose(1, (5, 5), strides=(1, 1), padding='same', use_bias=False, activation='tanh'))
assert model.output_shape == (None, 15, 10, 1)
return model
Each steps adds normalization (as we want our values to fall within out range) and a LeakyReLU. We tried with a basic ReLU, but the results were less good.
Alternative model
We can note that we went directly from 5x5 to 15x10, it may seem better to start from 3x2 then increasing to 15x10. It is possible for example with such a model:
def make_generator_model_alternative():
model = tf.keras.Sequential()
model.add(tf.keras.layers.Dense(5*5*256, use_bias=False, input_shape=(100,)))
model.add(tf.keras.layers.BatchNormalization())
model.add(tf.keras.layers.LeakyReLU())
model.add(tf.keras.layers.Reshape((5, 5, 256)))
assert model.output_shape == (None, 5, 5, 256) # Note: None is the batch size
model.add(tf.keras.layers.Conv2DTranspose(128, (3, 2), strides=(1, 1), padding='valid', use_bias=False))
assert model.output_shape == (None, 7, 6, 128)
model.add(tf.keras.layers.BatchNormalization())
model.add(tf.keras.layers.LeakyReLU())
model.add(tf.keras.layers.Conv2DTranspose(64, (4, 3), strides=(1, 1), padding='valid', use_bias=False))
assert model.output_shape == (None, 10, 8, 64)
model.add(tf.keras.layers.BatchNormalization())
model.add(tf.keras.layers.LeakyReLU())
model.add(tf.keras.layers.Conv2DTranspose(1, (6, 3), strides=(1, 1), padding='valid', use_bias=False))
print(model.output_shape)
assert model.output_shape == (None, 15, 10, 1)
model.add(tf.keras.layers.BatchNormalization())
model.add(tf.keras.layers.LeakyReLU())
model.add(tf.keras.layers.Conv2DTranspose(1, (5, 5), strides=(1, 1), padding='same', use_bias=False, activation='tanh'))
assert model.output_shape == (None, 15, 10, 1)
return model
However this model gave poorer results. The underlying 3x2 structure was creating artifacts at the later stages that would stay visible in the final pictures.
The discriminator is very similar but does the inverse operation: given a full picture, it reduces it while trying to keep the information ‘this is a valid puzzle’.
Important note
Keep in mind that at no point we gave the information of the rules to the neural network. It remains to be seen if the way, us, humans, are creating puzzles can be somewhat captured by a neural network. Obviously, the variety of puzzles created prevent to extract any kind of recognizable form (like an animal, an object, etc.) but maybe the rules are strict enough that we can approximate them with this network.
This point will be prevalent in the disctrimator model.
The discriminator model
def make_discriminator_model():
model = tf.keras.Sequential()
model.add(tf.keras.layers.Conv2D(64, (5, 5), strides=(3, 2), padding='same'))
model.add(tf.keras.layers.LeakyReLU())
model.add(tf.keras.layers.Dropout(0.3))
model.add(tf.keras.layers.Conv2D(128, (5, 5), strides=(1, 1), padding='same'))
model.add(tf.keras.layers.LeakyReLU())
model.add(tf.keras.layers.Dropout(0.3))
model.add(tf.keras.layers.Flatten())
model.add(tf.keras.layers.Dense(1))
return model
The discrimator model is almost a mirror of the generator model. It goes from the 10x15 picture and then reduces it further and further, up until to find a number that says if the puzzle is a real one.
Here, one option is to include a Nonogram solver into the discrimator. However we didn’t opt for this for two reasons. The first one is solving a puzzle is slow, all the more if the puzzle is invalid, as we have to explore all the options. Even if we created a faster version with heuristics, it would be a bit slow for our purposes. But more importantly, as we said, the goal of this program is to capture a sense of what is a good puzzle. After all, when humans are designing the puzzle, their don’t look at the rules all the time.
generator = make_generator_model()
discriminator = make_discriminator_model()
We can now generate the two models, we will need to apply them. Here we follow somewhat closely the dcgan1.4 path.
def generator_loss(generated_output):
return tf.losses.sigmoid_cross_entropy(tf.ones_like(generated_output), generated_output)
def discriminator_loss(real_output, generated_output):
real_loss = tf.losses.sigmoid_cross_entropy(multi_class_labels=tf.ones_like(real_output), logits=real_output)
generated_loss = tf.losses.sigmoid_cross_entropy(multi_class_labels=tf.zeros_like(generated_output), logits=generated_output)
total_loss = real_loss + generated_loss
return total_loss
We have two optimizers. Here an important parameters is the speed of the optimizer. Too high, and it will not converge, and too low, it will either have hard time to converge and/or converge too slowly.
generator_optimizer = tf.train.AdamOptimizer(1e-4)
discriminator_optimizer = tf.train.AdamOptimizer(1e-4)
After that it’s time to train!
EPOCHS = 5000
noise_dim = 100
def train_step(images):
# generating noise from a normal distribution
noise = tf.random_normal([BATCH_SIZE, noise_dim])
with tf.GradientTape() as gen_tape, tf.GradientTape() as disc_tape:
generated_images = generator(noise, training=True)
real_output = discriminator(images, training=True)
generated_output = discriminator(generated_images, training=True)
gen_loss = generator_loss(generated_output)
disc_loss = discriminator_loss(real_output, generated_output)
gradients_of_generator = gen_tape.gradient(gen_loss, generator.variables)
gradients_of_discriminator = disc_tape.gradient(disc_loss, discriminator.variables)
generator_optimizer.apply_gradients(zip(gradients_of_generator, generator.variables))
discriminator_optimizer.apply_gradients(zip(gradients_of_discriminator, discriminator.variables))
def train(dataset, epochs):
for epoch in range(epochs):
start = time.time()
for images in dataset:
train_step(images)
display.clear_output(wait=True)
generate_and_save_images(generator,
epoch + 1,
random_vector_for_generation)
# saving (checkpoint) the model every 10 epochs
if (epoch + 1) % 10 == 0:
checkpoint.save(file_prefix = checkpoint_prefix)
print ('Time taken for epoch {} is {} sec'.format(epoch + 1,
time.time()-start))
%%time
train(train_dataset, EPOCHS)
Once we have trained the model, we can generate various images. We made a function to help with that:
def generate_from_number(generator, rand_number, show=False):
tf.set_random_seed(rand_number)
np.random.seed(rand_number)
image = generator(tf.random_normal([1, noise_dim]), training=False)
image = (image * 2) + 2
image = tf.clip_by_value(image,0,3)
image = tf.cast(image, dtype=tf.uint8)
cmap = matplotlib.colors.ListedColormap ( np.random.rand (4,3))
if show:
plt.imshow(image[0, :, :, 0], cmap=cmap)
plt.show()
return image, cmap
Here since we already trained the model, we will load it from disk
network_version="v3"
checkpoint_dir = "./training_checkpoints_full_" + network_version
checkpoint = tf.train.Checkpoint(generator_optimizer=generator_optimizer,
discriminator_optimizer=discriminator_optimizer,
generator=generator,
discriminator=discriminator)
checkpoint.restore(tf.train.latest_checkpoint(checkpoint_dir))
<tensorflow.python.training.checkpointable.util.CheckpointLoadStatus at 0x1e806b2ba48>
It’s time to generate some puzzles!
np.random.seed(279593)
for i in range(10):
rand_number = np.random.randint(1000000)
print(f"Image number : {rand_number}")
_,_ = generate_from_number(generator, rand_number, True)
Image number : 809702
Image number : 41220
Image number : 761314
Image number : 442379
Image number : 508457
Image number : 924653
Image number : 26033
Image number : 298389
Image number : 758369
Image number : 540042
Conlusion
We can see that the neural network is able to capture much of the essence of what consitutes a “valid” puzzle. It’s quite interresting to see that the fact there is an “up” and a “down” in the puzzles is captured as well, as much of the puzzles have a sense of gravity with more details at the bottom. This may be fact that the neural network tries to imitate a sky or something.
As extensions, we could try to generate colors as well, as in the current implementation, they are totally random. This is left as an exercice to the reader.
For the fun, we generated thousands of puzzles using a large AWS instance. It cost only 1$ to generate roughly ~30000 puzzles. The rate of valid puzzles is between 30% and 50%, so it goes quite quickly.
You can play some of the generated puzzles below. In condensed form, each puzzle is just 50 bytes. Beware: they all have at least one solution, but some of them may have more than one. Feel free to give feedback!
Source code
If you’re curious about how to make a simple Nonogram with front-end technologies, here is the source code. It uses AlpineJS and some clever tricks in order to be quite short.
<script>
Array.matrix = function (numrows, numcols, initial) {
var arr = [];
for (var i = 0; i < numrows; ++i) {
var columns = [];
for (var j = 0; j < numcols; ++j) {
columns[j] = initial;
}
arr[i] = columns;
}
return arr;
}
const width = 10;
const height = 15;
const len = width * height;
const numcolors = 4;
const circled = "⓪①②③④⑤⑥⑦⑧⑨⑩⑪⑫⑬⑭⑮⑯⑰⑱⑲⑳";
const database = [
"5wonNx476rbGdClf///wwV8GqfAFPwCn8Cp/BbUAAAEAAZAAKlYBVVAVVQVWUFWVVVA=",
"n5LmlSeEpIQg0ukA//9vVWWX/BV/wVUAVVVVVUAF/gH/1V/wEAEAUAAFEABQAAYAJuA=",
"+DZoTHeRSK6uxOMlQABVAAWkAFpAAJUABQAAAAAFVQBVVQVZJACBAAAA8AAMBVBVQQA=",
"UHNEG92gWRGfmBcOBVXwQAoAVfAAPwAT8AA/VVX0BV8AVbAaXwHVUAqVRPrVa61Vn+A=",
"g5EHK67UTuO3MI1ZVVUJVVBVVQVVAFdUD1VAVQQFlACVQApQAFUAClAAJAAIQABQAAA=",
"v+cwZRmAuJ43wVNbVVVZVVW1VZpVVdVVWQFVAEW1FVVAFVUFlVRVVVpVpVWpVVqqv+A=",
"zJgZuCQSzfjIcXiaVaoKVVCVVQpVQFasB6vAla4FqVCql0qlda9VXvFVXwVLwFXpQFA=",
"Hnu5juOKIjvvKjrhAAAFAABUAAVABUAFUABVAEAAAVAAFwANeVXXVXFlipqWZanq1pA=",
"JiaHnoYemculRnZpAVUAFVBRVFoBVZACXAApAABQAAQAFAAKlVWppV6qSqrn6q//2/A=",
"CXVFv+01a4ElUeHtVVUKVVRVVVVVQEFYB5VAVUU1pnFZfxWr2VW/pa/62//n////7/A=",
"B6XyFhw7QmsZ21gpAAAAAAAMAODAL0AD9gA/AACAAGIAARAJUFXVqbVaT1WX5Vr/7+A=",
"r0fdzqyzADWYEUsq///11V8H/VBVGQECoAAqAABwAFIABSABVQBV8AFb0aV1a1dVRaA=",
"ChoZ7uIxB/QjfSISUAAaAAVQAAVAAFQADQAAAAAAAAAAAAAABQBAEGAEmlBZVQX/1VA=",
"0T3Bes7+2ehybROXQVUFFVBRVQUVQFSoBaqAploKqVCrlpq5ea+XWtFV/1Wf5Vn/gVA=",
"m9pUhgXb9+/xu7SG///x1V8CqlBVVSqpUFVVWZUFVQCVVUlQFFQABXAABQAFUAABQAA=",
"2alLIT4Or85t/hdfAABUAAVYAPWAP1YD/wA/BEX1VV9VVWVVVQFVUAlVAFVQFVUBX+A=",
"lDg5Ua3Xq84gODk3AABQQAUAAPAAPzwD9AA/VABlVQVVVAVVVQFVUAVV4FVtVVZVVqA="
];
function count(grid, index, color, direction="row") {
let max = direction == "row" ? width: height;
let left = max;
let right = 0;
let count = 0;
for (let i = 0; i < max; ++i) {
let value = direction == "row" ? grid[i][index]: grid[index][i];
if (value == color) {
count += 1;
right = Math.max(right, i);
left = Math.min(left, i);
}
}
if ((right - left) >= 0) {
if (((right - left + 1) == count) && count > 1) {
return circled[count];
} else {
return count;
}
}
return "";
}
function puzzle() {
return {
init() {
this.load();
},
load() {
this.grid = Array.matrix(10, 15, 4);
let encoded = database[Math.floor(Math.random() * database.length)];;
binary = atob(encoded);
for (let i = 0; i < 4; ++i) {
let r = binary.charCodeAt(i * 3 + 0);
let g = binary.charCodeAt(i * 3 + 1);
let b = binary.charCodeAt(i * 3 + 2);
this.colors[i] = 'rgb(' + r + ',' + g + ',' + b + ')'
}
let solution = Array.matrix(10, 15, 4);
let columns_hints = Array.matrix(4, 10, "_");
let rows_hint = Array.matrix(15, 4, "_");
for (let i = 0; i < len; ++i) {
let index = Math.floor(i / numcolors + 12);
const byte = binary.charCodeAt(index);
solution[i % width][Math.floor(i / width)] = (byte >> 6) & 0x3;
++i;
solution[i % width][Math.floor(i / width)] = (byte >> 4) & 0x3;
++i;
solution[i % width][Math.floor(i / width)] = (byte >> 2) & 0x3;
++i;
solution[i % width][Math.floor(i / width)] = (byte >> 0) & 0x3;
}
for (let j = 0; j < height; ++j) {
for (let c = 0; c < numcolors; ++c) {
rows_hint[j][c] = count(solution, j, c, "row");
}
}
for (let i = 0; i < width; ++i) {
for (let c = 0; c < numcolors; ++c) {
columns_hints[c][i] = count(solution, i, c, "column");
}
}
this.rows_hint = rows_hint;
this.columns_hint = columns_hints;
this.solution = solution;
},
currentColor: numcolors,
isPainting: false,
colors: ["red", "blue", "yellow", "green", "white"],
grid: Array.matrix(10, 15, 4),
solution: Array.matrix(10, 15, 4),
columns: [...Array(10).keys()],
columns_hint: Array.matrix(4, 10, "_"),
rows_hint: Array.matrix(15, 4, "_"),
getColor(i, j) {
return this.colors[this.grid[i][j]];
},
changeColor(i, j) {
if (this.isPainting &&
(this.grid[i][j] == numcolors ||
this.currentColor == numcolors))
this.grid[i][j] = this.currentColor;
},
solve() {
for (let i = 0; i < width; ++i) {
for (let j = 0; j < height; ++j) {
this.grid[i][j] = this.solution[i][j];
}
}
},
solved() {
for (let i = 0; i < width; ++i) {
for (let j = 0; j < height; ++j) {
if (this.grid[i][j] != this.solution[i][j]) {
return false;
}
}
}
return true;
}
}
}
</script>
<div style="margin:auto; max-width: 28em; border:2px gray; border-radius: 5px;" x-data="puzzle()">
<div style="margin:auto; max-width: 80%; display: flex; justify-content: space-between;">
<template x-for="color, index in colors" :key="index">
<div @click="currentColor = index" class="palette"
x-bind:style="'background-color:'+color+'; border:'+(currentColor == index ? 'solid 6px':'solid 1px')"
x-bind:id="'color'+index">
</div>
</template>
</div>
<div @mouseleave="isPainting = false">
<table class="hcptable">
<template x-for="color, cindex in colors.slice(0,4)">
<tr>
<td class="topleft"><button x-show="cindex == 0" @click="solve()">Solve</button><button x-show="cindex == 1" @click="load()">Random puzzle</button></td>
<td class="topleft"></td>
<td class="topleft"></td>
<td class="topleft"></td>
<template x-for="column_hint, colindex in columns_hint[cindex]" :key="colindex">
<td x-bind:class="cindex != 0 ? 'top': 'toptop'">
<span x-show="!solved() && count(grid, colindex, cindex, 'column') != column_hint" x-text="column_hint"
x-bind:style="'color:'+colors[cindex]">
</td>
</template>
</tr>
</template>
<template x-for="row, rindex in rows_hint">
<tr>
<template x-for="row_hint, index in row">
<td>
<span x-show="!solved() && count(grid, rindex, index, 'row') != row_hint" x-text="row_hint"
x-bind:style="'color:'+colors[index]" />
</td>
</template>
<template x-for="column in columns">
<td x-bind:class="solved() ? 'solved':''" x-bind:style="'background-color:'+getColor(column, rindex)" x-bind:id="column+'-'+rindex"
@mouseup="isPainting = false" @mousemove="changeColor(column, rindex)"
@mousedown="isPainting = true; changeColor(column, rindex)">
</td>
</template>
</tr>
</template>
</table>
</div>
</div>
