Есть там молот, есть там серп…28.05.2023 13:16

Вообще-то я не особый любитель игр. Но прочитал тут на любимом хабре про Кужлёвку и захотелось в это дело поиграть. Не буду утомлять описанием игры, скажу только что игра на мой взгляд исключительно достойная, хотя и не без серьёзных (опять-таки на мой дилетантский взгляд) недостатков. Перехожу к делу. Первый (и пока единственный) затык у меня случился в эпизоде, где Михалычу нужно собрать Серп и Молот из плиток типа пятнашек. Помучившись с этим часа полтора, я понял, что не смогу этого сделать даже за миллион. Хотя может конечно я просто тупой как пробка. Но на берегу спасённый мной мечехвост ждёт сигаретку ! Не могу же я бросить одно, да без курева, древнее живое существо !

Первым делом сделаем скриншот игры с головоломкой, загрузим его в графический редактор (я использую gimp) и перенумеруем в нём все плитки числами от 0 до 7. Числом 8 занумеруем пустую плитку (дырку) :

Пронумерованный скриншот из игры. Размер 741×741.

Попробуем теперь решить задачу в том же графическом редакторе, с помощью вырезаний и вставок. У меня хоть криво и косо, но получилось вот так:

Решение на картинке

Забудем теперь про картинки и будем смотреть только на номера плиток. Тогда задача сформулируется так:

Есть таблица размером 3×3, в которой записаны числа от 0 до 8. Каждым ходом разрешается менять позиции числа 8 и одного из его соседей по горизонтали или вертикали. Требуется найти последовательность ходов, преобразующих таблицу

в таблицу

Поможет нам в этом волновой алгоритм. Волновой алгоритм это алгоритм поиска пути в лабиринте, моделирующий распространение волны в некоей среде в соответствии с принципом Гюйгенса — каждая точка волнового фронта является независимым источником волны. Среда тут может обладать самыми разнообразными свойствами. Содержать препятствия, давать штрафы или поощрения на некоторые пути и т.п. Алгоритм хоть и не очень знаком начинающим, однако применяется повсюду, где грубо говоря требуется попасть из точки А в точку В (либо определить, что такой путь невозможен). От трассировки топологии чипов, до известной офисной игры Lines.

Забудем теперь и про таблицы. Вместо таблиц будем использовать массивы целых, в которых элементы таблицы записаны слева направо, сверху вниз. Например исходная таблица представляется массивом {0, 1, 2, 3, 4, 5, 6, 7, 8}, а целевая — {1, 0, 4, 6, 3, 5, 2, 7, 8}. Среда в которой распространяется наша волна и представляет собой множество таких массивов. Точнее не совсем так. Алгоритм завершится успехом (он может завершиться и не успешно !), когда мы достигнем целевой точки — массива {1, 0, 4, 6, 3, 5, 2, 7, 8}. Но нас интересует не сам факт успеха, а путь от начального массива к целевому. Значит вместе с массивом изображающим таблицу, среда должна хранить ещё и ссылку на предыдущий узел (из которого волна пришла в данную точку). Для самого первого узла (содержащего начальный массив) эта ссылка очевидно будет пустой. Таким образом двигаясь от целевого узла по предыдущим, мы вытащим задом наперед весь путь. Ну и раз уж узел среды более сложен чем просто массив целых, в нём можно заодно хранить и ещё что-то полезное. Будем там заодно хранить номер передвигаемой плитки (т.е. число, которое при переходе от предыдущего, меняется позициями с восьмёркой). Напишем класс (будем всё писать на java), представляющий узел среды:

class Node
{
  	public int[] value;    //массив перестановок
	public Node  parent;   //предыдущий узел
	public int act;        //активная (перемещаемая) плитка
	Node() {value=null; parent=null; act=-1;}
}

В словесном описании алгоритм выглядит примерно так:

1. Создаем первый узел среды, значение которого установим в {0, 1, 2, 3, 4, 5, 6, 7, 8}, и помещаем его в волновой фронт и список узлов.

2. Обновляем волновой фронт. Для этого создаем новый изначально пустой волновой фронт, а затем для каждого элемента старого:

3. Получаем позицию восьмерки и список её соседей.

4. Для каждого соседа восьмерки создаем новый массив, в котором этот сосед и восьмерка меняются местами.

5. Если такой массив уже был, ничего не делаем. Если этот массив ещё не встречался, создаем новый узел, с этим массивом в качестве значения. В качестве предыдущего указываем узел из старого волнового фронта. И в качестве активной плитки — число, с которым восьмерка менялась местами. Включаем этот узел в список узлов и новый волновой фронт. Проверяем, не является ли полученный массив целевым. Если да, то успешное завершение.

