TAAI 2011 Nonogram tournament result

TAAI 2011 hold Computer Games Tournaments at 2011/11/11-12. This page is the result of Nonogram part.

The rules

This time, we have two tournaments for nonogram, one is "A. Nonogram" and one is "B. Nonogram solver". The rule are different. The detailed rules are documented in A and B (in Chinese).

In brief:

A. Nonogram
- Machine model is not limited. Only allowed to use single CPU core.
- Each participant had to prepare an input file of 100 25x25 nonogram questions before the tournament.
- In the tournament, each program had to solve opponent's input file in 60 minutes.
- For each pair of participants, the winner is determined by the number of solved puzzles. For each puzzle with multiple solutions, the creator of such puzzle loss one solved puzzle.
B. Nonogram solver
- Machine model is not limited. Only allowed to use single CPU core.
- Input input is random generated, with random seed determined by all participants.
- The input file consists 1000 25x25 nonogram questions. The ratio of black cell is ranging from 0.5 to 0.35 in order. (This means that the difficulty of puzzles is roughly increasing in input order.)
- Each program solve these puzzles in order (cannot skip) in 120 minutes.
- For the puzzles with multiple solutions, the program have to generate 2 solutions.
- The rank is determined by the number of solved puzzles.

The participants

Program Name	Author	Organization	Machine
LalaFrogKK	陳干越, 郭青樺, Hao-Hua Kang	NCTU	Intel i7 970 3.6GHz; 8GB RAM
Yayagram	袁倫斌, 李建翰, 婁元輔	NCTU	Intel i7 2600 3.6GHz; 4GB RAM
Naughty	Kuang-che Wu	Google Inc.	Intel i3 540 3GHz; 16GB RAM

Data

Prepared input files from participants:
- LalaFrogKK question, solution
- Yayagram question, solution
- Naughty question, solution
Input file of B
- Random generator: boardgen.py
- The seed and command to generate input:
  ./boardgen.py 25 1000 0.5 0.35 7018923470193576528937659873456413245245746513498421524657453484164646497795613258845312135487455556321154777
- The random generated file: question, solution

Result

A. Nonogram

The links of solved number are the output of that program. The links of solved time are the timing log of that program.

Rank	Program Name	Prepared puzzles with multiple solutions	Solved LalaFrogKK's	Time	Solved Yayagram's	Time	Solved Naughty's	Time
1	LalaFrogKK	0	-	-	100	1082s	100	1802s
2	Naughty	0	5	3600s	60	3600s	-	-
3	Yayagram	99	2	3600s	-	-	25	3600s

B. Nonogram Solver

Rank	Program Name	Solved	Time
1	LalaFrogKK	1000	645.544s
2	Yayagram	766	4989.594s
3	Naughty	509	2325.271s

Comments

Yayagram made a mistake in tournament A. They forgot to check solution uniqueness when generate puzzles. And they can only solve puzzles in input order. So yayagram's score is not good. Actually we can see it is strong in tournament B.

LalaFrogKK is extreme fast and solved all puzzles less than 11 minutes. Yayagram solved 766 puzzle and struggled with #767 for 36 minutes. Naughty solved 509 puzzles and struggled with #510 for 81 minutes.