Mutilated chessboard problem (original) (raw)
مسألة رقعة الشطرنج المنقوصة من النوع الذي يطلب فيه تغطية رقعة شطرنج. طرح الأحجية جامو وسترن (بالإنجليزية: Gamow & Stern) سنة 1958 وناقشها في عمود ألعاب من الرياضيات بمجلة ساينتفك أمريكان (بالإنجليزية: Scientific American). تنص الأحجية على ما يلي :على رقعة شطرنج 8×8 ينقصها مربعين متناظرين على القطر (ما يترك 62 مربع)،يطلب هل من الممكن تغطية الرقعة بقطع دومينو 2×1 عددها 31 تغطية كاملة ؟
| Property | Value |
|---|---|
| dbo:abstract | El problema de l'escaquer mutilat és un puzle proposat pel filòsof Max Black al seu llibre Pensament Crític (1946). Fou estudiat més tard per (1954), o per Martin Gardner a la seva columna Mathematical Games a la revista Scientific American. El problema és com segueix: Donat un escaquer estàndard de 8x8 on dues cantonades de la mateixa diagonal han estat tretes, deixant així 62 caselles al tauler. Seria llavors possible de situar-hi 31 peces de dòmino de mida 2x1 caselles, de tal manera que es cobrissin totes les caselles? La majoria de consideracions sobre aquest problema a la literatura existent es dirigeixen a solucions «en el sentit conceptual» sense proves. John McCarthy va proposar-lo com un problema difícil per a sistemes de prova automatitzada. De fet, la seva solució fent servir un d'inferència és exponencialment difícil. (ca) مسألة رقعة الشطرنج المنقوصة من النوع الذي يطلب فيه تغطية رقعة شطرنج. طرح الأحجية جامو وسترن (بالإنجليزية: Gamow & Stern) سنة 1958 وناقشها في عمود ألعاب من الرياضيات بمجلة ساينتفك أمريكان (بالإنجليزية: Scientific American). تنص الأحجية على ما يلي :على رقعة شطرنج 8×8 ينقصها مربعين متناظرين على القطر (ما يترك 62 مربع)،يطلب هل من الممكن تغطية الرقعة بقطع دومينو 2×1 عددها 31 تغطية كاملة ؟ (ar) El problema del tablero de ajedrez mutilado es un rompecabezas de enlosado propuesto por el filósofo analítico Max Black en su libro "Critical Thinking" (Pensamiento Crítico) (1946). Fue posteriormente analizado por Solomon W. Golomb (1954), y por Martin Gardner en su columna del Scientific American "Juegos Matemáticos". El problema se plantea como sigue: Supóngase que a un tablero de ajedrez estándar de 8×8 se le eliminan dos esquinas diagonalmente opuestas, dejando 62 casillas. ¿Es posible colocar 31 piezas de dominó de tamaño 2×1 recubriendo todo el tablero? La mayoría de las consideraciones sobre este problema en la literatura relacionada proporcionan soluciones "en el sentido conceptual", pero sin pruebas. John McCarthy lo propuso como un "problema duro" para sistemas de prueba automatizada. De hecho, la solución que utiliza el sistema de resolución por inferencia es exponencialmente duro. (es) Le problème de l'échiquier mutilé est un puzzle de pavage proposé par le philosophe Max black dans son livre Critical Thinking (1946). Il a été débattu par Solomon W. Golomb (1954), par et par Martin Gardner dans sa rubrique "Jeux Mathématiques" dans Scientific American. Le problème est comme suit : Supposons qu'un échiquier standard 8 × 8 ait deux coins diagonalement opposés enlevés, laissant 62 carrés. Est-il possible de placer 31 dominos de taille 2 × 1 afin de couvrir l'ensemble de ces carrés? La plupart des considérations de ce problème dans la littérature apportent des solutions "au sens conceptuel" sans preuves. John McCarthy, l'a présenté comme un problème difficile pour les systèmes de preuve automatisés. En fait, sa solution utilisant le système de résolution d'inférence est exponentiellement difficile. (fr) The mutilated chessboard problem is a tiling puzzle posed by Max Black in 1946 that asks: Suppose a standard 8×8 chessboard (or checkerboard) has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31 dominoes of size 2×1 so as to cover all of these squares? It is an impossible puzzle: there is no domino tiling meeting these conditions. One proof of its impossibility uses the fact that, with the corners removed, the chessboard has 32 squares of one color and 30 of the other, but each domino must cover equally many squares of each color. More generally, if any two squares are removed from the chessboard, the rest can be tiled by dominoes if and only if the removed squares are of different colors. This problem has been used as a test case for automated reasoning, creativity, and the philosophy of mathematics. (en) Nesse problema, temos um tabuleiro de jogo de xadrez onde dois quadras em cantos opostos foram cortados. O problema consiste em cobrir totalmente o tabuleiro com pedras de jogo de dominó, considerando que uma pedra cobre exatamente duas casas contíguas do tabuleiro. A abstração que será feita nesse caso é a de não considerar a cor das casas. Sendo o estado inicial o tabuleiro vazio, tem 108 estados possíveis depois de ter colocado a primeira pedra de dominó. Pode-se verificar que por um tabuleiro de tamanho n o número de possibilidades para colocar a primeira pedra é 2n(n-1)-4. Para colocar a segunda pedra, o número de possibilidade varia entre 101 e 104, dependendo do número de pares de casas contíguas que a pedra impede de usar. (pt) Проблема обрізаної шахівниці — це , запропонована філософом Максом Блеком у книзі Critical Thinking (1946). Пізніше цієї проблеми торкалися Соломон Голомб (1954), та Мартін Гарднер в його колонці «Математичні ігри» в Scientific American. Проблема формулюється наступним чином: Припустімо, зі стандартної (8x8) шахівниці видалили дві клітинки в діагонально протилежних кутах, і залишилось 62 клітинки. Чи можливо розмістити 31 доміно розміром 2x1 так, щоб покрити всі ці клітинки? Більшість розмірковувань над цією проблемою надають рішення «в концептуальному сенсі» без доказів. Джон МакКарті запропонував її як складну проблему для автоматичних доказових систем. Насправді, рішення цієї проблеми з використанням резолютивної системи виходу надзвичайно важке. (uk) 肢解國際象棋盤問題（英語：mutilated chessboard problem）屬於，最早是由在1946年的《Critical Thinking》中提出。後來數學家所羅門·格倫布（1954年）及馬丁·加德納（在雜誌《科學人》中的專欄《Mathematical Games》中）都有討論到此問題。問題：「假設一個標準的8x8格國際象棋棋盤，移除對角的2個方塊，餘下62個方塊。可不可以用31個2x1格骨牌來蓋上餘下方塊呢？」 大部份討論此問題的文獻是在概念上說明此問題，電腦科學家约翰·麦卡锡認為這問題對於自動證明系統而言是很難的問題。若使用归结系統，其解的困難度是指數等級。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Mutilated_chessboard_vectorized.svg?width=300 |
| dbo:wikiPageExternalLink | http://demonstrations.wolfram.com/GomorysTheorem/ |
| dbo:wikiPageID | 9308202 (xsd:integer) |
| dbo:wikiPageLength | 30769 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1117623824 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Tiling_puzzles dbr:Proof_assistant dbr:Scientific_American dbr:Mizar_system dbr:Bipartite_matching dbr:Relaxation_(approximation) dbr:Resolution_(logic) dbr:Cuboid dbr:De_Bruijn's_theorem dbr:Numbrix dbc:Unsolvable_puzzles dbr:Max_Black dbr:Chessboard dbr:Nqthm dbr:Claude_Berge dbr:Cognitive_science dbr:George_Gamow dbr:George_Stanley_Rushbrooke dbr:Constraint_satisfaction_problem dbr:Creativity dbr:Shmuel_Winograd dbr:Hall's_marriage_theorem dbr:Automated_proof dbc:Logic_puzzles dbr:First-order_logic dbc:Mathematical_chess_problems dbr:Checkerboard dbr:Fairy_chess_piece dbr:File:Mutilated_chessboard_vectorized.svg dbr:List_of_Martin_Gardner_Mathematical_Games_columns dbr:Knowledge_representation dbr:Mathematical_proof dbr:Isabelle_(proof_assistant) dbr:Tatami dbr:Statistical_mechanics dbr:Artificial_intelligence dbr:John_McCarthy_(computer_scientist) dbr:Bipartite_graph dbr:Tiling_puzzle dbr:Polyomino dbr:Domino_tiling dbr:Dominoes dbr:Automated_reasoning dbr:Martin_Gardner dbr:Philosophy_of_mathematics dbr:Solomon_W._Golomb dbr:Group_theory dbr:Polynomial_time dbr:The_Wolfram_Demonstrations_Project dbr:Ralph_E._Gomory dbr:Ralph_H._Fowler dbr:Wazir_(chess) dbr:Semidefinite_programming dbr:Hamiltonian_cycle dbr:Grid_graph dbr:Impossible_puzzle dbr:File:Equicolored_unmatchable.svg dbr:File:Gomory's_theorem.svg dbr:File:Mutilated_chessboard_problem_example.jpg |
| dbp:cs1Dates | ly (en) |
| dbp:date | October 2022 (en) |
| dbp:wikiPageUsesTemplate | dbt:Clear dbt:Commons_category dbt:Good_article dbt:R dbt:Reflist dbt:Short_description dbt:Use_list-defined_references dbt:Use_mdy_dates dbt:Chess_diagram_small |
| dct:subject | dbc:Tiling_puzzles dbc:Unsolvable_puzzles dbc:Logic_puzzles dbc:Mathematical_chess_problems |
| gold:hypernym | dbr:Puzzle |
| rdf:type | yago:WikicatLogicPuzzles yago:WikicatMathematicalChessProblems yago:WikicatTilingPuzzles yago:Abstraction100002137 yago:Attribute100024264 yago:Communication100033020 yago:Condition113920835 yago:Difficulty114408086 yago:Message106598915 yago:Problem106784003 yago:Problem114410605 yago:Puzzle106784639 yago:Question106783768 dbo:VideoGame yago:State100024720 yago:Subject106599788 yago:WikicatPuzzles |
| rdfs:comment | مسألة رقعة الشطرنج المنقوصة من النوع الذي يطلب فيه تغطية رقعة شطرنج. طرح الأحجية جامو وسترن (بالإنجليزية: Gamow & Stern) سنة 1958 وناقشها في عمود ألعاب من الرياضيات بمجلة ساينتفك أمريكان (بالإنجليزية: Scientific American). تنص الأحجية على ما يلي :على رقعة شطرنج 8×8 ينقصها مربعين متناظرين على القطر (ما يترك 62 مربع)،يطلب هل من الممكن تغطية الرقعة بقطع دومينو 2×1 عددها 31 تغطية كاملة ؟ (ar) Nesse problema, temos um tabuleiro de jogo de xadrez onde dois quadras em cantos opostos foram cortados. O problema consiste em cobrir totalmente o tabuleiro com pedras de jogo de dominó, considerando que uma pedra cobre exatamente duas casas contíguas do tabuleiro. A abstração que será feita nesse caso é a de não considerar a cor das casas. Sendo o estado inicial o tabuleiro vazio, tem 108 estados possíveis depois de ter colocado a primeira pedra de dominó. Pode-se verificar que por um tabuleiro de tamanho n o número de possibilidades para colocar a primeira pedra é 2n(n-1)-4. Para colocar a segunda pedra, o número de possibilidade varia entre 101 e 104, dependendo do número de pares de casas contíguas que a pedra impede de usar. (pt) 肢解國際象棋盤問題（英語：mutilated chessboard problem）屬於，最早是由在1946年的《Critical Thinking》中提出。後來數學家所羅門·格倫布（1954年）及馬丁·加德納（在雜誌《科學人》中的專欄《Mathematical Games》中）都有討論到此問題。問題：「假設一個標準的8x8格國際象棋棋盤，移除對角的2個方塊，餘下62個方塊。可不可以用31個2x1格骨牌來蓋上餘下方塊呢？」 大部份討論此問題的文獻是在概念上說明此問題，電腦科學家约翰·麦卡锡認為這問題對於自動證明系統而言是很難的問題。若使用归结系統，其解的困難度是指數等級。 (zh) El problema de l'escaquer mutilat és un puzle proposat pel filòsof Max Black al seu llibre Pensament Crític (1946). Fou estudiat més tard per (1954), o per Martin Gardner a la seva columna Mathematical Games a la revista Scientific American. El problema és com segueix: Donat un escaquer estàndard de 8x8 on dues cantonades de la mateixa diagonal han estat tretes, deixant així 62 caselles al tauler. Seria llavors possible de situar-hi 31 peces de dòmino de mida 2x1 caselles, de tal manera que es cobrissin totes les caselles? (ca) El problema del tablero de ajedrez mutilado es un rompecabezas de enlosado propuesto por el filósofo analítico Max Black en su libro "Critical Thinking" (Pensamiento Crítico) (1946). Fue posteriormente analizado por Solomon W. Golomb (1954), y por Martin Gardner en su columna del Scientific American "Juegos Matemáticos". El problema se plantea como sigue: Supóngase que a un tablero de ajedrez estándar de 8×8 se le eliminan dos esquinas diagonalmente opuestas, dejando 62 casillas. ¿Es posible colocar 31 piezas de dominó de tamaño 2×1 recubriendo todo el tablero? (es) The mutilated chessboard problem is a tiling puzzle posed by Max Black in 1946 that asks: Suppose a standard 8×8 chessboard (or checkerboard) has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31 dominoes of size 2×1 so as to cover all of these squares? (en) Le problème de l'échiquier mutilé est un puzzle de pavage proposé par le philosophe Max black dans son livre Critical Thinking (1946). Il a été débattu par Solomon W. Golomb (1954), par et par Martin Gardner dans sa rubrique "Jeux Mathématiques" dans Scientific American. Le problème est comme suit : Supposons qu'un échiquier standard 8 × 8 ait deux coins diagonalement opposés enlevés, laissant 62 carrés. Est-il possible de placer 31 dominos de taille 2 × 1 afin de couvrir l'ensemble de ces carrés? (fr) Проблема обрізаної шахівниці — це , запропонована філософом Максом Блеком у книзі Critical Thinking (1946). Пізніше цієї проблеми торкалися Соломон Голомб (1954), та Мартін Гарднер в його колонці «Математичні ігри» в Scientific American. Проблема формулюється наступним чином: Припустімо, зі стандартної (8x8) шахівниці видалили дві клітинки в діагонально протилежних кутах, і залишилось 62 клітинки. Чи можливо розмістити 31 доміно розміром 2x1 так, щоб покрити всі ці клітинки? (uk) |
| rdfs:label | مسألة رقعة الشطرنج المنقوصة (ar) Problema de l'escaquer mutilat (ca) Problema del tablero de ajedrez mutilado (es) Problème de l'échiquier mutilé (fr) Mutilated chessboard problem (en) Tabuleiro mutilado de xadrez (pt) Проблема обрізаної шахівниці (uk) 肢解國際象棋盤問題 (zh) |
| owl:sameAs | freebase:Mutilated chessboard problem yago-res:Mutilated chessboard problem wikidata:Mutilated chessboard problem dbpedia-ar:Mutilated chessboard problem dbpedia-ca:Mutilated chessboard problem dbpedia-es:Mutilated chessboard problem dbpedia-fi:Mutilated chessboard problem dbpedia-fr:Mutilated chessboard problem dbpedia-he:Mutilated chessboard problem dbpedia-pt:Mutilated chessboard problem dbpedia-uk:Mutilated chessboard problem dbpedia-zh:Mutilated chessboard problem https://global.dbpedia.org/id/2hwZb |
| prov:wasDerivedFrom | wikipedia-en:Mutilated_chessboard_problem?oldid=1117623824&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Equicolored_unmatchable.svg wiki-commons:Special:FilePath/Gomory's_theorem.svg wiki-commons:Special:FilePath/Mutilated_chessboard_problem_example.jpg wiki-commons:Special:FilePath/Mutilated_chessboard_vectorized.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Mutilated_chessboard_problem |
| is dbo:wikiPageRedirects of | dbr:Gomory's_theorem dbr:Gomory's_Theorem dbr:Dominoes_on_a_checker_board_puzzle dbr:Dominoes_on_a_chessboard_puzzle dbr:Mutilated_checkerboard dbr:Mutilated_checkerboard_problem dbr:Mutilated_chessboard dbr:Gomory_theorem |
| is dbo:wikiPageWikiLink of | dbr:Tromino dbr:Algorithmic_Puzzles dbr:Domino_(mathematics) dbr:List_of_impossible_puzzles dbr:Chess_puzzle dbr:Chessboard dbr:Parity_(mathematics) dbr:Mathematical_puzzle dbr:Gomory's_theorem dbr:Gomory's_Theorem dbr:Tiling_puzzle dbr:Domino_tiling dbr:Dominoes_on_a_checker_board_puzzle dbr:Dominoes_on_a_chessboard_puzzle dbr:Polyominoes:_Puzzles,_Patterns,_Problems,_and_Packings dbr:Mutilated_checkerboard dbr:Mutilated_checkerboard_problem dbr:Mutilated_chessboard dbr:Gomory_theorem |
| is foaf:primaryTopic of | wikipedia-en:Mutilated_chessboard_problem |
