{"created":"2023-05-15T15:32:02.747276+00:00","id":4816,"links":{},"metadata":{"_buckets":{"deposit":"889ef352-9ae2-4075-b123-0e3f05eab0a0"},"_deposit":{"created_by":17,"id":"4816","owners":[17],"pid":{"revision_id":0,"type":"depid","value":"4816"},"status":"published"},"_oai":{"id":"oai:barrel.repo.nii.ac.jp:00004816","sets":["1:536","4"]},"author_link":["10510","10511"],"item_1_biblio_info_5":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2015-05","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"3","bibliographicPageEnd":"283","bibliographicPageStart":"276","bibliographicVolumeNumber":"23","bibliographic_titles":[{"bibliographic_title":"Journal of Information Processing","bibliographic_titleLang":"en"}]}]},"item_1_description_18":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"Among many variations of pencil puzzles, Latin square Completion-Type puzzles (LSCPs) are quite popular for puzzle fans. Concerning these puzzles, the solvability has been investigated from the viewpoint of time complexity in the last decade; it has been shown that, in most of these puzzles, it is NP-complete to determine whether a given puzzle instance has a proper solution. In this paper, we investigate the approximability of three LSCPs: Sudoku, Futoshiki and Kenken. We formulate each LSCP as a maximization problem that asks to fill as many cells as possible, under the Latin square condition and the inherent condition. We then propose simple generic approximation algorithms for them and analyze their approximation ratios.","subitem_description_language":"en","subitem_description_type":"Abstract"}]},"item_1_publisher_6":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"Information Processing Society of Japan","subitem_publisher_language":"en"}]},"item_1_relation_8":{"attribute_name":"DOI","attribute_value_mlt":[{"subitem_relation_type":"isIdenticalTo","subitem_relation_type_id":{"subitem_relation_type_id_text":"info:doi/10.2197/ipsjjip.23.276","subitem_relation_type_select":"DOI"}}]},"item_1_rights_12":{"attribute_name":"権利表記","attribute_value_mlt":[{"subitem_rights":"利用は著作権の範囲内に限定される","subitem_rights_language":"ja"}]},"item_1_source_id_11":{"attribute_name":"書誌ID（NCID）","attribute_value_mlt":[{"subitem_source_identifier":"AA00700121","subitem_source_identifier_type":"NCID"}]},"item_1_source_id_7":{"attribute_name":"ISSN / EISSN","attribute_value_mlt":[{"subitem_source_identifier":"0387-6101","subitem_source_identifier_type":"PISSN"}]},"item_1_subject_16":{"attribute_name":"日本十進分類法","attribute_value_mlt":[{"subitem_subject":"007","subitem_subject_language":"ja","subitem_subject_scheme":"NDC"}]},"item_1_subject_17":{"attribute_name":"NIIサブジェクト","attribute_value_mlt":[{"subitem_subject":"情報学","subitem_subject_language":"ja","subitem_subject_scheme":"Other"}]},"item_1_version_type_15":{"attribute_name":"テキストバージョン","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_970fb48d4fbd8a85","subitem_version_type":"VoR"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Haraguchi, Kazuya","creatorNameLang":"en","creatorNameType":"Personal"}],"nameIdentifiers":[{"nameIdentifier":"10510","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Ono, Hirotaka","creatorNameLang":"en","creatorNameType":"Personal"}],"nameIdentifiers":[{"nameIdentifier":"10511","nameIdentifierScheme":"WEKO"}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2016-01-26"}],"displaytype":"detail","filename":"JIP_23_3.pdf","filesize":[{"value":"329.5 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"JIP_23_3.pdf","url":"https://barrel.repo.nii.ac.jp/record/4816/files/JIP_23_3.pdf"},"version_id":"2fa8722b-bd3b-487f-b811-caf6c705dd3d"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"Latin square Completion-Type puzzles","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"approximation algorithms","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"Sudoku","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"Futoshiki","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"Kenken","subitem_subject_language":"en","subitem_subject_scheme":"Other"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"How Simple Algorithms Can Solve Latin Square Completion-Type Puzzles Approximately","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"How Simple Algorithms Can Solve Latin Square Completion-Type Puzzles Approximately","subitem_title_language":"en"}]},"item_type_id":"1","owner":"17","path":["4","536"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2015-05-15"},"publish_date":"2015-05-15","publish_status":"0","recid":"4816","relation_version_is_last":true,"title":["How Simple Algorithms Can Solve Latin Square Completion-Type Puzzles Approximately"],"weko_creator_id":"17","weko_shared_id":-1},"updated":"2025-03-17T00:20:54.977700+00:00"}