Skip to content

Instantly share code, notes, and snippets.

@koyo-miyamura
Last active January 20, 2020 03:52
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save koyo-miyamura/665e1ab0fc6328fb86d50fc4722916e9 to your computer and use it in GitHub Desktop.
Save koyo-miyamura/665e1ab0fc6328fb86d50fc4722916e9 to your computer and use it in GitHub Desktop.
8パズルの最短手を求めるプログラム
/*
8puzzle.cpp : 8パズルの最短手を求めるプログラム
author : Koyo Miyamura
*/
#include <stdio.h>
#include <iostream>
#include <queue>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#define N_C 362880 //9! = 362880
class Puzzle{
private:
int p[3][3];
int step_opt;
int check_board[N_C];
typedef struct{
int p_b[3][3];
int exclude;
} Board;
// This changes board state into number
int board_number(Board board){
int num = 0;
int i,j =0;
int tmp[9];
const int Factorial[9] = {40320, 5040, 720, 120, 24, 6, 2, 1, 0};
for(i = 0; i <= 2; i++){
for(j = 0; j <= 2; j++){
tmp[(3 * i) + j] = board.p_b[i][j];
}
}
for(i = 0; i < 8 ; i++){
num += tmp[i] * Factorial[i];
for(j = i + 1; j <= 8; j++){
if(tmp[i] < tmp[j]) tmp[j]--;
}
}
return num;
}
// Used for optend()
int endcheck_for_opt(int p2[3][3]){
int i,j;
int p_e[3][3];
int flag = 1;
p_e[0][0] = 1; p_e[0][1] = 2; p_e[0][2] = 3;
p_e[1][0] = 4; p_e[1][1] = 5; p_e[1][2] = 6;
p_e[2][0] = 7; p_e[2][1] = 8; p_e[2][2] = 0;
for(i = 0; i <= 2 ; i++){
for(j = 0; j <= 2 ; j++){
if(p2[i][j] != p_e[i][j]) flag = 0;
}
}
return flag;
}
// Used for optend()
std::queue<int> next_q(int p2[3][3], int exclude){
std::queue<int> q;
int i, j;
int null_i, null_j;
for(i = 0; i <= 2 ; i++){
for(j = 0; j <= 2 ; j++){
if(p2[i][j] == 0){
null_i = i;
null_j = j;
}
}
}
for(i = 0; i <= 2 ; i++){
for(j = 0; j <= 2 ; j++){
if( ((((i + 1) == null_i) || ((i - 1) == null_i)) && (j == null_j))
|| ((((j + 1) == null_j) || ((j - 1) == null_j)) && (i == null_i)) ){
if(p2[i][j] != exclude){
q.push(p2[i][j]);
}
}
}
}
return q;
}
// Used for optend()
void swap_for_opt(int num, int p2[3][3]){
int i, j;
int n_i, n_j, null_i, null_j;
for(i = 0; i <= 2 ; i++){
for(j = 0; j <= 2 ; j++){
if(p2[i][j] == num){
n_i = i;
n_j = j;
}
else if(p2[i][j] == 0){
null_i = i;
null_j = j;
}
}
}
p2[null_i][null_j] = num;
p2[n_i][n_j] = 0;
return;
}
// Return opt step number for input board
int optend(int step, Board *board, int n_board){
std::queue<int> q;
int i, j, k, num;
int board_num;
int result;
int q_num = 0;
Board *board_new;
board_new = (Board *)malloc(sizeof(Board) * 3);
std::cout << step << "手目" << std::endl;
std::cout << "探索数:" << n_board << std::endl;
if(step == 1){
if(endcheck_for_opt(board[0].p_b) == 1){
return 0;
}
}
for(i = 0; i < n_board; i++){
board_num = board_number(board[i]);
if(check_board[board_num] == 0){
check_board[board_num] = 1;
q = next_q(board[i].p_b, board[i].exclude);
board_new = (Board *)realloc(board_new, sizeof(Board) * (q.size() + q_num));
while(q.empty() != 1){
for(j = 0; j <= 2; j++){
for(k = 0; k <= 2; k++){
board_new[q_num].p_b[j][k] = board[i].p_b[j][k];
}
}
num = q.front();
board_new[q_num].exclude = num;
q.pop();
swap_for_opt(num, board_new[q_num].p_b);
if(endcheck_for_opt(board_new[q_num].p_b) == 1){
free(board_new);
return step;
}
q_num ++;
}
}
}
//recursive call
result = optend(step + 1, board_new, q_num);
free(board_new);
return result;
}
public:
//Constructor
Puzzle(){
int i;
for(i = 0; i < N_C ; i++) check_board[i] = 0;
//------------ここに最短手を求めたい8パズルの初期状態を入力-------------
// 最短25手
p[0][0] = 8; p[0][1] = 1; p[0][2] = 7;
p[1][0] = 6; p[1][1] = 3; p[1][2] = 4;
p[2][0] = 2; p[2][1] = 0; p[2][2] = 5;
/*
// 最短31手
p[0][0] = 8; p[0][1] = 6; p[0][2] = 7;
p[1][0] = 2; p[1][1] = 5; p[1][2] = 4;
p[2][0] = 3; p[2][1] = 0; p[2][2] = 1;
/*
// 最短18回
p[0][0] = 1; p[0][1] = 4; p[0][2] = 3;
p[1][0] = 7; p[1][1] = 2; p[1][2] = 6;
p[2][0] = 8; p[2][1] = 5; p[2][2] = 0;
*/
/*
// 最短1回
p[0][0] = 1; p[0][1] = 2; p[0][2] = 3;
p[1][0] = 4; p[1][1] = 5; p[1][2] = 6;
p[2][0] = 7; p[2][1] = 0; p[2][2] = 8;
*/
}
//------------------------------------------------------------
void print(){
int i, j;
printf("------------------\n");
for(i = 0; i <= 2 ; i++){
for(j = 0; j <= 2 ; j++){
if(p[i][j] != 0){
printf("%d \t", p[i][j]);
}
else{
printf(" \t");
}
}
printf("\n");
}
printf("------------------\n");
return;
}
//-----getter,setter-----
int Getoptstep(){
int i, j;
Board p_board[1];
for(i = 0; i <= 2 ; i++){
for(j = 0; j <= 2 ; j++){
p_board[0].p_b[i][j] = p[i][j];
}
}
p_board[0].exclude = 10;//0~8以外の整数であればいい
step_opt = optend(1, p_board, 1);
return step_opt;
}
};
int main(){
Puzzle pz;
std::cout << "初期状態" << std::endl;
pz.print();
std::cout << "最短の手数は" << pz.Getoptstep() << "" << std::endl;
return 0;
}
@koyo-miyamura
Copy link
Author

koyo-miyamura commented Oct 20, 2017

8パズルの最短手を求めるプログラム

8パズルについては以下が参考になります
http://www.geocities.jp/m_hiroi/puzzle/eight.html

プログラム中のp[3][3]を書き換えることで任意の初期値について解ける

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment