Skip to content

Instantly share code, notes, and snippets.

@salamantos

salamantos/Пятнашки_A.cpp

Created March 13, 2018 19:04
Show Gist options
  • Save salamantos/d423917f16833905ea9ba850fe50b4f8 to your computer and use it in GitHub Desktop.
Save salamantos/d423917f16833905ea9ba850fe50b4f8 to your computer and use it in GitHub Desktop.
Download ZIP
Пятнашки
Raw
Пятнашки_A.cpp
#include <assert.h>
#include <fstream>
#include <queue>
#include <set>
#include <sstream>
#include <string>
using namespace std;
//const vector<int> goal = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0 }; // Положение фишек, до которого нужно дойти
const unsigned long long goal = 1147797409030816545; // Положение фишек, до которого нужно дойти
const vector<int> x = { 4,1,2,3,4,1,2,3,4,1,2,3,4,1,2,3 }; // Положение, в котором должны оказаться фишки
const vector<int> y = { 4,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4 };
const vector<int> maskX = { 1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4 };
const vector<int> maskY = { 1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4 };
const unsigned long long Masks[] = {
0x000000000000000F,
0x00000000000000F0,
0x0000000000000F00,
0x000000000000F000,
0x00000000000F0000,
0x0000000000F00000,
0x000000000F000000,
0x00000000F0000000,
0x0000000F00000000,
0x000000F000000000,
0x00000F0000000000,
0x0000F00000000000,
0x000F000000000000,
0x00F0000000000000,
0x0F00000000000000,
0xF000000000000000,
};
const unsigned long long AntiMasks[] = {
0xFFFFFFFFFFFFFFF0,
0xFFFFFFFFFFFFFF0F,
0xFFFFFFFFFFFFF0FF,
0xFFFFFFFFFFFF0FFF,
0xFFFFFFFFFFF0FFFF,
0xFFFFFFFFFF0FFFFF,
0xFFFFFFFFF0FFFFFF,
0xFFFFFFFF0FFFFFFF,
0xFFFFFFF0FFFFFFFF,
0xFFFFFF0FFFFFFFFF,
0xFFFFF0FFFFFFFFFF,
0xFFFF0FFFFFFFFFFF,
0xFFF0FFFFFFFFFFFF,
0xFF0FFFFFFFFFFFFF,
0xF0FFFFFFFFFFFFFF,
0x0FFFFFFFFFFFFFFF
};
const int maxQueueSize = 65;
const int truncateKoeff = 3;
const bool truncateQ = true;
struct CLastPos {
char pos; // Шаг, которым получена данная конфигурация
CLastPos* pointer;
CLastPos( char pos, CLastPos* pointer ) : pos( pos ), pointer( pointer ) {}
};
class CPosition {
public:
explicit CPosition( const std::string& source );
// Передвижение пустышки вверх, вниз, влево, вправо
CPosition inline Up() const;
CPosition inline Down() const;
CPosition inline Left() const;
CPosition inline Right() const;
vector<int> inline GetVector() const;
int GetNullPos() const { return nullPos; }
unsigned long long GetData() const { return data; }
int GetSteps() const { return steps; }
CLastPos* GetLastDir() const { return lastPosition; }
int prediction;
private:
int nullPos;
unsigned long long data; // 16 ячеек по 4 бита каждая.
int steps; // Число ходов, которое сделано для достижения данного состояния
CLastPos* lastPosition;
void inline setAt( int place, unsigned char value );
unsigned char inline getAt( int place ) const;
};
CPosition::CPosition( const string& source ) :
data( 0 ),
nullPos( 0 ),
steps( 0 ),
prediction( 0 ),
lastPosition( NULL )
{
//istringstream stringStream( source );
for (char i = 0; i < 16; ++i) {
unsigned short value = source[i];
//stringStream >> value;
setAt( i, static_cast<unsigned char>(value) );
if (value == 0) {
nullPos = i;
}
}
}
// Установка значения в некоторую позицию.
void inline CPosition::setAt( int place, unsigned char value )
{
data = (data & AntiMasks[place]) | (static_cast<long long>(value) << (place << 2));
}
// Получение того, что лежит в некоторой позиции.
unsigned char inline CPosition::getAt( int place ) const
{
return static_cast<unsigned char>((data & Masks[place]) >> (place << 2));
}
CPosition inline CPosition::Up() const
{
assert( nullPos >= 4 );
CPosition result( *this );
// Ставим пустышку выше.
result.setAt( nullPos - 4, 0 );
// Ставим то, что было выше, на то место, где была пустышка.
result.setAt( nullPos, getAt( nullPos - 4 ) );
result.nullPos -= 4;
result.lastPosition = new CLastPos( 'D', this->lastPosition );
result.steps++;
return result;
}
CPosition inline CPosition::Down() const
{
assert( nullPos <= 11 );
CPosition result( *this );
result.setAt( nullPos + 4, 0 );
result.setAt( nullPos, getAt( nullPos + 4 ) );
result.nullPos += 4;
result.lastPosition = new CLastPos( 'U', this->lastPosition );
result.steps++;
return result;
}
CPosition inline CPosition::Left() const
{
assert( nullPos != 0 && nullPos != 4 && nullPos != 8 && nullPos != 12 );
CPosition result( *this );
result.setAt( nullPos - 1, 0 );
result.setAt( nullPos, getAt( nullPos - 1 ) );
result.nullPos -= 1;
result.lastPosition = new CLastPos( 'R', this->lastPosition );
result.steps++;
return result;
}
CPosition inline CPosition::Right() const
{
assert( nullPos != 3 && nullPos != 7 && nullPos != 11 && nullPos != 15 );
CPosition result( *this );
result.setAt( nullPos + 1, 0 );
result.setAt( nullPos, getAt( nullPos + 1 ) );
result.nullPos += 1;
result.lastPosition = new CLastPos( 'L', this->lastPosition );
result.steps++;
return result;
}
vector<int> inline CPosition::GetVector() const
{
vector<int> res( 16, 0 );
for (int i = 0; i < 16; i++) {
res[i] = getAt( i );
}
return res;
}
class Compare {
public:
bool operator()( const CPosition& left, const CPosition& right )
{
return left.prediction > right.prediction;
}
};
bool check_solvability( const CPosition& board )
{
vector<int> numbers = board.GetVector();
bool chetn = true;
for (size_t i = 0; i < 16; ++i) {
if (numbers[i] == 0) continue;
for (size_t j = i; j < 16; ++j) {
if (numbers[j] == 0) continue;
if (numbers[i] < numbers[j]) {
chetn = !chetn;
}
}
}
int nullPos = board.GetNullPos();
bool line = false; // Четность строки, где стоит пустышка. Нумерация с 1
if ((nullPos >= 4 && nullPos <= 7) || (nullPos >= 12 && nullPos <= 15)) {
line = true;
}
return ((!chetn&&line) || (chetn && !line)); // xor
}
int inline heuristic( vector<int>& boardVector )
{
// Manhattan distance
int res = 0;
for (size_t i = 0; i < 16; i++) {
if (boardVector[i] != 0) {
res += abs( x[boardVector[i]] - maskX[i] );
res += abs( y[boardVector[i]] - maskY[i] );
}
}
// Linear conflict
// Перебираем строки
for (int i = 0; i < 4; ++i) {
// Перебираем первые 3 элемента в строке
for (int j = 0; j < 3; ++j) {
// Если элемент в решенном состоянии должен быть в этой строке
int tile1 = boardVector[4 * i + j];
if(tile1==0) continue;
if (tile1 >= 4*i + 1 && tile1 <= 4*i + 4) {
// Перебираем элементы правее него
for (int k = j + 1; k < 4; ++k) {
int tile2 = boardVector[4 * i + k];if(tile2==0) continue;
if (tile2 >= 4 * i + 1 && tile2 <= 4 * i + 4 && tile2 < tile1) {
res += 2;
}
}
}
}
}
// Перебираем столбцы
for (int i = 0; i < 4; ++i) {
// Перебираем первые 3 элемента в столбце
for (int j = 0; j < 3; ++j) {
// Если элемент в решенном состоянии должен быть в этом столбце
int tile1 = boardVector[4 * j + i];if(tile1==0) continue;
if ((tile1 - 1) % 4 == i) {
// Перебираем элементы ниже него
for (int k = j + 1; k < 4; ++k) {
int tile2 = boardVector[4 * k + i];if(tile2==0) continue;
if ((tile2 - 1) % 4 == i && tile2 < tile1) {
res += 2;
}
}
}
}
}
//int ret = 0;
//// строка
//int row[] = { 3, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3 };
//// столбец
//int column[] = { 3, 0 ,1 ,2, 3, 0 ,1 ,2, 3, 0 ,1 ,2, 3, 0 ,1 ,2 };
//// строки
//for (int i = 0; i < 4; i++)
// for (int j = 0; j < 4; j++) {
// int currNum = posTable[i][j];
// for (int k = j + 1; k < 4; k++) {
// if (row[posTable[i][k]] == row[posTable[i][j]] && column[posTable[i][k]] < column[posTable[i][j]])
// ret += 2;
// }
// }
//// столбца
//for (int j = 0; j < 4; j++)
// for (int i = 0; i < 4; i++) {
// int currNum = posTable[i][j];
// for (int k = i + 1; k < 4; k++) {
// if (column[posTable[k][j]] == column[posTable[i][j]] && row[posTable[k][j]] < row[posTable[i][j]])
// ret += 2;
// }
// }
//return ret;
return res;
}
template <typename TQueue>
void inline finderStep( set<unsigned long long>& prev_states, TQueue& q, CPosition& board )
{
// Пытаемся сделать шаг в одном из направлений, запоминаем путь
char last_dir = 0;
if (board.GetLastDir() != NULL)
last_dir = board.GetLastDir()->pos;
int nullPos = board.GetNullPos();
// Up
if (last_dir != 'U' && nullPos >= 4) {
CPosition tmpBoard = board.Up();
if (prev_states.find( tmpBoard.GetData() ) == prev_states.end() || tmpBoard.GetSteps() + 1 < board.GetSteps()) {
vector<int> qwerty = tmpBoard.GetVector();
tmpBoard.prediction = heuristic( qwerty );
q.push( tmpBoard );
prev_states.insert( tmpBoard.GetData() );
}
}
// Down
if (last_dir != 'D' && nullPos <= 11) {
CPosition tmpBoard = board.Down();
if (prev_states.find( tmpBoard.GetData() ) == prev_states.end() || tmpBoard.GetSteps() + 1 < board.GetSteps()) {
vector<int> qwerty = tmpBoard.GetVector();
tmpBoard.prediction = heuristic( qwerty );
q.push( tmpBoard );
prev_states.insert( tmpBoard.GetData() );
}
}
// Left
if (last_dir != 'L' && nullPos != 0 && nullPos != 4 && nullPos != 8 && nullPos != 12) {
CPosition tmpBoard = board.Left();
if (prev_states.find( tmpBoard.GetData() ) == prev_states.end() || tmpBoard.GetSteps() + 1 < board.GetSteps()) {
vector<int> qwerty = tmpBoard.GetVector();
tmpBoard.prediction = heuristic( qwerty );
q.push( tmpBoard );
prev_states.insert( tmpBoard.GetData() );
}
}
// Right
if (last_dir != 'R' && nullPos != 3 && nullPos != 7 && nullPos != 11 && nullPos != 15) {
CPosition tmpBoard = board.Right();
if (prev_states.find( tmpBoard.GetData() ) == prev_states.end() || tmpBoard.GetSteps() + 1 < board.GetSteps()) {
vector<int> qwerty = tmpBoard.GetVector();
tmpBoard.prediction = heuristic( qwerty );
q.push( tmpBoard );
prev_states.insert( tmpBoard.GetData() );
}
}
}
template <typename TQueue>
void inline truncateQueue( TQueue& q )
{
priority_queue<CPosition, vector<CPosition>, Compare> tempQ;
int newSize = maxQueueSize / truncateKoeff;
for (size_t i = 0; i < newSize; i++) {
CPosition tempElem = q.top();
q.pop();
tempQ.push( tempElem );
}
q = tempQ;
}
void findSolution( CPosition& givenBoard, int& steps, string& solution )
{
set<unsigned long long> prev_states;
priority_queue<CPosition, vector<CPosition>, Compare> q;
prev_states.insert( givenBoard.GetData() );
q.push( givenBoard );
while (!q.empty()) {
CPosition board = q.top();
q.pop();
if (board.GetData() == goal) {
steps = board.GetSteps();
string invertedSolution = "";
CLastPos* lastDir = board.GetLastDir();
for (size_t i = 0; i < steps; i++) {
invertedSolution += lastDir->pos;
lastDir = lastDir->pointer;
}
for (size_t i = 0; i < steps; i++) {
solution += invertedSolution[steps - i - 1];
}
return;
}
// Пытаемся сделать шаг в одном из направлений, запоминаем путь
finderStep( prev_states, q, board );
// Для ускорения удаляем элементы с наибольшей удаленностью
if ( truncateQ && q.size() > maxQueueSize) {
truncateQueue( q );
}
}
}
int main()
{
ifstream fin( "input.txt" );
string state = "";
for (size_t i = 1; i <= 16; i++) {
int number = 0;
fin >> number;
state += (char) number;
}
fin.close();
CPosition board( state );
vector<int> t = board.GetVector();
int steps = 1000; // Минимальное количество ходов в решении
string solution = ""; // Последовательность ходов
if (!check_solvability( board )) {
ofstream fout( "output.txt" );
fout << -1;
fout.close();
return 0;
}
findSolution( board, steps, solution );
ofstream fout( "output.txt" );
fout << steps;
fout << '\n';
fout << solution.c_str();
fout.close();
return 0;
}
Raw
Пятнашки_B.cpp
/*
Оптимальное решение пятнашек с использованием IDA*
*/
#include <assert.h>
#include <fstream>
#include <queue>
#include <set>
#include <sstream>
#include <string>
using namespace std;
#define FOUND 146
const unsigned long long goal = 1147797409030816545; // Положение фишек, до которого нужно дойти
const vector<int> x = { 4,1,2,3,4,1,2,3,4,1,2,3,4,1,2,3 }; // Положение, в котором должны оказаться фишки
const vector<int> y = { 4,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4 };
const vector<int> maskX = { 1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4 };
const vector<int> maskY = { 1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4 };
const unsigned long long Masks[] = {
0x000000000000000F,
0x00000000000000F0,
0x0000000000000F00,
0x000000000000F000,
0x00000000000F0000,
0x0000000000F00000,
0x000000000F000000,
0x00000000F0000000,
0x0000000F00000000,
0x000000F000000000,
0x00000F0000000000,
0x0000F00000000000,
0x000F000000000000,
0x00F0000000000000,
0x0F00000000000000,
0xF000000000000000,
};
const unsigned long long AntiMasks[] = {
0xFFFFFFFFFFFFFFF0,
0xFFFFFFFFFFFFFF0F,
0xFFFFFFFFFFFFF0FF,
0xFFFFFFFFFFFF0FFF,
0xFFFFFFFFFFF0FFFF,
0xFFFFFFFFFF0FFFFF,
0xFFFFFFFFF0FFFFFF,
0xFFFFFFFF0FFFFFFF,
0xFFFFFFF0FFFFFFFF,
0xFFFFFF0FFFFFFFFF,
0xFFFFF0FFFFFFFFFF,
0xFFFF0FFFFFFFFFFF,
0xFFF0FFFFFFFFFFFF,
0xFF0FFFFFFFFFFFFF,
0xF0FFFFFFFFFFFFFF,
0x0FFFFFFFFFFFFFFF
};
class CPosition {
public:
explicit CPosition( const std::string& source );
// Передвижение пустышки вверх, вниз, влево, вправо
CPosition inline Up() const;
CPosition inline Down() const;
CPosition inline Left() const;
CPosition inline Right() const;
vector<int> inline GetVector() const;
int GetNullPos() const { return nullPos; }
unsigned long long GetData() const { return data; }
int GetSteps() const { return steps; }
char GetLastDir() const { return lastPosition; }
int prediction;
private:
int nullPos;
unsigned long long data; // 16 ячеек по 4 бита каждая.
int steps; // Число ходов, которое сделано для достижения данного состояния
char lastPosition;
void inline setAt( int place, unsigned char value );
unsigned char inline getAt( int place ) const;
};
CPosition::CPosition( const string& source ) :
data( 0 ),
nullPos( 0 ),
steps( 0 ),
prediction( 0 ),
lastPosition( 0 )
{
//istringstream stringStream( source );
for (char i = 0; i < 16; ++i) {
unsigned short value = source[i];
//stringStream >> value;
setAt( i, static_cast<unsigned char>(value) );
if (value == 0) {
nullPos = i;
}
}
}
// Установка значения в некоторую позицию.
void inline CPosition::setAt( int place, unsigned char value )
{
data = (data & AntiMasks[place]) | (static_cast<long long>(value) << (place << 2));
}
// Получение того, что лежит в некоторой позиции.
unsigned char inline CPosition::getAt( int place ) const
{
return static_cast<unsigned char>((data & Masks[place]) >> (place << 2));
}
CPosition inline CPosition::Up() const
{
assert( nullPos >= 4 );
CPosition result( *this );
// Ставим пустышку выше.
result.setAt( nullPos - 4, 0 );
// Ставим то, что было выше, на то место, где была пустышка.
result.setAt( nullPos, getAt( nullPos - 4 ) );
result.nullPos -= 4;
result.lastPosition = 'D';
result.steps++;
return result;
}
CPosition inline CPosition::Down() const
{
assert( nullPos <= 11 );
CPosition result( *this );
result.setAt( nullPos + 4, 0 );
result.setAt( nullPos, getAt( nullPos + 4 ) );
result.nullPos += 4;
result.lastPosition = 'U';
result.steps++;
return result;
}
CPosition inline CPosition::Left() const
{
assert( nullPos != 0 && nullPos != 4 && nullPos != 8 && nullPos != 12 );
CPosition result( *this );
result.setAt( nullPos - 1, 0 );
result.setAt( nullPos, getAt( nullPos - 1 ) );
result.nullPos -= 1;
result.lastPosition = 'R';
result.steps++;
return result;
}
CPosition inline CPosition::Right() const
{
assert( nullPos != 3 && nullPos != 7 && nullPos != 11 && nullPos != 15 );
CPosition result( *this );
result.setAt( nullPos + 1, 0 );
result.setAt( nullPos, getAt( nullPos + 1 ) );
result.nullPos += 1;
result.lastPosition = 'L';
result.steps++;
return result;
}
vector<int> inline CPosition::GetVector() const
{
vector<int> res( 16, 0 );
for (int i = 0; i < 16; i++) {
res[i] = getAt( i );
}
return res;
}
class Compare {
public:
bool operator()( const CPosition& left, const CPosition& right )
{
return left.prediction > right.prediction;
}
};
bool check_solvability( const CPosition& board )
{
vector<int> numbers = board.GetVector();
bool chetn = true;
for (size_t i = 0; i < 16; ++i) {
if (numbers[i] == 0) continue;
for (size_t j = i; j < 16; ++j) {
if (numbers[j] == 0) continue;
if (numbers[i] < numbers[j]) {
chetn = !chetn;
}
}
}
int nullPos = board.GetNullPos();
bool line = false; // Четность строки, где стоит пустышка. Нумерация с 1
if ((nullPos >= 4 && nullPos <= 7) || (nullPos >= 12 && nullPos <= 15)) {
line = true;
}
return ((!chetn&&line) || (chetn && !line)); // xor
}
int inline heuristic( vector<int>& boardVector )
{
// Manhattan distance
int res = 0;
for (size_t i = 0; i < 16; i++) {
if (boardVector[i] != 0) {
res += abs( x[boardVector[i]] - maskX[i] );
res += abs( y[boardVector[i]] - maskY[i] );
}
}
// Linear conflict
// Перебираем строки
for (int i = 0; i < 4; ++i) {
// Перебираем первые 3 элемента в строке
for (int j = 0; j < 3; ++j) {
// Если элемент в решенном состоянии должен быть в этой строке
int tile1 = boardVector[4 * i + j];
if (tile1 >= 4 * i + 1 && tile1 <= 4 * i + 4) {
// Перебираем элементы правее него
for (int k = j + 1; k < 4; ++k) {
int tile2 = boardVector[4 * i + k];
if (tile2 >= 4 * i + 1 && tile2 <= 4 * i + 4 && tile2 < tile1) {
res += 2;
}
}
}
}
}
// Перебираем столбцы
for (int i = 0; i < 4; ++i) {
// Перебираем первые 3 элемента в столбце
for (int j = 0; j < 3; ++j) {
// Если элемент в решенном состоянии должен быть в этом столбце
int tile1 = boardVector[4 * j + i];
if ((tile1 - 1) % 4 == i) {
// Перебираем элементы ниже него
for (int k = j + 1; k < 4; ++k) {
int tile2 = boardVector[4 * k + i];
if ((tile2 - 1) % 4 == i && tile2 < tile1) {
res += 2;
}
}
}
}
}
return res;
}
int search( CPosition& board, int madeSteps, int const threshold, string& invertedSolution )
{
vector<int> boardVector = board.GetVector();
int prediction = madeSteps + heuristic( boardVector );
if (prediction > threshold)
return prediction;
if (board.GetData() == goal) {
invertedSolution = board.GetLastDir();
return FOUND;
}
int min = 1000;
char last_dir = 0;
if (board.GetLastDir() != 0)
last_dir = board.GetLastDir();
int nullPos = board.GetNullPos();
// Down
if (last_dir != 'D' && nullPos <= 11) {
CPosition tmpBoard = board.Down();
int res = search( tmpBoard, madeSteps + 1, threshold, invertedSolution );
if (res == FOUND) {
if (board.GetLastDir() != 0)
invertedSolution += board.GetLastDir();
return FOUND;
}
if (res < min)
min = res;
}
// Left
if (last_dir != 'L' && nullPos != 0 && nullPos != 4 && nullPos != 8 && nullPos != 12) {
CPosition tmpBoard = board.Left();
int res = search( tmpBoard, madeSteps + 1, threshold, invertedSolution );
if (res == FOUND) {
if (board.GetLastDir() != 0)
invertedSolution += board.GetLastDir();
return FOUND;
}
if (res < min)
min = res;
}
// Up
if (last_dir != 'U' && nullPos >= 4) {
CPosition tmpBoard = board.Up();
int res = search( tmpBoard, madeSteps + 1, threshold, invertedSolution );
if (res == FOUND) {
if (board.GetLastDir() != 0)
invertedSolution += board.GetLastDir();
return FOUND;
}
if (res < min)
min = res;
}
// Right
if (last_dir != 'R' && nullPos != 3 && nullPos != 7 && nullPos != 11 && nullPos != 15) {
CPosition tmpBoard = board.Right();
int res = search( tmpBoard, madeSteps + 1, threshold, invertedSolution );
if (res == FOUND) {
if (board.GetLastDir() != 0)
invertedSolution += board.GetLastDir();
return FOUND;
}
if (res < min)
min = res;
}
return min;
}
void findSolution( CPosition& givenBoard, int& steps, string& solution )
{
vector<int> givenBoardVector = givenBoard.GetVector();
int threshold = heuristic( givenBoardVector );
string invertedSolution;
while (true) {
int stepRes = search( givenBoard, 0, threshold, invertedSolution );
if (stepRes == FOUND) {
steps = threshold;
solution = "";
for (size_t i = 0; i < steps; i++) {
solution += invertedSolution[steps - i - 1];
}
return;
} else {
threshold = stepRes;
}
}
}
int main()
{
ifstream fin( "input.txt" );
string state = "";
for (size_t i = 1; i <= 16; i++) {
int number = 0;
fin >> number;
state += (char) number;
}
fin.close();
CPosition board( state );
vector<int> t = board.GetVector();
int steps = 1000; // Минимальное количество ходов в решении
string solution = ""; // Последовательность ходов
if (!check_solvability( board )) {
ofstream fout( "output.txt" );
fout << -1;
fout.close();
return 0;
}
findSolution( board, steps, solution );
ofstream fout( "output.txt" );
fout << steps;
fout << '\n';
fout << solution.c_str();
fout.close();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment