• Welcome to TechPowerUp Forums, Guest! Please check out our forum guidelines for info related to our community.

Java+VB developers project

Joined
Jan 4, 2009
Messages
136 (0.04/day)
Likes
13
Location
Ninja's Dont Need Homes
#1
hey i am taking a java programming class and we have a developers project to do

our task:
a simple chess board with a knight.
what we have to do is programm the knight to move on all squares/tiles of the board without going on the same square/tile.

now this can be done because i have seen some of the ones the last years class did
some of the methods they used were things like:

-brute force
trying every possible algorithym until prooved successful
the problem with this is that it took ages and had a total of ~3.5 million failed tries before it had found a successful path.

-or valued squares
where the tiles on the chess board had a certain value depending on the avaliable moves once on that tile. this method prooved great only it needed a certain AI for it to know what tile had the best value on the next moves.
this method got it solved it in 2.5 seconds.

as i know it can be done in java, and i am confident in visual basic, i would like to see if anyone can help me out with making this happen in visual basic. if not, try it out in java

happy coding
 

FordGT90Concept

"I go fast!1!11!1!"
Joined
Oct 13, 2008
Messages
21,101 (6.22/day)
Likes
10,230
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.
#2
The first thing you need is a chess board (an array 8x8). I would make it an array of signed bytes where -1 is a tile that hasn't been touched and 0-63 indicating moves (where the knight was).

Knights move 2 in one direction and 1 in another.

Make a method which returns an array 8 long. Every value in the array represents one of the possible places the peice could move. If the value is true, that means the peice can go there. If it is false, it can't. The conditions for returning a false value are as follows:
1) this location resides outside of the array
2) this location has already been hit (value != -1)

Loop through that method until all the values in the array are false (no legal moves). It may, or may not hit them all.

A random seed may have to be used on the order in which the possible value is chosen in order to increase the liklihood that it would eventually hit all 64 tiles (assuming it doesn't the first time).



I won't code this unless you've already gotten credit for it in the class (not gonna do the work for you :p).
 

FordGT90Concept

"I go fast!1!11!1!"
Joined
Oct 13, 2008
Messages
21,101 (6.22/day)
Likes
10,230
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.
#4
Attempts: 858,183
Duration: 39.0312500 seconds

Mind you, it runs on a random number generator so it is possible that it succeeds on the first attempt.

Second run...
Attempts: 625,637
Duration: 28.7343750 seconds

Third run...
Attempts: 33,420
Duration: 1.5781250 seconds

Fourth run...
Attempts: 132,226
Duration: 6.125 seconds

Fifth run...
Attempts: 50,836
Duration: 2.453125 seconds
Solution:
Code:
+----+----+----+----+----+----+----+----+
|  0 | 21 | 62 | 35 |  2 | 33 | 24 |  9 |
+----+----+----+----+----+----+----+----+
| 63 | 54 |  1 | 22 |  7 | 10 |  3 | 32 |
+----+----+----+----+----+----+----+----+
| 20 | 61 | 36 | 55 | 34 | 23 |  8 | 25 |
+----+----+----+----+----+----+----+----+
| 53 | 56 | 19 |  6 | 11 | 26 | 31 |  4 |
+----+----+----+----+----+----+----+----+
| 60 | 37 | 58 | 27 | 18 |  5 | 12 | 47 |
+----+----+----+----+----+----+----+----+
| 57 | 52 | 41 | 38 | 13 | 46 | 17 | 30 |
+----+----+----+----+----+----+----+----+
| 40 | 59 | 50 | 43 | 28 | 15 | 48 | 45 |
+----+----+----+----+----+----+----+----+
| 51 | 42 | 39 | 14 | 49 | 44 | 29 | 16 |
+----+----+----+----+----+----+----+----+
Sixth run...
Attempts: 956,781
Duration: 45.03125 seconds
Solution:
Code:
+----+----+----+----+----+----+----+----+
|  0 | 57 |  8 | 53 | 10 | 55 | 40 | 43 |
+----+----+----+----+----+----+----+----+
| 37 | 52 |  1 | 56 | 39 | 42 | 11 | 18 |
+----+----+----+----+----+----+----+----+
| 58 |  7 | 38 |  9 | 54 | 19 | 44 | 41 |
+----+----+----+----+----+----+----+----+
| 51 | 36 |  5 |  2 | 29 | 12 | 17 | 20 |
+----+----+----+----+----+----+----+----+
|  6 | 59 | 50 | 13 |  4 | 27 | 30 | 45 |
+----+----+----+----+----+----+----+----+
| 35 | 62 |  3 | 28 | 47 | 16 | 21 | 24 |
+----+----+----+----+----+----+----+----+
| 60 | 49 | 14 | 33 | 26 | 23 | 46 | 31 |
+----+----+----+----+----+----+----+----+
| 63 | 34 | 61 | 48 | 15 | 32 | 25 | 22 |
+----+----+----+----+----+----+----+----+

I think that's enough for now. :p


My code allows to change the start location to anywhere, resize the chess board, and stop at x number of moves.

It averages 21247 attempts per second on my Core i7 920. It is only a single thread app right now but I could make it run on multiple threads and output the solution that is found first. ;)
 
Last edited:

FordGT90Concept

"I go fast!1!11!1!"
Joined
Oct 13, 2008
Messages
21,101 (6.22/day)
Likes
10,230
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.
#5
I multithreaded it. The fastest result so far is:

Attempts: 3,181
Duration: 0.2031250 seconds
Seed: 110152139
Solution:
Code:
+----+----+----+----+----+----+----+----+
|  0 | 63 | 52 | 27 |  2 | 35 | 50 | 29 |
+----+----+----+----+----+----+----+----+
| 53 | 26 |  1 | 36 | 51 | 28 | 33 |  4 |
+----+----+----+----+----+----+----+----+
| 62 | 37 | 24 | 21 | 34 |  3 | 30 | 49 |
+----+----+----+----+----+----+----+----+
| 25 | 54 | 15 | 38 | 23 | 20 |  5 | 32 |
+----+----+----+----+----+----+----+----+
| 42 | 61 | 22 |  7 | 14 | 31 | 48 | 19 |
+----+----+----+----+----+----+----+----+
| 55 | 58 | 43 | 16 | 39 |  6 | 13 | 10 |
+----+----+----+----+----+----+----+----+
| 60 | 41 | 56 | 45 |  8 | 11 | 18 | 47 |
+----+----+----+----+----+----+----+----+
| 57 | 44 | 59 | 40 | 17 | 46 |  9 | 12 |
+----+----+----+----+----+----+----+----+

It is coded in C#.NET (could relatively easily be converted to VB.NET, performance about the same).

Here's the class diagram of the code:
http://img.techpowerup.org/090507/ClassDiagram1.png

I won't paste/upload any code until I know you got credit for the assignment. ;)
 
Last edited:
Joined
Jan 4, 2009
Messages
136 (0.04/day)
Likes
13
Location
Ninja's Dont Need Homes
#6
hey thanks heaps this has given me a great idea how to do it.

now all i need to do is......to do it lol

we are meant to hand it in in java but my lecturer said if that i can do it in VB he'll pass me strait away. im guessing this means that it'll be harder in VB
 

FordGT90Concept

"I go fast!1!11!1!"
Joined
Oct 13, 2008
Messages
21,101 (6.22/day)
Likes
10,230
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.
#7
I would use VB.NET over Java any day. If you haven't done any VB.NET coding before though, you best stick to Java unless the due date is rather distant.


It took me an hour and a hour and a half to code the single threaded version, half an hour to make it display the results in the grid, and an hour and a half to multithread it. It took about three and a half hours total.


Of course, using my method, it could take several minutes to find a result or it might take mere seconds. It depends how good of a random seed it is working on. XD
 
Last edited:

Oliver_FF

New Member
Joined
Oct 15, 2006
Messages
544 (0.13/day)
Likes
65
Processor Intel q9400 @ stock
Motherboard Lanparty P45-T2RS
Cooling Zalman CNPS-9500
Memory 8GB OCZ PC2-6400
Video Card(s) BFG Nvidia GTX285 OC
Storage 1TB, 500GB, 500GB
Display(s) 20" Samsung T200HD
Case Antec Mini P180
Audio Device(s) Sound Blaster X-Fi Elite Pro
Power Supply 700w Hiper
Software Ubuntu x64 virtualising Vista
#8
If you don't want to brute force it as per FordGT's proposal, you can add in some logic to test for un-reachable squares.

eg- if, after making a move, an untouched square is surrounded by touched squares 2 levels deep, the previous move was invalid. Suppose you get an un-reachable square after the 10th move (54 moves left to make) then you've immediately ruled out 432 moves. You need to be clever about it though, you don't want to waste time checking for impossible squares when they are clearly possible ;)

I suppose it all depends on how competent you are at programming and how much computer algorithms interest you :)
 

FordGT90Concept

"I go fast!1!11!1!"
Joined
Oct 13, 2008
Messages
21,101 (6.22/day)
Likes
10,230
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.
#9
Hmm, sounds like a node system. That would be great for systematically finding every possible solution given a start point. I doubt it would be very fast but it would be far more reliable than my "throw spaghetti at the wall and see if it sticks" solution. XD


You'd think there would be some equation/pattern that could solve it pretty much instantly but I'm no mathematical expert.
 

Sonido

New Member
Joined
Aug 25, 2008
Messages
356 (0.10/day)
Likes
85
Location
USA
System Name Sonido
Processor E6600 @ 3.20 GHz (1600 FSB)
Motherboard abit IX38 QuadGT
Cooling Tt SpinQ (load @ 29c)
Memory TopRam SpeedRAM A.K.A "El Cheapo" @ 800 MHz
Video Card(s) Diamond HD 4870 (@ Stock)
Storage Primary: 500 GB WD
Display(s) 32" Samsung 1080p HDTV
Case Antec Twelve hundred (Modded Tri-cool fans)
Audio Device(s) On-board HD Audio
Power Supply 700W Rocketfish
Software Vista\7\Linux\Hackintosh
#10
Hmm, sounds like a node system. That would be great for systematically finding every possible solution given a start point. I doubt it would be very fast but it would be far more reliable than my "throw spaghetti at the wall and see if it sticks" solution. XD


You'd think there would be some equation/pattern that could solve it pretty much instantly but I'm no mathematical expert.
The equation would actually be quite long. The permutations possible are in the range of "A LOT". So... Yea... :D

Unless, are you are speaking of a static pattern? A pattern that doesn't change?
 

FordGT90Concept

"I go fast!1!11!1!"
Joined
Oct 13, 2008
Messages
21,101 (6.22/day)
Likes
10,230
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.
#11
Yeah, a static pattern. Figure out one pattern that will hit like 32 of the tiles, then another to hit another 16 or so, one that will hit another 8, and another that will hit the final 8. That way, you run those 4 algorithms in succession and the puzzle is done.

I admit, that route is kind of boring because you always know the outcome. It is interesting to see how such random paths work with my algorithm. ;)


Edit: The fastest way to solve it would be to take one of the solutions I pasted and procedurally produce it every time. It could be somewhat entertaining to make a class which describes the eight movements he knight can make and then list the 64 moves necessary to complete the puzzle. For example:

Code:
Knight myknight = new Knight(0, 0);
myknight.MoveRightDown();
myknight.MoveRightUp();
myknight.MoveDownRight();
// etc.
Where the first direction implies two squares and the second direction implies one square. I'm not sure that would meet your class's requirements though. It would "solve" in the thousandths or hundredths of a second.

Edit: I took the liberty to add this functionality to my code. Here is a result:
Code:
+----+----+----+----+----+----+----+----+
|  0 | 57 | 40 | 59 | 24 | 49 | 42 | 47 |
+----+----+----+----+----+----+----+----+
| 39 | 60 |  1 | 52 | 41 | 46 | 25 | 50 |
+----+----+----+----+----+----+----+----+
| 56 | 53 | 58 | 23 | 12 | 51 | 48 | 43 |
+----+----+----+----+----+----+----+----+
| 61 | 38 | 55 |  2 | 45 | 22 | 11 | 26 |
+----+----+----+----+----+----+----+----+
| 54 |  3 | 34 | 13 | 10 | 27 | 44 | 21 |
+----+----+----+----+----+----+----+----+
| 37 | 62 |  5 | 32 | 15 | 18 |  9 | 28 |
+----+----+----+----+----+----+----+----+
|  4 | 33 | 14 | 35 | 30 |  7 | 20 | 17 |
+----+----+----+----+----+----+----+----+
| 63 | 36 | 31 |  6 | 19 | 16 | 29 |  8 |
+----+----+----+----+----+----+----+----+
The move list...
Code:
RightDown
DownRight
LeftDown
DownLeft
RightUp
DownRight
RightUp
RightDown
UpLeft
LeftUp
RightUp
LeftUp
DownLeft
DownLeft
RightUp
DownRight
RightUp
LeftUp
DownLeft
RightUp
UpRight
LeftUp
LeftUp
UpRight
RightDown
DownRight
LeftDown
RightDown
DownLeft
LeftUp
LeftDown
UpRight
LeftDown
UpRight
DownRight
LeftDown
UpLeft
UpRight
UpLeft
RightUp
RightDown
RightUp
DownRight
DownLeft
LeftUp
UpRight
RightUp
DownLeft
UpLeft
RightDown
LeftDown
LeftUp
LeftDown
DownLeft
RightUp
LeftUp
UpRight
DownRight
UpRight
LeftDown
DownLeft
DownRight
DownLeft
 
Last edited:

Sonido

New Member
Joined
Aug 25, 2008
Messages
356 (0.10/day)
Likes
85
Location
USA
System Name Sonido
Processor E6600 @ 3.20 GHz (1600 FSB)
Motherboard abit IX38 QuadGT
Cooling Tt SpinQ (load @ 29c)
Memory TopRam SpeedRAM A.K.A "El Cheapo" @ 800 MHz
Video Card(s) Diamond HD 4870 (@ Stock)
Storage Primary: 500 GB WD
Display(s) 32" Samsung 1080p HDTV
Case Antec Twelve hundred (Modded Tri-cool fans)
Audio Device(s) On-board HD Audio
Power Supply 700W Rocketfish
Software Vista\7\Linux\Hackintosh
#12
TBH, you are right. It would be boring, but it's also safe. e-condom?
 

FordGT90Concept

"I go fast!1!11!1!"
Joined
Oct 13, 2008
Messages
21,101 (6.22/day)
Likes
10,230
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.
#13
LMAO, yeah. XD
 

Sonido

New Member
Joined
Aug 25, 2008
Messages
356 (0.10/day)
Likes
85
Location
USA
System Name Sonido
Processor E6600 @ 3.20 GHz (1600 FSB)
Motherboard abit IX38 QuadGT
Cooling Tt SpinQ (load @ 29c)
Memory TopRam SpeedRAM A.K.A "El Cheapo" @ 800 MHz
Video Card(s) Diamond HD 4870 (@ Stock)
Storage Primary: 500 GB WD
Display(s) 32" Samsung 1080p HDTV
Case Antec Twelve hundred (Modded Tri-cool fans)
Audio Device(s) On-board HD Audio
Power Supply 700W Rocketfish
Software Vista\7\Linux\Hackintosh
#14
If you don't want to brute force it as per FordGT's proposal, you can add in some logic to test for un-reachable squares.

eg- if, after making a move, an untouched square is surrounded by touched squares 2 levels deep, the previous move was invalid. Suppose you get an un-reachable square after the 10th move (54 moves left to make) then you've immediately ruled out 432 moves. You need to be clever about it though, you don't want to waste time checking for impossible squares when they are clearly possible ;)

I suppose it all depends on how competent you are at programming and how much computer algorithms interest you :)
Hmm, sounds like a node system. That would be great for systematically finding every possible solution given a start point. I doubt it would be very fast but it would be far more reliable than my "throw spaghetti at the wall and see if it sticks" solution. XD
I just thought about something... Oliver's solution would take a lot more time to code, but it would take less time to solve. While Ford's concept takes less time to code, it take a lot more time to solve. Hmmm, I just blew my own mind!
 

FordGT90Concept

"I go fast!1!11!1!"
Joined
Oct 13, 2008
Messages
21,101 (6.22/day)
Likes
10,230
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.
#15
Actually, I doubt a node system would take too long to code--just needs some OOP. The only difference is that, instead of restarting from scratch, it would move back in the move list, try a different solution, and failing that solution, move back and try again. It might be faster, it might not be. I'm not sure if I'll code it though as the OP hasn't come back. :(