ruzzle.py

import string
import numpy as np
import networkx
import pickle
import pandas as pd

#First, we need to determine the set of legal moves in the game.
# The grid is 4x4, and we can move in any direction so long as we don't 
# retrace our steps.
# This means we take a simple walk on a graph

# Hard code the nodes and edges for the graph
# Starting on the top right and moving rowise
neighbors = {
    0: [1,4,5],
    1: [0,2,4,5,6],
    2: [1,3,5,6,7],
    3: [2, 6,7],
    4: [0,1,5, 8, 9],
    5: [0,1,2,4,6,8,9,10],
    6: [1,2,3,5,7,9,10,11],
    7: [2,3,6,10,11],
    8: [4,5,9,12,13],
    9: [3,4,5,8,10,12,13,14],
    10: [5,6,7,9, 11, 13,14,15],
    11: [6,7,10,14,15],
    12: [8,9,13],
    13: [8,9,10,12,14],
    14: [9,10,11,13,15],
    15: [10,11,14]
}

g = networkx.Graph(neighbors)
simple_walks = []
#We can compute the walks once and then load them later
for i in range(16):
    for j in range(16):
        if i!=j:
            walk = networkx.all_simple_paths(g, source = i, target = j)
            for w in walk:
                simple_walks.append(w)
                

#Download a set of english words
url = 'https://raw.githubusercontent.com/dwyl/english-words/master/words_alpha.txt'
words = pd.read_csv(url, names = ['word']).word.tolist()


#Input the tiles on the board here
tiles = 'trcloeralndntosm'

def cheat(tiles, simple_walks, words):
    
    t = np.array(list(tiles))
    plays = []
    for walks in simple_walks:
        plays.append(''.join(t[walk]))
        
    set_plays = set(plays)
    set_words = set(words)
    
    return set_plays.intersection(set_words)