• We've upgraded our forums. Please post any issues/requests in this thread.

N-Puzzle Solvability

Joined
Aug 10, 2007
Messages
4,059 (1.07/day)
Likes
1,123
Location
Geneva, FL, USA
Processor Intel i5-6600
Motherboard ASRock H170M-ITX
Cooling Cooler Master Geminii S524
Memory G.Skill DDR4-2133 16GB (8GB x 2)
Video Card(s) Gigabyte R9-380X 4GB
Storage Samsung 950 EVO 250GB (mSATA)
Display(s) LG 29UM69G-B 2560x1080 IPS
Case Lian Li PC-Q25
Audio Device(s) Realtek ALC892
Power Supply Seasonic SS-460FL2
Mouse Logitech G700s
Keyboard Logitech G110
Software Windows 10 Pro
#1
With all the talk about n-puzzle, I wanted to start playing around with a PHP implementation. I've gotten a solver in place, but it only solves it some of the time. Want to get my validator looked at to see if I understood the parity calculation correctly. If it looks sound, then I know the problem is later in the code.

- I'm using explanation given here about how to calculate parity.

- "total" is considered the space square.

- While permutations parity is odd, reshuffle the order until even parity is achieved.

- Loop through the range and for each square, test if value is greater than value of squares further in the sequence. If so, increment the counter.

PHP:
$tall = 3;
$wide = 3;

$total = $tall * $wide;

$range = range(1, $total);

do {

	shuffle($range);

	$permutations = 0;
	for ( $i = 0; $i < ($total - 1); ++$i ) {
		for ( $j = ($i + 1); $j < $total; ++$j ) {
			if ( $range[$i] > $range[$j] ) {
				++$permutations;
			}
		}
	}

} while ( $permutations & 1 );

//use validated range for board
 

Kreij

Senior Monkey Moderator
Staff member
Joined
Feb 6, 2007
Messages
13,817 (3.49/day)
Likes
5,524
Location
Cheeseland (Wisconsin, USA)
Processor Intel Core 2 Quad QX9650 Extreme @ 3.0 GHz
Motherboard Asus Rampage Formula
Cooling ZeroTherm Nirvana NV120 Premium
Memory 8GB (4 x 2GB) Corsair Dominator PC2-8500
Video Card(s) 2 x Sapphire Radeon HD6970
Storage 2 x Seagate Barracuda 320GB in RAID 0
Display(s) Dell 3007WFP 30" LCD (2560 x 1600)
Case Thermaltake Armor w/ 250mm Side Fan
Audio Device(s) SupremeFX 8ch Audio
Power Supply Thermaltake Toughpower 750W Modular
Software Win8 Pro x64 / Cat 12.10
#2
The validator looks sound to me.
It should never exit the do loop when the value of $permutations is odd.

Disclaimer : I could be wrong.
 

FordGT90Concept

"I go fast!1!11!1!"
Joined
Oct 13, 2008
Messages
20,919 (6.24/day)
Likes
10,017
Location
IA, USA
System Name BY-2015
Processor Intel Core i7-6700K (4 x 4.00 GHz) w/ HT and Turbo on
Motherboard MSI Z170A GAMING M7
Cooling Scythe Kotetsu
Memory 2 x Kingston HyperX DDR4-2133 8 GiB
Video Card(s) PowerColor PCS+ 390 8 GiB DVI + HDMI
Storage Crucial MX300 275 GB, Seagate 6 TB 7200 RPM
Display(s) Samsung SyncMaster T240 24" LCD (1920x1200 HDMI) + Samsung SyncMaster 906BW 19" LCD (1440x900 DVI)
Case Coolermaster HAF 932 w/ USB 3.0 5.25" bay
Audio Device(s) Realtek Onboard, Micca OriGen+
Power Supply Enermax Platimax 850w
Mouse SteelSeries Sensei RAW
Keyboard Tesoro Excalibur
Software Windows 10 Pro 64-bit
Benchmark Scores Faster than the tortoise; slower than the hare.
#3
Could try $permutations % 2 instead. It would return 0 on even, something else on everything else.
 
Joined
Aug 10, 2007
Messages
4,059 (1.07/day)
Likes
1,123
Location
Geneva, FL, USA
Processor Intel i5-6600
Motherboard ASRock H170M-ITX
Cooling Cooler Master Geminii S524
Memory G.Skill DDR4-2133 16GB (8GB x 2)
Video Card(s) Gigabyte R9-380X 4GB
Storage Samsung 950 EVO 250GB (mSATA)
Display(s) LG 29UM69G-B 2560x1080 IPS
Case Lian Li PC-Q25
Audio Device(s) Realtek ALC892
Power Supply Seasonic SS-460FL2
Mouse Logitech G700s
Keyboard Logitech G110
Software Windows 10 Pro
#4
Good disclaimer Kriej :)

