The Chess Queen Puzzle (Source Included)
BlitzMax Forums/BlitzMax Programming/The Chess Queen Puzzle (Source Included)
| ||
| TomToad wrote an article on recursion. According to what he wrote, he said it would take an inordinately large amount of time to calculate the position of eight chess Queen pieces on a board where no queen can capture another. There are several ways to go about solving this problem. One way would be to put the queens on the board in some random combination, then see if that combination results in a solution. If not, then replace the queens in another, untried combination. Since there are 178,462,987,637,760 possible combinations, that will potentially take a lot of time to compute. In the worse case scenario, being there is no possible solutions, if the computer calculates 100 combinations per millisecond, then it would take over 56 years to go through all the combinations. He said it's supposed to be easier with recursion.  Well, here is my method without recursion and it works rather quickly. [1] Choose a random square that is empty. [2] check to see if can be captured by any existing queen pieces ? If yes, go back to step 1. After 50 times of this though, remove an existing queen and try again. [3] Piece is in the clear ? Drop it down. [4] Repeat until all 8 queens are down on board and none can capture each other. On my computer it takes anywhere from immediate to 10-seconds to find a solution. Note, this could actually run a LOT faster if you only updated the graphics when a piece was dropped and it was higher than the last highest count, but it's interesting to watch the pieces fight each other so I opted to show the board's progress so you can see it in action. :) Here is the code including a neat way to draw lathed chess pieces, enjoi !  |
| ||
| Recursion is certainly not necessary, nor is guessing with random placement. I once wrote a backtracking program to generate all possible solutions to the eight queens problem. It finished in practically no time, running on an 8-bit 1.77MHz computer. That's not even a thousandth the speed of a reasonably modern PC. |
| ||
| Hey Cap'n ! Well, there are some things I could do to make this faster. One of which I call a Seek Random. That is, a random position is thought of, but if it doesn't match, instead of seeking a new random position, it increases the horizontal or vertical, then increases the other (if it was vertical increase horizontal or if it was horizontal then increase vertical). Do this until you wrap around the board back to your home position. THEN for certain you know there is =NO= possible solution for that piece and you can go back a step. I think that would speed up the search considerably. Pretty sure I'm doing this in my maze-maker when seeking out empty spaces to carve into: http://www.blitzbasic.com/Community/posts.php?topic=105489 Do you still have the code you wrote on the Queen puzzle ? And did you ever port it to BlitzMAX ? |
| ||
| And - is it in BlitzMAX ? Hardly! I think I wrote that in a very nice proprietary language called Action!, on an 8-bit Atari. Do I still have the code? Maybe. Somewhere in the crawlspace under my house there is a box with the old Atari computer, plus the external disk drive and a bunch of 5.25" floppies. If the equipment still works and the relevant disk is readable then I still have the code. I would have no way to post it short of manual retyping, unless the old dial-up modem also worked and I found some place that still offers a dial-up connection. But I can summarize what the algorithm was like. The placement of the queens was represented by an eight element array. The array [ 3, 7, ...] for example would mean that, examining the board left to right, there is a queen on the the third rank, seventh rank etc. That is, on squares a3, b7... When looking for solutions lets say we have [ 2, 5, ...] so far. We try placing a third queen, successively trying positions 1,2,3 etc. In this example, using 1 for the third queen fails immediately. We move on to 2,3,4 which also fail. 5 works, so we use that and proceed to placing the fourth queen. When we encounter a situation in which every possible placement fails we "backtrack". For example, we try to place a sixth queen and all eight attempts fail. Then there is no solution extending what we have with the first five. So we back up to the fifth queen and try higher values, placing it farther up the board. Any consistent arrangement of eight queens is reported as a solution. We then backtrack to the seventh queen and keep looking. Any time we have examined every placement 1..8 for the nth queen we back up to n-1 and forge ahead. If we ever need to backtrack from the first queen then every possibility has been tried and we quit. The idea of backtracking is pruning infeasible partial solutions. Every placement of eight queens can be considered as an eight digit number, each digit being in the range 1..8. For example 134xxxxx would represent a large number of potential solutions beginning 134. But we don't look at them because we recognize that 134 is already inconsistent. Thus we move on to 135. Come to think of it you might do better to by Googling eight queen backtracking rather than trying to decipher my description. |
| ||
| According to what he wrote, he said it would take an inordinately large amount of time to calculate the position of eight chess Queen pieces on a board where no queen can capture another - if you do not use recursive code If you read the post carefully, I did not say it would take an inordinately large amount of time without recursion. I said that the method of randomly selecting positions until one works would take an inordinately large amount of time, and that recursion is one way to make things go faster. Since the tutorial was about using recursion and not necessarily about solving the 8 queens puzzle, I did not focus on other solutions. However, I did post one alternative at the bottom which did not use recursion and was actually faster than my code. However, that program was tailored specifically for the 8 queens and difficult to modify for other types of puzzles, which went out of scope for the tutorial. |
| ||
| What I've noticed, Tom, is it seems to me that all 8 figures can be found based on the movements of a knight. Place a queen in the bottom-right-hand corner. Then spread out based entirely on movements a knight would make. The other is a bit simpler now that I really think about it. Only 2 checks need to be made: If x2=x or y2=y then placement is invalid if abs(x2-x)=abs(y2-y) then this placement is also invalid Done ! :) Maybe sometime I should try my hand at writing a chess game where you play against the computer. I did not read the recursion part. I'll look at that next. Recursion to me is still a pretty amazing thing. |
| ||
Here's a small recursion-based example which is quite fast :SuperStrict Framework brl.standardio Local q:TQueensRecursion = New TQueensRecursion q.test(0,0,0) Print "Solutions = " + q.count Type TQueensRecursion Field all:Int = 255 Field count:Int Field rows:Int[8] ' based on Martin Richards. Backtracking Algorithms in MCPL using Bit Patterns and Recursion ' http://www.cl.cam.ac.uk/~mr10/backtrk.pdf Method test(ld:Int, col:Int, rd:Int, row:Int = 1) Local poss:Int = ~(ld | col | rd) & all While poss Local bit:Int = poss & -poss poss :- bit rows[row-1] = bit ' record row test( (ld|bit)Shl 1, col|bit, (rd|bit) Shr 1, row + 1 ) Wend If col = all Then ' we have a completed solution DumpRows() count :+ 1 End If End Method ' solution output stuff Method DumpRows() Print "" For Local i:Int = 0 Until 8 Print Binary(rows[i]) Next End Method Method Binary:String(val:Int) Local buf:Short[8] For Local k:Int=7 To 0 Step -1 If val&1 Then buf[k] = Asc("Q") Else buf[k] = Asc(".") End If val:Shr 1 Next Return String.FromShorts( buf,8 ) End Method End Type |
| ||
| Hi Brucey. No, there's a certain satisfaction in having solved this logic puzzle myself without help from someone's else's formula. :) Cap'n, no, the adventure was in finding a solution in my own code. And I discovered a new drawing method on how to doodle lathed marble chess pieces effectively !  Awright you guyz ! How about the, "Knight's Tour" in your own code ? No borry from other sources or formula, this one is a real brainweave ! http://en.wikipedia.org/wiki/Knight's_tour |
| ||
| Just for fun I wondered how small of coding I could do to solve the Queen problem. Here it is ! 15-lines of code not counting remarks and display routine ! |
| ||
| Was just thinking about a chess puzzle program I did years ago. Posted it here http://www.blitzbasic.com/Community/posts.php?topic=80915#1293445 |
| ||
| Hi Tom. You're not posting the source. That's fine. :) I think I decided when I finish this 750k to 64-byte compressor, I'll post the EXE but gonna keep the source for myself. I know not all commercial programmers - especially those who write games that sell for $50 and up - are too eager about releasing their source codes to the public either. On the line of chess, you might be interested in this: SOLITAIRE CHESS There is also Fork My Fruit, one of my favorite chess games and puzzles on a PSP game called Chessmaster. I couldn't seem to find a decent video in Youtube, some guy horking up, not very professional. Basically you put fruit on the screen, then a chess piece (or two), and you must navigate to zap as many fruit as you can. Unlike regular chess if there are two or more fruit that can be captured, forks leap out in those directions to 'fork' them. I like this game so much I was thinking of maybe writing one in the future where you don't fork fruit but shoot swords at monsters and your chess pieces are rendered to look more human than wooden and walk with animation around the board. :) |
| ||
| Awright you guyz ! How about the, "Knight's Tour" in your own code ? No borry from other sources or formula, this one is a real brainweave ! Gave this one a try. Wrote the code, let it go for half an hour without a solution found, aborted the run. Optimized the code a bit, let run for another half hour without a solution. Tried optimizing a bit more, can't optimize any further, ran for 30 minutes without a solution found. Then thought of one more way to optimize the code. Was shocked when it came up with the solution in only .08 seconds! I would've been happy if it ran under 30 minutes, didn't expect less than a second. :-) |
| ||
| Wholly Smacks, Tom ! That is some real BB code there ! Beyond beautiful ! I thought about the puzzle myself and I =THINK= this particular one is considerably more difficult than the Queens. Not that it would be easy, can you have it start from any position on the board ? You can change this code: If (x & 1) ~ (y & 1) = 1to If(x+y)Mod 2if you like and you will still get a beautifully colored chessboard. Still ... very nice coding ! |
| ||
| Actually, I could've done (x~y)&1 That probably would've been the fastest way. |
| ||
| For those who want it, Source code for Mate in Two |
| ||
| Does ~ mean NOT or XOR in BMax? If it means NOT then (x+y) & 1 would be fastest. because NOT has drawback in speed (you could use XOR allbits to fake NOT but then you have one uneeded instruction instead). If it means XOR then both (x~y)&1 and (x+y)&1 would be equally fast. I´m amazed at all the code here. Really nice. Both graphicswise, and the algoritms it looks MARBLE-less. I would like to dig up my Suduoko code and convert it into Bmax now. |
| ||
| Hi Casaber. Glad I know something for a change. :) Yes, the tilde "~" means XOR. You can see it in heavy use for encryption HERE: http://www.blitzbasic.com/Community/post.php?topic=105767&post=1293912 |
| ||
| if there is only 1 parameter, it means NOT (a = ~x -> a = NOT x) If there are 2 parameters, it means XOR(a = x ~ y -> a = x XOR y) After doing a benchmark, I was surprised that + was twice as fast as ~, I'd think worse case scenario would be the same speed. |
| ||
| Good to know, TomToad ! It means NOT you don't have a variable on the left. I need to commit that to memory. I could find that useful later. |
| ||
| What am I doing wrong here? Or, is Bmax optimizing after all? I don´t know what else to believe because I get the same time time on all? 700+-1 EDIT OOPS loop overhead. Take away one zero of the loop and do 10 of anything instead inside the loop and it gets tenfold faster. This was a bad benchmark of me. The loop code got all the time. EDIT Still the same zero difference between them though. I need to check the assembler source. Got curious. I´m doing something very wrong. a=0 ; x=10 ; y=20 starttime = MilliSecs() For temp = 1 To 1000000000 a = x + y ' ADD 704 ' a = x - y ' SUB 704 ' a = -x ' NEG 700 ' a = ~x ' NOT 705 ' a = x ~ y ' XOR 695 Next endtime = MilliSecs() Print endtime-starttime WaitKey |
| ||
| Ok, I think my difference is to CPU optimizations. I wrote a test program that would perform ~ a bunch of times, then + a bunch of times and print the results. + was coming out twice as fast. If I swap the order of the tests, then ~ is twice as fast. I think that the CPU sees that the test program is doing a ton of calculations really quick and after a while, tasks more of the CPU to the program, causing whatever tests later to run much faster. |
| ||
| Actually that's correct here. 4000+ is about 4-seconds. Or if you are getting a different result, please post the total you are receiving, Casaber. |
| ||
| Yeup, that is what's happening. Just ran task manager and watched as CPU usage was ramped up from about 20% to over 30%. That will make profiling much more difficult to achieve. |
| ||
| Also, Casaber, I think what you want to do to determine which command is at what speed. Try this code and see if it gives you better information: As far as I can tell, I think these commands are pretty well and evenly matched. |
| ||
| I´m going crazy trying to understand where to find the assembler source on OSX here. With Blitz3D and Windows you could create a file like so, easy peasy: Compile.bat blitzcc -a -c name.bmax name.asm |
| ||
| Are you wanting to run a BAT file in BlitzMAX ? That can be done. |
| ||
| I don´t think OSX has bat files? Is there a way to tell Bmax to leave the assembler files intact and not throw them away on Macs? |
| ||
| I don't even know if BlitzMAX can do assembly. I =THINK= it can do C but I'm not certain. OSX is for the Macintosh ? |
| ||
| Ya Bmax executables is created using FASM on all platforms. And I read in the latest info that now it allows FASM optimations. BMax I think is able to IMPORT "filename.s" even, but you cannot inline assembler code. EDIT Monkey for example keeps all the sourcefiles readily after you've pushed the run button, which is nice. But BMax throws everything away, and keeps only the final executable. I would love to check that temporarily created asm file now. I cannot come up with a easy way. Right now the easiest way would be to deassemble and look carefully for a few hours haha. I know, It's probably easiest thing in the world when you've finally learned it, but right now I´m getting gray hair here :s |
| ||
| Ya Bmax executables is created using FASM on all platforms. And I read in the latest info that now it allows FASM optimations. BMax I think is able to IMPORT "filename.s" even, but you cannot inline assembler code. EDIT Monkey for example keeps all the sourcefiles readily after you've pushed the run button, which is nice. But BMax throws everything away, and keeps only the final executable. I would love to check that temporarily created asm file now. I cannot come up with a easy way. Right now the easiest way would be to deassemble and look carefully for a few hours haha. I know, It's probably easiest thing in the world when you've finally learned it, but right now I´m getting gray hair here :s |
| ||
| Ya Bmax executables is created using FASM on all platforms. And I read in the latest info that now it allows FASM optimations. BMax I think is able to IMPORT "filename.s" even, but you cannot inline assembler code. EDIT Monkey for example keeps all the sourcefiles readily after you've pushed the run button, which is nice. But BMax throws everything away, and keeps only the final executable. I would love to check that temporarily created asm file now. I cannot come up with a easy way. Right now the easiest way would be to deassemble and look carefully for a few hours haha. I know, It's probably easiest thing in the world when you've finally learned it, but right now I´m getting gray hair here :s |
| ||
| Three gray hairs to be precise. :) Looks like the forum triple-posted you. It's done that to me a few times. Casaber, as this post is primarily about chess, you might make a new post about what you are asking. You'll have fresh faces and new ideas sent to you. Because I think if someone sees that there is a new post in the Chess Queen Puzzle and they may not be looking for someone asking for help with assembly. You may get it here, I hope you find the answer you're looking for. |
| ||
| BTW, Casaber, you mentioned you are looking for assembly code ? I found if you go inside the directory, ".bmx" which is located outside the compiled EXE, there are two types of files there. One has an "o" extension. I think you would be interested in the "s" extension which, from viewing in Notepad, appears to be the raw assembly code of what you just compiled. |
| ||
| Wouldn't you know it? Since a never gets used, the math is never performed. The compiler just optimizes it right out of the code. It just loops several times, prints the resulting times, then ends. By adding the result of a to the Print statement after the loop, the math is kept in the code. Both take exactly the same amount of time. Print a+" "+(EndTime - StartTime) |
| ||
| @Dw817 I htough t i saw that somewhere !! I guess it's different on Windows and I saw it over there, On Mac you cannot see tha but yu of course I might start a thread later about that. Sorry for the subjectchange, good call. |
| ||
| No, that's fine, we're all learning here, Casaber. Truly I thought operands operated at a different speed, but maybe not. It's an interesting point you brought up: Here is another model: Now you would THINK this one to be very accurate as it determines the average value of cycles per 1% of a second in a total of 100 times. I'm also not just calculating the same number each time but adding it the total so you are guaranteed to have work on each type. I'm also doing a time out in the beginning to ensure there is nothing to mess up the timing. |
| ||
| Just one last about code (I got my hands on the PC) It was tough to get it to keep variables, if you don´t end up using something, it just won´t compile anything. So it's kind of good that way. EDIT So it's very sloppy optimizing. It manages the not needed part. An add for instance wouldnt hurt and most of all, it would be easy as cake to see it in the source and take away manually if it where a catastrophy in speed. Then it plumps on all kinds things CALL, branches etc. I would call this code. Non-optimized. Technically it is optimized, but on the wrong things. It´s okay though. I know Assembler all to well to appriciate BASIC ;) And the test becomes An open closeup on the simpler example EDIT the code stays like this when defining a as integer. EDIT it optimized out !! the add It came to me.. If you force in a PLOT A,A after the add, it compiles the add. It skipped it, that FPU code is nothing related to an add. Im not sure what it does in there. Repeat a=5 Plot a,a a=a+1 Delay 1 Flip 1 Until MouseDown(2) Becomes _24: ' REPEAT' ' A = 5' mov eax,5 ' A = A + 1 ' (ODD ADD MULTILINER COMING UP) mov dword [ebp+-4],eax fild dword [ebp+-4] sub esp,4 fstp dword [esp] mov dword [ebp+-4],eax fild dword [ebp+-4] sub esp,4 fstp dword [esp] ' PLOT' call _brl_max2d_Plot add esp,8 ' DELAY 1' push 1 call _bbDelay add esp,4 ' FLIP 1' push 1 call _brl_graphics_Flip add esp,4 _22: push 2 call _brl_polledinput_MouseDown ' READ MOUSEDOWN' add esp,4 cmp eax,0 ' = 0 ? je _24 ' UNTIL (JUMP IF MOUSEDOWN = 0) ' END' .. for completeness this is how it looks when you add a PLOT A,A right after the add. It then compiles the add. (if not its clever not to compile the add). It seem like that FPU code is for the PLOT? Converting integer to float? I´m not sure what else it could be about. Ya it's conversion in action. |
| ||
| Casaber, you have the repeat before the a = 5. You might swap places and then the line will draw. :) In addition to that, if you use Framework your machine code might get smaller and using GlMax2DDriver(),0 will make it plot a lot faster than without. Strict Framework brl.glmax2d ' standard Graphics Local a SetGraphicsDriver GLMax2DDriver(),0 Graphics 800,600 a=5 Repeat Plot a,a a=a+1 Delay 1 Flip 1 Until MouseDown(2) |
   |