Solver for the popular game Ruzzle

ruzzle.py

#!/usr/bin/env python3

'''Ruzzle Solver

   __author__ = 'github.com/Bekt'
   __date__ = 3/22/2014
'''

import sys
from collections import defaultdict


def get_words(f):
    with open(f, 'r') as f:
        return {w.lower() for w in f.read().splitlines()}


def get_board(size):
    print("Enter Ruzzle board of size %d" % size)
    board = []
    for x in range(size):
        inp = input().replace(' ', '')
        if len(inp) != size:
            print("Board size must be %d" % size)
            sys.exit(1)
        board.append(tuple(inp.lower()))
    return board


def solve(board, words, sol, visited, word, y, x):
    # Ignore words >= 10 characters, otherwise it's too slow (lol)
    if x < 0 or y < 0 or x >= len(board) or y >= len(board) or visited[y][x] or len(word) >= 10:
        return
    word += board[y][x]
    if len(word) > 1 and word not in sol and word in words:
        sol.add(word)
    visited[y][x] = True
    steps = [(y-1, x-1), (y-1, x), (y-1, x+1),(y, x-1),
            (y, x+1), (y+1, x-1), (y+1, x), (y+1, x+1)]
    for step in steps:
        solve(board, words, sol, visited, word, step[0], step[1])
    visited[y][x] = False


def get_solutions(board, words):
    size = len(board)
    solutions = set()
    for y in range(size):
        for x in range(size):
            visited = [[False for x in range(size)] for y in range(size)]
            sol = set()
            solve(board, words, sol, visited, '', y, x)
            solutions |= sol
    return solutions


def pr(solutions):
    print("Found words: %d" % len(solutions))
    group = defaultdict(list)
    for word in solutions:
        group[len(word)].append(word)
    keys = sorted(group.keys())
    for k in keys:
        print("Length %d" % k)
        print(sorted(group[k]))
        print()


def main():
    f = '/usr/share/dict/words'
    board_size = 4
    words = get_words(f)
    board = get_board(board_size)
    sol = get_solutions(board, words)
    pr(sol)


if __name__ == '__main__':
    main()