C++ program to solve nonogram by heuristic and DFS
build program heu
make mode=release
: (default mode)make mode=debug
: problem will print detail messages on each step
normal mode
- line 1:
[row] [column]
- line 2 ~ r+1: row constraints with space seperated
- line r+2 ~ r+c+1: column constraints with space seperated
- if no constraint in a line, just put "0"
There are some example test input files in testdata/input*
tourment mode: used for TCGA or TAAI nonogram input, multiple questions in one file
- line 1:
$[problem index]
(index start from 1) - line 2 ~ boardSize+1: row constraints with
\t
seperated - line boardSize+2 ~ boardSize*2+1: column constraints with
\t
seperated - if no constraint in a line, just put "0"
There are some example test input files testdata/question.txt
After solved, answer will be outputted by number format(1 = black, -1 = white, 0 = space) and graph format(unicode black and white blocks).
There is no simple output(like input) yet.
normal mode(boardsize is decided by first line of input)
./heu -f [result file name] < inputfile
tourment mode(always square, a.k.a, row = column)
./heu -t -s [BoardSize] -n [problemNum] < inputfile
- Heuristic
- Refer to techniques in wiki
- DFS
- Fill a line constraint in one step, if found conflict constraints, backtrack
- Hybrid
- Use heuristic method first, if it isn't solved, do DFS
- Heuristic
- update left-most and right-most possible grid of each constraint
- consider the line which changed the most first
- update left-most and right-most possible grid of each constraint
- DFS
- fill the row or column which has minimum possible variations(the smallest branching factor)
- also apply heuristic as many as possible to decrease further searching space
- Heuristic
- optimize the progress of updating constraints and grids
- DFS
- also consider to fill column at each step 1. is it better to fill only some grids instead of line at each step?
NCTU