Skip to content

huwlloyd-mmu/jpop

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

4 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

J-POP

Japanese Puzzles as Optimization Problems

This code implements a number of nature-inspired algorithms to solve Japanese Pencil Puzzles. Puzzles are represented by a simulator which iteratively constructs a solution for a puzzle instance. The simulator repeatedly presents set of choices to a puzzle-agnostic solver until the solution is complete, and calculates a cost value for the solution.

Simulators:

Sudoku, Futoshiki, Nurikabe, Slitherlink, Hashiwokakero, Zen Puzzle Garden

Solvers:

ACO, GA, Simulated Annealing, Random search, Backtracking search

Build

Linux (g++)

make puzzlesolver

Windows (Visual Studio)

Project files in msvc folder

Data

The instances used in the published experiments can be found in the puzzledata folder. Instances for the puzzles are in the subfolders. The top level folder contains two spreadsheets - test_instances.csv and train_instances.csv which list the instances used for parameter tuning (train) and the main experiments (test). The log_ss_size column gives log10 of the size of the search space, measured by the 'prescient' solver (see paper for details).

Run

Command line qualifiers:

--puzzle (sudoku, futoshiki, nurikabe, hashi, zpg) puzzle type

--file filename - file containing puzzle instance

--solver (aco, ga, backtrack, random) solver type - default random

--timeout seconds - timeout in seconds, default 0 (no timeout)

--evaluations maxeval - maximum number of puzzle evaluations, default 0 (unlimited)

GA options

--length n - chromosome length (ints or bits)

--chromosome (int, bitmap) - chromosome representation

--mutation value - mutation rate, default 1/length

--crossover value - crossover fraction (0 to 1, default 0.98)

--population n - population size, default 100

--tournament n - tournament size, default 10

ACO options

--ants n - number of ants (default 10)

--q0 value - ACS q0 parameter (default 0.9)

--rho value - ACS rho parameter (default 0.9)

--evap value - best-value evaporation constant (default 0.005)

SA Options

--maxtemp value - initial temperature (default 10000)

--tempchange value - change in temperature per iteration (default 0.98)

About

Japanese Puzzles as Optimization Problems

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages