Thursday, February 12, 2015

0hn0.com solver

Below is a solver for the puzzles at 0hn0.com. Using it I calculated that an empty 2x2 puzzle can be solved in 10 different ways, an empty 3x3 puzzle can be solved in 250 different ways, and an empty 4x4 puzzle can be solved in in 22946 different ways.

% uses clingo ASP solver from http://potassco.sourceforge.net/
% USAGE: clingo thisfile.txt
% The solution is in the squarecolor(Y,X,blue;red) terms in the output.

% problem specification; example 8x8 puzzle from 0hn0.com:
% - * 6 - 5 - - -
% - * - * - - 5 -
% - - - - - 4 8 -
% 4 - * - * - - -
% - - 5 - * 2 - -
% - - - - - 7 - 3
% 3 - - 7 6 - - -


% begin problem description in ASP
% num(Y,X,N) means the number in square (Y,X) is N
% (squares with numbers are all initially blue.)
% red(Y,X) means square (Y,X) is initially red.
#const ysize=8.
#const xsize=8.


num(1,1,1).
num(1,2,1).
num(1,5,2).
num(1,8,1).
red(2,2).
num(2,3,6).
num(2,5,5).
red(3,2).
red(3,4).
num(3,7,5).
num(4,6,4).
num(4,7,8).
num(5,1,4).
red(5,3).
red(5,5).
num(6,3,5).
red(6,5).
num(6,6,2).
num(7,6,7).
num(7,8,3).
num(8,1,3).
num(8,4,7).
num(8,5,6).

% end ASP problem description
% nothing below this line needs to be edited

% list the valid colors and directions
color(red;blue).
dir(up;down;left;right).

% squares with numbers are blue
squarecolor(Y,X,blue) :- num(Y,X).

% squares specified as red in the initial problem are red in the solution
squarecolor(Y,X,red) :- red(Y,X).

% num(Y,X) :- square(Y,X) was assigned a number in the initial problem
num(Y,X) :- num(Y,X,C).

% choose a color for each initially-empty square
1 { squarecolor(Y,X,C) : color(C) } 1 :- square(Y,X), not num(Y,X), not red(Y,X).

% dir(Y,X,D,YD,XD) = (YD,XD) is 1 square in direction D from (Y,X)
% square 0,0 is used to represent an invalid square, e.g. going up
% from a square in the top row.
row(1..ysize).
col(1..xsize).
square(Y,X) :- row(Y), col(X).
dirok(Y,X, up, Y-1,X) :- square(Y,X).
dirok(Y,X, down, Y+1,X) :- square(Y,X).
dirok(Y,X, left, Y,X-1) :- square(Y,X).
dirok(Y,X, right, Y,X+1) :- square(Y,X).
dir(Y,X,D, 0,0) :- square(Y,X), dir(D), dirok(Y,X,D,YD,XD), not square(YD,XD).
dir(Y,X,D, YD,XD) :- square(Y,X), dir(D), dirok(Y,X,D,YD,XD), square(YD,XD).

% consider any invalid square (0,0) to be colored red.
squarecolor(0,0,red).


% seendir(Y,X,D,N) = N blue squares can be seen in direction D from square (Y,X)
seendir(Y,X,D,1+SD) :- squarecolor(Y,X,blue), dir(D), dir(Y,X,D,YD,XD), seendir(YD,XD,D,SD).

% red squares block vision, so nothing can be seen in any direction from a red square.
seendir(Y,X,D,0) :- squarecolor(Y,X,red), dir(D).

% seen(Y,X,N) = Blue square (Y,X) can see N blue discs in all directions.
seen(Y,X,U+D+L+R-4) :- square(Y,X), squarecolor(Y,X,blue), seendir(Y,X,up,U),
                seendir(Y,X,down,D), seendir(Y,X,left,L), seendir(Y,X,right,R).


% each blue square must see at least 1 other blue square (can't see only 0)
:- squarecolor(Y,X,blue), seen(Y,X,0).

% every blue square must see a number of neighbors equal to the number written on it.
:- num(Y,X,C), seen(Y,X,D), C != D.

Followers

Contributors