So far the numbers it comes up with are even {10, 12, 14, ...} so from that perspective it works.

Expanding on my method, I wanted to do n-puzzle the worst way possible: random moves. AKA give the puzzle to a monkey (a monkey that can do ~300,000 moves/second). When they do get solved, it's always between .5 and 2 seconds. Otherwise, the script can run for 10 minutes and not get an answer. I suppose it's possible when talking about randomness, but I should be getting times in between 2 seconds and 10 minutes, right?

OH... to narrow down the problem, I could try validating the board after every move to make sure it's still solvable.

(10 minutes later)

Hmm, still getting "solves" in a short period of time or not at all. I'll give the code a look-over in the morning.
 

Kreij

Senior Monkey Moderator
Staff member
Joined
Feb 6, 2007
Messages
13,817 (3.49/day)
Likes
5,524
Location
Cheeseland (Wisconsin, USA)
Processor Intel Core 2 Quad QX9650 Extreme @ 3.0 GHz
Motherboard Asus Rampage Formula
Cooling ZeroTherm Nirvana NV120 Premium
Memory 8GB (4 x 2GB) Corsair Dominator PC2-8500
Video Card(s) 2 x Sapphire Radeon HD6970
Storage 2 x Seagate Barracuda 320GB in RAID 0
Display(s) Dell 3007WFP 30" LCD (2560 x 1600)
Case Thermaltake Armor w/ 250mm Side Fan
Audio Device(s) SupremeFX 8ch Audio
Power Supply Thermaltake Toughpower 750W Modular
Software Win8 Pro x64 / Cat 12.10
#5
If the state of the board begins in a solvable manner, random movement should not produce an unsolvable result. You may have to backtrack on the moves, but it should always be solvable.
After you start to solve the puzzle from a solvable solution, what determines (or stops) the code from completing it? If you are using the same criteria as a starting state (the validity test), and not considering that the puzzle could be backtracked, then I suppose it is possible the program would determine that it was impossible.

Interesting take on it, Jizzler. :toast:
 
Joined
Aug 10, 2007
Messages
4,059 (1.07/day)
Likes
1,123
Location
Geneva, FL, USA
Processor Intel i5-6600
Motherboard ASRock H170M-ITX
Cooling Cooler Master Geminii S524
Memory G.Skill DDR4-2133 16GB (8GB x 2)
Video Card(s) Gigabyte R9-380X 4GB
Storage Samsung 950 EVO 250GB (mSATA)
Display(s) LG 29UM69G-B 2560x1080 IPS
Case Lian Li PC-Q25
Audio Device(s) Realtek ALC892
Power Supply Seasonic SS-460FL2
Mouse Logitech G700s
Keyboard Logitech G110
Software Windows 10 Pro
#6
Right, just wanted to make sure that my code was handling the movements correctly. It seems to be doing that. I've outputted samples and watched it shift values. That, and the validator seems to agree that no incorrect movements are happening (at least no moves that would make the board unsolvable).

n-puzzle-sample.png

(Click: y, x)

In in each loop it's randomly choosing one of the four possible squares to "click" then shifting the number(s) from that point towards the space.

The goal state is reached when the board is in order, starting with 1 in the top-left corner and 9(space) in the bottom-right.
 
Last edited:

Kreij

Senior Monkey Moderator
Staff member
Joined
Feb 6, 2007
Messages
13,817 (3.49/day)
Likes
5,524
Location
Cheeseland (Wisconsin, USA)
Processor Intel Core 2 Quad QX9650 Extreme @ 3.0 GHz
Motherboard Asus Rampage Formula
Cooling ZeroTherm Nirvana NV120 Premium
Memory 8GB (4 x 2GB) Corsair Dominator PC2-8500
Video Card(s) 2 x Sapphire Radeon HD6970
Storage 2 x Seagate Barracuda 320GB in RAID 0
Display(s) Dell 3007WFP 30" LCD (2560 x 1600)
Case Thermaltake Armor w/ 250mm Side Fan
Audio Device(s) SupremeFX 8ch Audio
Power Supply Thermaltake Toughpower 750W Modular
Software Win8 Pro x64 / Cat 12.10
#7
How's this going, Jizz?
What you are doing is really interesting (although crazily inefficient :D).
 
Joined
Aug 10, 2007
Messages
4,059 (1.07/day)
Likes
1,123
Location
Geneva, FL, USA
Processor Intel i5-6600
Motherboard ASRock H170M-ITX
Cooling Cooler Master Geminii S524
Memory G.Skill DDR4-2133 16GB (8GB x 2)
Video Card(s) Gigabyte R9-380X 4GB
Storage Samsung 950 EVO 250GB (mSATA)
Display(s) LG 29UM69G-B 2560x1080 IPS
Case Lian Li PC-Q25
Audio Device(s) Realtek ALC892
Power Supply Seasonic SS-460FL2
Mouse Logitech G700s
Keyboard Logitech G110
Software Windows 10 Pro
#8
Didn't have much time to look it over yesterday, but did alter it to be able to loop X number of times.

