Skip to content
master
Switch branches/tags
Code

Latest commit

 

Git stats

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time
 
 
www
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Shikaku

Travis Codecov Code Climate

Solves games of Shikaku. This problem has been proven NP-complete.

What it is

Shikaku is a puzzle game, similar to Sudoku. You start with a board which looks like this:

-- -- -- -- -- -- -- 08
07 -- -- -- -- -- -- --
-- -- -- -- -- -- 02 03
-- 08 -- -- -- 04 -- --
-- 04 -- -- -- -- 08 --
-- -- 03 03 -- -- -- --
06 -- -- -- 02 04 -- 02
-- -- -- -- -- -- -- --

The goal is to enclose each number in a rectangle of that number's area. None should overlap, and all squares should be covered.

Basically, any numbered square will be enclosed by a rectangle with dimensions of any of that number's factor pairs.

How the solver works

The solver has 2 main parts.

First, for each given square on the board, it will determine all the possible bounding rectangles which don't overlap with anything else. Then, if any blank square is only covered by one rectangle, or any given square only has one possible solution, mark the squares as final. This is repeated until no more squares are marked as final.

Then, if the board still has unknown squares, it will pick a possible solution, mark it as final, and try to solve that board, starting again from step 1. It will try possible solutions until one of them eventually works. If the board has no unknown squares, it is solved, and the algorithm returns. If, after all the possible solutions are tried, the solution won't work.

About

An efficient, heuristic solver for shikaku puzzles.

Resources

Releases

No releases published

Packages

No packages published