6. Если новый волновой фронт пуст, не успешное завершение. Если не пуст, переходим к пункту 2.

Ниже приведена программа на java полностью решающая задачу. Не пинайте ногами, если коряво получилось, писал её по-быстрому. Кроме собственно волнового алгоритма, она ещё выводит картинки, показывающие ходы, и возникающие при этом позиции. Манипуляции с картинками довольно просты, и я их здесь не рассматриваю. Для рисования картинок ей нужен файл puzzle.png. Чтобы получить его, просто сохраните под этим именем первую картинку в статье.

Текст программы:

Hidden text

import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.image.BufferedImage;
import java.io.File;
import java.util.ArrayList;
import java.util.HashSet;
import javax.imageio.ImageIO;

public class Main 
{
	//Копирует плитку с номером p0 из исходного изображение img0 в позицию p1 изображения img1.
	//Если hl=true, плитка подсвечивается
	static void copy(int p0, BufferedImage img0, int p1, BufferedImage img1, boolean hl)
	{
		int ww=img0.getWidth()/3;
		int hh=img0.getHeight()/3;
		int y0=(p0/3)*hh;
		int x0=(p0%3)*ww;
		int y1=(p1/3)*hh;
		int x1=(p1%3)*ww;
		for(int i=0; i>16)&255)+d, g=((rgb>>8)&255)+d, b=(rgb&255)+d;
					if(r>255) r=255;
					if(g>255) g=255;
					if(b>255) b=255;
					rgb=(255<<24)+(r<<16)+(g<<8)+b;
					
				}
				img1.setRGB(x1+j, y1+i, rgb);
			}
		}
	}
	
	//Строит изображение img1 из исходного изображения img0 в соответствии с массивом перестановок плиток a.
	//hl - номер подсвеченной плитки.
	static void makeAll(int[] a, BufferedImage img0, BufferedImage img1, int hl)
	{
		for(int i=0; i field;   //Множество уже пройденных строк
	static ArrayList nodes;   //Массив узлов
	static ArrayList front;   //Фронт волны
	
	//Получает массив перестановок (поле value узла Node)
	//Выдает массив, нулевой элемент которого позиция числа 8, а остальные - соседи числа 8.
	static int[] getNeibours(int[] val)
	{
		int pos=0;
		for(int i=0; i8)) return null;
		int x=pos%3, y=pos/3;
		int n=0;
		int[] a=new int[6];
		a[n++]=pos;
		if(x-1 >= 0) a[n++]=pos-1;
		if(x+1 <  3) a[n++]=pos+1;
		if(y-1 >= 0) a[n++]=pos-3;
		if(y+1 <  3) a[n++]=pos+3;
		int[] b=new int[n];
		for(int i=0; i tmp=new ArrayList<>(); //новый волновой фронт
		for(int i=0; i extractPath()
	{
		ArrayList path=new ArrayList<>();
		Node nd=nodes.get(nodes.size()-1);
		int act=-1;
		do
		{
			Node nd1=nd.parent;
			int act1=nd.act;
			nd.act=act;
			path.add(nd);
			nd=nd1;
			act=act1;
		} while(nd != null);
		return path;
	}
	
	//Выводит одну суммарную картинку
	static void makeTotal()
	{
		try
		{
			BufferedImage img=ImageIO.read(new File("puzzle.png"));
			int ww=img.getWidth();
			int hh=img.getHeight();
			int type=img.getType();
			int gap=30; //промежуток между картинками
			BufferedImage img1=new BufferedImage(5*ww+4*gap, 4*hh+3*gap, type);
			Graphics2D gr=img1.createGraphics();
			gr.setPaint(new Color(255, 255, 255));
			gr.fillRect ( 0, 0, img1.getWidth(), img1.getHeight());
			
			int nn=1;
			int xx=0, yy=0;
			for(int i=0; i<4; i++)
			{
				xx=0;
				for(int j=0; j<5; j++)
				{
					String name="./solution/step_"+nn+".png";
					nn++;
					BufferedImage imgn=ImageIO.read(new File(name));
					int w=imgn.getWidth(), h=imgn.getHeight();
					for(int y=0; y();
		nodes=new ArrayList<>();
		front=new ArrayList<>();
		target="104635278";
		int[] a= new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8};
		Node nd0 = new Node();
		nd0.value=a;
		field.add(toString(a));
		nodes.add(nd0);
		front.add(nd0);
		int res=0;
		while(res==0) res=step();
		if(res==1) 
		{
			System.out.println("Puzzle solved. Now save pictures");
			ArrayList path=extractPath();
			for(int i=0; i