{"entities":{"Q1395573":{"pageid":1406313,"ns":120,"title":"Item:Q1395573","lastrevid":70325172,"modified":"2026-04-13T14:01:10Z","type":"item","id":"Q1395573","labels":{"en":{"language":"en","value":"Pushing blocks is hard."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1944827"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1395573$5ED70D52-5CCC-4D8D-AECD-9B18BC8BC767","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2b8a3e930ab9d989eacf7e0006a503ff8f1bd939","datavalue":{"value":{"text":"Pushing blocks is hard.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1395573$BD914D03-85A9-44D7-B743-E02A0CA0B402","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c8214890118fa9be20d49380d3916ebd9f4d627f","datavalue":{"value":"1041.65021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1395573$114432EF-03A5-4B9A-9068-9316A1615008","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7b104e196c1f5fe9f61583a42b5d23acebde4bb7","datavalue":{"value":"10.1016/S0925-7721(02)00170-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1395573$80CAE0C4-A9A7-40D7-9B55-039510F506A0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3e8ca735896d8fd1610d4d740dab3fd7cadda6d4","datavalue":{"value":{"entity-type":"item","numeric-id":1380459,"id":"Q1380459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1395573$FAC4E900-FE39-4276-AAC8-B19B6974F6ED","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"285beb29e5e30a7ba8792191178d7f52682884ef","datavalue":{"value":{"entity-type":"item","numeric-id":175378,"id":"Q175378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1395573$E61FD9A2-08CA-43CC-90A6-108F7AD74904","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4a64159b588e3459a5fca46f6d5073d79064c685","datavalue":{"value":{"time":"+2003-07-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1395573$415BE1D2-0369-4FAF-A18A-62BE46C7BAD3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ec58e09192eb0e90db88a9d091d4677507a8d8c8","datavalue":{"value":"The authors study several variations of simpler puzzles and show that the models are NP-hard. The results subsume a number of previous NP-hardness proofs of pushing-block variations, and solve the Push-X open problem. The main idea in the is to force the robot to follow constrained Eulerian tours of planar graphs and carry a constant amount of information along each edge of the graph. Moreover it is build a kind of logic engine. This approach is innovative and contrast with other previous approaches of building circuits based on graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1395573$8A7B2880-007D-4BEB-8319-50382D1CAE8E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2f9e16b52bc8c390b9fea0fb31de1975133dd070","datavalue":{"value":{"entity-type":"item","numeric-id":455938,"id":"Q455938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1395573$53113227-56E4-40D1-B315-7F68D96FADEE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1395573$95959CCD-4675-492A-BF01-3491E491AEF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"355ea56a4f84d7973d94c70a8b1f92966ec83542","datavalue":{"value":"65Y20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1395573$D7684668-2E55-462E-BCE2-13E3794F8482","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1395573$F20FE719-6964-497F-8D1C-7A34811CFE55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3c9759ba1beabf7a5237e2e05cc9f021be9a23e5","datavalue":{"value":"70B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1395573$230BCDA3-AE6A-42F6-9E9A-797E13B8FAB6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ddfeafd1d65d4f62198b8a1823bcbb619a5d59fa","datavalue":{"value":"1944827","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1395573$C6429FDA-2B26-4D95-B408-0ED023D90FB5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1395573$3810A3A8-6D83-4D4E-9309-2CAC7A05A216","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1395573$5C6567FE-AEF9-4F37-A152-D472A0713F00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f3c4174a5d716f293c7527ce1cefdfb920908bc","datavalue":{"value":"motion planning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1395573$E1EC43D4-FB91-4997-9190-AD5C12891B45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"535d360cb8c0c1aa80f78a968709bdfad17bee58","datavalue":{"value":"combinatorial games","type":"string"},"datatype":"string"},"type":"statement","id":"Q1395573$266138A9-BC13-4FA9-B6E9-3932E8D4B811","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1395573$1D435554-ED8E-48E9-8623-0498B79A6478","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6d2b48426a8fa4316d3fed1f93efe215d58b00b","datavalue":{"value":"push-X open problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1395573$862BFE53-1193-42B9-B8D4-012F293DEDA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6dd3b966f2c41fb59fe2959bbf19800704f516e","datavalue":{"value":"robot","type":"string"},"datatype":"string"},"type":"statement","id":"Q1395573$0ED215FC-FE37-441B-B9C6-7C102141E069","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e380adfb0f8fbf4ca071c80e09c7fa08edc4a86d","datavalue":{"value":"Eulerian tours of planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1395573$236FA257-1BAD-43DB-A602-F4FF2656CC47","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1395573$A63B5636-545F-4830-9CE4-1D34F9EC00BA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"625a03d46620a33bee2de786dbc5e81f0c26accc","datavalue":{"value":{"entity-type":"item","numeric-id":3154375,"id":"Q3154375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1395573$3B6AB7E9-D05C-4179-B9C8-2EF110262AFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f03a5c0ef3c5fcffeeb0f59690768c9aa053660d","datavalue":{"value":{"entity-type":"item","numeric-id":4232783,"id":"Q4232783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1395573$6FD23533-B298-4A59-A3C7-ECAC79B59302","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80dd6b91453ec62471b997a9f3d4dc3b6a4399d2","datavalue":{"value":{"entity-type":"item","numeric-id":1818116,"id":"Q1818116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1395573$7D6753BA-873F-42CA-933C-080201A93B20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1395573$C919017C-1964-4664-9376-42B7E2D843C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1395573$B9FFFE37-0152-4BBA-86C0-5B0EAA04102B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e05c02488d41603e6960c473a2f65c63278ee1f0","datavalue":{"value":{"entity-type":"item","numeric-id":4401030,"id":"Q4401030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1395573$BA1D4733-BD83-47E7-BC38-5305A2E45DF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bb12728089679565e1bcb9883e0d55e8925b6d0","datavalue":{"value":{"entity-type":"item","numeric-id":1356169,"id":"Q1356169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1395573$8478BF66-0E5F-4568-8163-14C63D276D8B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"550e336018f1d6cd82f740f7ef99c8f8c3adb1d1","datavalue":{"value":"https://doi.org/10.1016/s0925-7721(02)00170-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1395573$8BDB1C4F-CA88-4979-9246-43B0262028F5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b24dbb0866e8747c2d6654b6c9b53d4246c0f8f6","datavalue":{"value":"W1999708036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1395573$B1D43252-8A6B-4259-97F4-8D2E1B0A6A89","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbdac715686828d2e48f4a7d0245a6bf8180b21f","datavalue":{"value":{"entity-type":"item","numeric-id":5283366,"id":"Q5283366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98d3d4f0bb10264fd23fc7e5faa321d884910953","datavalue":{"value":{"amount":"+0.8763437271118164","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1395573$7DA5820E-07E4-4B02-BB75-D2B17B3638A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"abe37a69d43049439e704de30f6beb22db60bab6","datavalue":{"value":{"entity-type":"item","numeric-id":266272,"id":"Q266272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3de4274606a995590270514f76a50467221b6d8f","datavalue":{"value":{"amount":"+0.8248162865638733","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1395573$EDF3D0E7-16CA-42E1-953C-4D315D71A1BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4354a4c30bd56b4ae6868c3c2852c6f1685daef8","datavalue":{"value":{"entity-type":"item","numeric-id":2570127,"id":"Q2570127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15abb1c15c4be90d150d1c40cef22b2aed9e9882","datavalue":{"value":{"amount":"+0.8151236772537231","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1395573$DE70F7F0-F3D0-404E-93FD-DA7E2FBA71D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef131b480e1f9f993cb38a8bdcf7cb41fc489a1e","datavalue":{"value":{"entity-type":"item","numeric-id":1818116,"id":"Q1818116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"360baebacc18174dbcb7ab48dba9ec8474d9217b","datavalue":{"value":{"amount":"+0.8126240372657776","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1395573$42B3E293-50CE-422B-BAA3-D0FA14F65568","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dff56da849f362c3a50cd680481abcfa81f3c745","datavalue":{"value":{"entity-type":"item","numeric-id":6487573,"id":"Q6487573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"482687999793cc06df579db6b19f1be08308a050","datavalue":{"value":{"amount":"+0.7858632206916809","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1395573$46146296-A5F8-4104-AD7A-4C118D4A5ABB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Pushing blocks is hard.","badges":[]}}}}}