Есть ли в этой игре решение

Question

Я занимаюсь разработкой простой игры с использованием Java Swing.Я хочу знать, есть ли у этой конкретной игры решение в следующем сценарии.Если я убежден, что теоретически решение не может быть достигнуто на этом этапе, я отправлю уведомление пользователю.

3x3
http://img814.imageshack.us/img814/7449/screenshot20100924at206.png

4x4
http://img39.imageshack.us/img39/1851/screenshot20100924at241.png

Цель этой игры - заполнить числа от 1 до 8 (или от 1 до 15), используя один доступный пробел, чтобы переместить числа в это пустое пространство,Каждый раз, когда я получаю комбинацию, показанную выше.Я просто хочу убедить себя, что нет способа найти правильное решение из приведенного выше сценария.Пожалуйста, помогите.

РЕДАКТИРОВАТЬ: Решение было размещено в здесь и здесь

Answer 1

Да, и нет.Если вы генерируете числа случайным образом, я считаю, что может возникнуть ситуация, в результате которой головоломка будет неразрешимой.Я бы предложил создать головоломку, начиная с решенной головоломки и выполняя количество (увеличивающихся в зависимости от сложности) ходов в обратном порядке.Таким образом, вы знаете, что конечная головоломка разрешима.

Answer 2

Обсуждение 15 Puzzle , вероятно, даст вам ответ. Я подозреваю, что анализ перестановок в этой загадке применим к вашей маленькой загадке.

Answer 3

Из французской википедии о "Такине" (загадка 15):

Анекдот

Инициал положения Сэм Лойд
Утверждение Лойда о том, что его ждут «Возврат на второй план», а также изменение условий. Предложенный вариант конфигурации, Les Carreaux 14 и 15, а также пространство с хорошим местом для отдыха. Loyd prétendait избегают обещаний 1 000 долларов США за вознаграждение за вознаграждение за лорд, Французский Французский Ямайский округ.
Решение проблемы невозможно. Часть времени, в которой есть все, что нужно сделать 14 и 15, и то, что нужно, и то, что нужно, или нет. С другой стороны, в порядке вещей, с самого начала, с самого начала, количественно, обязательно и без пар. Если это возможно, это может быть как раз от 1 до 15 случаев, в том числе от случая к случаю.

---

Анекдот

Начальная позиция загадки Сэма Лойда 15
Лойд сказал, что он "сделал мир сумасшедшим" ​​с 15 измененными загадками. В предложенной конфигурации плитки 14 и 15 были перевернуты, пустое пространство размещено в правом нижнем углу. Лойд утверждал, что пообещал 1 000 долларов США за того, кто наведет порядок, но награда так и не была востребована. Решить эту проблему невозможно. С одной стороны, он действительно должен поменять местами ячейки 14 и 15, и можно показать, что для этой операции требуется нечетное количество слайдов. С другой стороны, пустое пространство должно возвращаться в исходное положение, операция, которая требует четного количества слайдов. Можно заказать номера от 1 до 15, если пустое пространство изначально находится в левом верхнем углу.

---

Ресурсы:

• fr.wikipedia - Taquin