{"updated":"2025-01-20T06:47:24.494428+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00096758","sets":["581:7002:7344"]},"path":["7344"],"owner":"11","recid":"96758","title":["Yosenabe is NP-complete"],"pubdate":{"attribute_name":"公開日","attribute_value":"2013-12-15"},"_buckets":{"deposit":"0bf5c870-9db1-4834-a884-69c949db6edd"},"_deposit":{"id":"96758","pid":{"type":"depid","value":"96758","revision_id":0},"owners":[11],"status":"published","created_by":11},"item_title":"Yosenabe is NP-complete","author_link":["358663","358664"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Yosenabe is NP-complete"},{"subitem_title":"Yosenabe is NP-complete","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"[一般論文(テクニカルノート)] NP-complete, computational complexity, one-player game, Yosenabe","subitem_subject_scheme":"Other"}]},"item_type_id":"2","publish_date":"2013-12-15","item_2_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Hiroshima University, Graduate School of Engineering"}]},"item_2_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Hiroshima University, Graduate School of Engineering","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"publish_status":"0","weko_shared_id":11,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/96758/files/IPSJ-JNL5412001.pdf","label":"IPSJ-JNL5412001"},"date":[{"dateType":"Available","dateValue":"2015-12-15"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-JNL5412001.pdf","filesize":[{"value":"320.0 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"8"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"d58f6b36-f023-40e7-b598-883c9d7e5a0f","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2013 by the Information Processing Society of Japan"}]},"item_2_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Chuzo, Iwamoto"}],"nameIdentifiers":[{}]}]},"item_2_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Chuzo, Iwamoto","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_2_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN00116647","subitem_source_identifier_type":"NCID"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_6501","resourcetype":"journal article"}]},"item_2_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1882-7764","subitem_source_identifier_type":"ISSN"}]},"item_2_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"Yosenabe is one of Nikoli's pencil puzzles, which is played on a rectangular grid of cells. Some of the cells are colored gray, and two gray cells are considered connected if they are adjacent vertically or horizontally. A set of connected gray cells is called a gray area. Some of the gray areas are labeled by numbers, and some of the non-gray cells contain circles with numbers. The object of the puzzle is to draw arrows, vertically or horizontally, from all circles to gray areas so that (i) the arrows do not bend, and do not cross other circles or lines of other arrows, (ii) the number in a gray area is equal to the total of the numbers of the circles which enter the gray area, and (iii) gray areas with no numbers may have any sum total, but at least one circle must enter each gray area. It is shown that deciding whether a Yosenabe puzzle has a solution is NP-complete.\n\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.22(2014) No.1 (online)\nDOI http://dx.doi.org/10.2197/ipsjjip.22.40\n------------------------------","subitem_description_type":"Other"}]},"item_2_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"Yosenabe is one of Nikoli's pencil puzzles, which is played on a rectangular grid of cells. Some of the cells are colored gray, and two gray cells are considered connected if they are adjacent vertically or horizontally. A set of connected gray cells is called a gray area. Some of the gray areas are labeled by numbers, and some of the non-gray cells contain circles with numbers. The object of the puzzle is to draw arrows, vertically or horizontally, from all circles to gray areas so that (i) the arrows do not bend, and do not cross other circles or lines of other arrows, (ii) the number in a gray area is equal to the total of the numbers of the circles which enter the gray area, and (iii) gray areas with no numbers may have any sum total, but at least one circle must enter each gray area. It is shown that deciding whether a Yosenabe puzzle has a solution is NP-complete.\n\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.22(2014) No.1 (online)\nDOI http://dx.doi.org/10.2197/ipsjjip.22.40\n------------------------------","subitem_description_type":"Other"}]},"item_2_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographic_titles":[{"bibliographic_title":"情報処理学会論文誌"}],"bibliographicIssueDates":{"bibliographicIssueDate":"2013-12-15","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"12","bibliographicVolumeNumber":"54"}]},"relation_version_is_last":true,"weko_creator_id":"11"},"created":"2025-01-18T23:43:29.906577+00:00","id":96758,"links":{}}