激光網格拼圖

在HN上看到下面的拼圖，並認爲我會在這裏重新發布。它可以使用Simplex來解決，但我想知道是否有更優雅的解決方案，或者是否有人可以證明NP完整性。激光網格拼圖

下面的每個點代表激光的位置。通過用^，v，<或>替換點來指示激光器應該點亮的方向。每個網格位置i，j應該完全由網格[i] [j]激光擊中。在下面的例子中，網格位置0,0應該由網格[0] [0] = 2激光器命中。

激光經過包括其他槍支在內的所有事情（沒有摧毀那些槍支）。

2 2 3 . 1 . 2 2 3 
1 . 2 1 1 . 1 . 2 
2 3 . 1 . 2 . 4 . 
. 3 . 2 2 . 2 3 4 
1 . 2 . 2 3 2 . . 
2 3 . 3 . 3 2 2 . 
3 . 2 4 2 . 2 . 2 
1 1 . . 1 3 . 2 . 
. 2 1 . 2 . 1 . 3

來源

2011-06-15 Jeff

[Code Golf：Lasers]的可能重複（http://stackoverflow.com/questions/1480023/code-golf-lasers）。或不。無論如何，這個問題應該遷移到[Puzzles＆Code Golf]（http://codegolf.stackexchange.com/）。 – 2011-06-15 00:49:27

如果這是爲了某種挑戰，它可能非常適合CodeGold.SE **之後的**，它已被更完整地指定。你可以在[元沙箱]（http://meta.codegolf.stackexchange.com/questions/336/）或[益智實驗室聊天]（http://chat.stackexchange.com/rooms/307）上獲得幫助/高爾夫益智實驗室）。唉!兩者都需要一些代表，所以你可能不得不解決閱讀[我們的一些更好的謎題]（http://codegolf.stackexchange.com/search?tab=votes&q=closed%3a0）。請注意提供的規格類型和標籤。 – dmckee 2011-06-15 02:29:25

如果它可以用Simplex（線性規劃）解決，它不是NP-complete。

來源

2013-02-05 23:00:43

激光網格拼圖

回答

相關問題