![\"\"](\"http:\/\/kb.shoelace.biz\/wp-content\/uploads\/2023\/10\/image.png\")
Fun isn’t fun until its ruined, so as is de rigueur, I started kicking around the idea of getting a computer to solve sudoku puzzles. Of course sudoku-solvers already exist on the internet, so I won’t be treading any new ground for humanity – but I’m interested in a subset of those solvers. Specifically, ones you don’t have to “teach” the rules to:<\/p>\n\n\n
![\"\"](\"http:\/\/kb.shoelace.biz\/wp-content\/uploads\/2023\/10\/image-1.png\")
<\/figure>\n<\/div>\n\n\nBaby Sudoku For Baby Minds<\/h2>\n\n\n\n
My first concern was whether a simple feed-forward neural network could even sort out the easiest problem to solve in sudoku – which is when you have numbers in a row or column and only 1 is missing:<\/p>\n\n\n
![\"\"](\"http:\/\/kb.shoelace.biz\/wp-content\/uploads\/2023\/10\/image-2.png\")
<\/figure>\n<\/div>\n\n\nEven if you’ve never played sudoku you can probably deduce what number goes in the box. I was not convinced this was particularly easy for a simple neural network to figure out. I mean, how would you set up a problem like this for any ML algorithm? I decided to do it like this:<\/p>\n\n\n\n
- \n
- Treat the numbers as categories. The numbers could be anything – and their actual relationships (2 being 1+1, 9 being 3 x 3) are irrelevant to the puzzle.<\/li>\n\n\n\n
- Make the position of the numbers irrelevant. You can imagine that you don’t need the missing number to be in any particular box to solve the above puzzle.<\/li>\n\n\n\n
- One-hot encode the categories. If you don’t what that means – you can read here<\/a> (or ignore this point).<\/li>\n<\/ol>\n\n\n\n
I wrote a small block of code to generate the above problem 20,000 times (with a random number from 1 to 9 missing each time).<\/p>\n\n\n\n
import pandas as pd\nimport numpy as np\n# %%\ncategories = ['1','2','3','4','5','6','7','8','9']\npredictors = categories[:-1]\ndef generateSingleLineSudoku(samples):\n\n df_list = []\n for i in np.arange(0,samples):\n df_list.append(\n np.random.choice(\n np.arange(1,10,1),size=9,replace=False\n )\n )\n\n return pd.DataFrame(\n df_list, \n columns=predictors+['target']\n )<\/code><\/pre>\n\n\n\nThen I one hot encoded the predictors (the 8 numbers shown) and the target (the 9th number – aka the thing we’re trying to predict), and trained a single-hidden-layer neural network on 10,000 of the predictors and target:<\/p>\n\n\n
\n![\"\"](\"http:\/\/kb.shoelace.biz\/wp-content\/uploads\/2023\/10\/image-3.png\")
<\/figure>\n<\/div>\n\n\nAll the “Nones” refer to batch sizes, which aren’t important here. The critical thing to see is that the model takes 72 values and outputs 9, Which sounds like 9 times too many given that I claimed it’s supposed to only predict one missing number given 8 other numbers. The devil-in-the-details is the one-hot encoding – so each of the 9 outputs from the model represents a probability that particular number is missing.<\/p>\n\n\n\n
Here are 4 different predictions (rows) with columns 1 through 9 where each cell represents the probability that the missing number is the column number.<\/p>\n\n\n
\n![\"\"](\"http:\/\/kb.shoelace.biz\/wp-content\/uploads\/2023\/10\/image-4.png\")
<\/figure>\n<\/div>\n\n\nThese match the actual missing numbers for these rows. Suffice to say this model is very good at predicting the missing number. Upon further reflection this isn’t too surprising. The model only has to “see” 9 unique examples in its training data to have seen the entire universe of possible examples – and I trained it on 10,000 examples.<\/p>\n\n\n\n
Interestingly, if I remove a second number and ask the neural net to predict what is missing from this puzzle:<\/p>\n\n\n
\n![\"\"](\"http:\/\/kb.shoelace.biz\/wp-content\/uploads\/2023\/10\/image-5.png\")
<\/figure>\n<\/div>\n\n\nIt correctly predicts that both 7 AND 8 are missing! So it is has appropriately generalized to a slightly more complex problem.<\/p>\n\n\n\n
Toddler Sudoku for Toddler Minds<\/h2>\n\n\n\n
![\"\"](\"http:\/\/kb.shoelace.biz\/wp-content\/uploads\/2023\/11\/Screenshot-2023-11-04-120441.png\")
<\/figure>\n<\/div>\n\n\n![\"\"](\"http:\/\/kb.shoelace.biz\/wp-content\/uploads\/2023\/11\/Screenshot-2023-11-04-121743.png\")
<\/figure>\n<\/div>\n\n\n![\"\"](\"http:\/\/kb.shoelace.biz\/wp-content\/uploads\/2023\/11\/Screenshot-2023-11-04-160113.png\")
<\/figure>\n<\/div>\n\n\n