woodenpuzzle-cpp

A brute force algorithm to solve a 10x6 wooden puzzle

This program is a brute-force algorithm to solve a 10x6 puzzle that contains numerous available_pieces. Each piece is a different shape, but is limited to a dimension no bigger than 5x5.

The puzzle is solved once all holes or gaps on the board are filled with available_pieces. A piece cannot go over the boundary of the board, and no two available_pieces can overlap.

---

Building the program

All you need to build the program is to run make and the binary will be placed under the bin folder. If you choose to build the program with debugging symbols, run DEBUG=1 make instead.

---

Running the program

The program has four available options:

• -h: Displays the help menu
• -c: Continuously runs the algorithm until SIGTERM or SIGINT is received.
• -w: Writes solutions to a file. The file name is solutions.txt and is placed in the current directory.
• -p: Prints each step of the algorithm to the console.
• -t: Enables multi threading mode.
• -s: The starting piece to use. The default is Utah (0).
• -n: The number of threads to use. The default is 1. The executable is located under the bin folder, titled wooden_puzzle.

---

The available pieces

Utah

Col1	Col2
	U
U	U
U	U

Plus

Col1	Col2	Col3
	P
P	P	P
	P

T Piece #1

Col1	Col2	Col3
T	T	T
	T
	T

T Piece #2

Col1	Col2	Col3
2	2	2
	2
	2

M Piece

Col1	Col2	Col3
M	M
	M	M
		M

Long Z Piece

Col1	Col2	Col3	Col4	Col5
z	z
	z	z	z	z

Short T Piece

Col1	Col2	Col3	Col4	Col5
t	t	t	t	t
	t

Z Piece

Long Z Piece

Col1	Col2	Col3
Z	Z
	Z
	Z	Z

Awkward T Piece

Col1	Col2	Col3
		a
a	a	a
	a

L Piece

Col1	Col2
L
L
L
L	L

Long L Piece

Col1	Col2	Col3
B
B
B
B	B	B

I Piece

Col1
I
I
I
I
I

U Piece

Col1	Col2	Col3
u		u
u	u	u

A possible solution

Below is a solution generated by the program.

t	I	I	I	I	I	Z	a	u	u
t	t	U	U	Z	Z	Z	a	a	u
t	z	U	U	Z	M	a	a	u	u
t	z	T	U	P	M	M	B	B	B
z	z	T	P	P	P	M	M	L	B
z	T	T	T	P	L	L	L	L	B