Ken Ken Fast Optimization Solver

Overview

KenKen is a mathematical logic puzzle created to help people grow their reasoning skills. They fall under the classification of NP-Hard, and solving them is computationally complex. The Penn State Behrend School of Engineering tasked us with creating an application to solve them. This furthers the field of Computer Science as a whole, and provides a useful tool for those using KenKen puzzles as an academic tool.

Objectives

Our team sought to build an application that can solve Hard 9×9 KenKen puzzles in under two minutes. This application comes with a simple and intuitive user interface for the user to upload and solve their own puzzles using a .json file. Application also comes along with multiple solving algorithms, allowing users to compare the difference in solving times for different solving algorithms. It is cross-compatible for use on any operating system.

Approach

• Met with industry sponsor (Dr. Wen-Li Wang) weekly to understand client’s needs
• Developed user requirements; engineered functional and nonfunctional system requirements
• Created diagrams for system design, behavior, and architecture using UML
• Incrementally developed solving algorithms using node.js
• Tested algorithm efficiency with increasingly difficult puzzles
• Built frontend for puzzle interface using Electron for cross-compatibility
• Connected frontend interface and puzzle solving backend
• Executed further testing to ensure frontend and backend worked together seamlessly

Outcomes

• Application is able to solve most 9×9 KenKen puzzles in under 10 seconds
• Only one puzzle tested failed to solve in under two minutes using most powerful algorithm
• 3 algorithms implemented for solving puzzles (brute force, iterative solver, and graph solver)
• Users can upload custom puzzle using .json file and custom format
• System can be deployed on any operating system (Linux, macOS, and Windows)