@article{oai:ipsj.ixsq.nii.ac.jp:00142073,
 author = {Uejima, Akihiro and Suzuki, Hiroaki and Uejima, Akihiro and Suzuki, Hiroaki},
 issue = {5},
 journal = {情報処理学会論文誌},
 month = {May},
 note = {We study the computational complexity of a packing puzzle Fillmat, which is a type of pencil-and-paper puzzles made by Japanese puzzle publisher Nikoli. We show that the problem to decide if a given instance of Fillmat has a solution is NP-complete by a reduction from the circuit-satisfiability problem (Circuit-SAT). Our reduction is carefully designed so that we can also prove \textbf{ASP}-completeness of the another-solution-problem.

------------------------------
This is a preprint of an article intended for publication Journal of
Information Processing(JIP). This preprint should not be cited. This
article should be cited as: Journal of Information Processing Vol.23(2015) No.3 (online)
DOI　http://dx.doi.org/10.2197/ipsjjip.23.310
------------------------------, We study the computational complexity of a packing puzzle Fillmat, which is a type of pencil-and-paper puzzles made by Japanese puzzle publisher Nikoli. We show that the problem to decide if a given instance of Fillmat has a solution is NP-complete by a reduction from the circuit-satisfiability problem (Circuit-SAT). Our reduction is carefully designed so that we can also prove \textbf{ASP}-completeness of the another-solution-problem.

------------------------------
This is a preprint of an article intended for publication Journal of
Information Processing(JIP). This preprint should not be cited. This
article should be cited as: Journal of Information Processing Vol.23(2015) No.3 (online)
DOI　http://dx.doi.org/10.2197/ipsjjip.23.310
------------------------------},
 title = {Fillmat is NP-Complete and ASP-Complete},
 volume = {56},
 year = {2015}
}