Code:
C:\php>php puzzle.php 20
Time: 0.394s    Moves: 83998
Time: 1.102s    Moves: 236531
Time: 60.000s   Moves: 12626534
Time: 60.000s   Moves: 12811238
Time: 1.034s    Moves: 215050
Time: 60.000s   Moves: 12276046
Time: 60.000s   Moves: 12754828
Time: 2.386s    Moves: 510520
Time: 1.234s    Moves: 263973
Time: 60.000s   Moves: 12806750
Time: 0.346s    Moves: 73623
Time: 1.000s    Moves: 210736
Time: 60.000s   Moves: 12830742
Time: 1.515s    Moves: 325494
Time: 60.000s   Moves: 12602517
Time: 60.000s   Moves: 12329020
Time: 60.000s   Moves: 12433728
Time: 60.000s   Moves: 12634548
Time: 1.552s    Moves: 332954
Uh huh... timed out 10 of 20 runs, and half of all sequences are unsolvable. There might be something to that! :laugh:

Either the parity calculation I linked to was wrong or I implemented it incorrectly. Either way, going to look for another way to do it. Definitely need that working before going on to 4x4 or greater sized puzzles.
 
Joined
Aug 10, 2007
Messages
4,059 (1.07/day)
Likes
1,123
Location
Geneva, FL, USA
Processor Intel i5-6600
Motherboard ASRock H170M-ITX
Cooling Cooler Master Geminii S524
Memory G.Skill DDR4-2133 16GB (8GB x 2)
Video Card(s) Gigabyte R9-380X 4GB
Storage Samsung 950 EVO 250GB (mSATA)
Display(s) LG 29UM69G-B 2560x1080 IPS
Case Lian Li PC-Q25
Audio Device(s) Realtek ALC892
Power Supply Seasonic SS-460FL2
Mouse Logitech G700s
Keyboard Logitech G110
Software Windows 10 Pro
#9
Those parity calculations and other methods were just too fancy for such a random brute force approach to n-puzzle. Changed it up so that it starts from the goal state and runs 10,000 moves before it is allowed to break loop when it reaches the goal state again.

Code:
C:\php>php puzzle.php 5 3 3
Time: 1.063s    Moves: 197761
Time: 3.327s    Moves: 617154
Time: 3.246s    Moves: 589875
Time: 1.562s    Moves: 290963
Time: 1.308s    Moves: 243138

C:\php>php puzzle.php 5 3 4
Time: 631.760s  Moves: 107567139
Time: 3004.540s Moves: 501030478
(var order is loops/height/width)

Nice. Time to run this on my desktop when I get home. Faster than this laptop and can run puzzles 3x4, 4x4, 4x5, and 5x5 simultaneously.
 
Joined
Aug 10, 2007
Messages
4,059 (1.07/day)
Likes
1,123
Location
Geneva, FL, USA
Processor Intel i5-6600
Motherboard ASRock H170M-ITX
Cooling Cooler Master Geminii S524
Memory G.Skill DDR4-2133 16GB (8GB x 2)
Video Card(s) Gigabyte R9-380X 4GB
Storage Samsung 950 EVO 250GB (mSATA)
Display(s) LG 29UM69G-B 2560x1080 IPS
Case Lian Li PC-Q25
Audio Device(s) Realtek ALC892
Power Supply Seasonic SS-460FL2
Mouse Logitech G700s
Keyboard Logitech G110
Software Windows 10 Pro
#10
While I could have continued to optimize my script, there's no way I could have it match a compiled program. So I wrote it up C++ style:

Code:
Projects\Puzzle\Release>Puzzle.exe 10 3 4
L1: 31.201s,	Moves: 431331490
L2: 22.865s,	Moves: 313645354
L3: 54.819s,	Moves: 751440362
L4: 7.02s,	Moves: 99313507
L5: 2.73s,	Moves: 38240275
L6: 38.14s,	Moves: 523117195
L7: 8.424s,	Moves: 115969315
L8: 4.695s,	Moves: 64458998
L9: 10.483s,	Moves: 146073973
L10: 53.599s,	Moves: 753855436
At an average of 13.8M moves/second, that's one fast monkey! I have him busily working on a 4x4 puzzle now.

Next up, have the program spawn multiple monkey processes and if possible, make them semi-intelligent. Ideally it would involve them learning number order, and learning from each other. The time each one takes to solve the puzzle should go down as the numbers of monkeys increase.