Python written BFS/A* with heuristic for higher levels. Python Version tested: Python 2.7.15+

Works:

In the Chess.py File change INITIAL_BORD & WINNING_BOARD accordingly.
Set SPEEDUP False / True.
Set SPEEDUP_EXP False / True.
Run.

SPEEDUP == True will usually solve the Game way faster, uses out of place heuristic. And is optimal.

SPEEDUP_EXP == True will use a non-admissible heuristic, solves 5x5-boards usually within seconds or less, but may be non-optimal.

SPEEDUP == SPEEDUP_EXP == False will solve the Game optimal, but will take longer (without heuristic).

For King levels (5x5) SPEEDUP == False will mostly consume too much memory, to be solvable, SPEEDUP == True or better: SPEEDUP_EXP == True will do the job.

SETTINGS:

Figures:

  Empty: 0      
  Not Moveable: -1
  Red: 1
  Blue: 2
  Golden: 3

Board is numerated in this fashion:

Setting BOARDS:

IMPORTANT!:

Goldens (3's) are set to 0 in the WINNING_BOARD!! As you can see in this Picture:

Example:

Output with SPEEDUP == False:

Output with SPEEDUP_EXP == True:

False returns the optimum, True a suboptimal solution, but way faster. Time depends on the machine.

The 3x3, 4x3, 4x4 boards are usually solved < 1 sec. (SPEEDUP == False and SPEEDUP_EXP == False)

The 5x4 boards can take several minutes. (SPEEDUP == False and SPEEDUP_EXP == False)

The 5x5 boards mostly won't be solved without SPEEDUP == True or SPEEDUP_EXP == True.

IMPORTANT!!::

Printed boards must be read from bottom to top.

Uses heapq module.