Solving the Shirokuro puzzle constraint satisfaction problem with backtracking: a theoretical foundation

Thesis (M.S.) California State University, Los Angeles, 2011Committee members: Gary Brookfield, Russ Abbott, Anthony Shaheen, Grant FraserBacktracking, Constraint Satisfaction Problem, Evolutionary Algorithms, Puzzles, ShirokuroShirokuro is a Japanese puzzle recently featured in Spirit magazine. It is played on a grid of n by n cells, each of which may be empty or contain a black or white disk. The goal is to fill every empty cell with a white or black disk so that the following conditions are satisfied: (1) No two-by-two region contains four disks of the same color. (2) Each pair of like-colored disks is connected via a chain of disks which travels horizontally or vertically through disks of the same color as the pair. We describe Shirokuro as a constraint satisfaction problem, and then propose a backtracking algorithm which solves the puzzle by incrementally building candidate solutions. We propose several relaxed constraints which may help to speed up the algorithm and give an overview of some advanced backtracking techniques