|
|
|||||||||
|
|||||||||
| |||||||||
|
|
|
| |||||||||
![]() |
|
|
«
Previous Thread
|
Next Thread
»
|
Thread Tools | Search this Thread | Rate Thread | Display Modes |
|
|
AT&T devCentral & BlackBerry(r) Webcast Series: BlackBerry and GPS -Build Location Awareness into your BlackBerry Applications, July 10th-1:00PM EST. Register Today!
|
|
#1
|
|||
|
|||
|
8 queen memory problem
i have written a script that should solve the 8 queen puzzle. you can find it here -> http://rok.pajek.net/hp/8queen.phps
i think that there is no problem in algorithm... problem is becouse this script uses realy a lot of memory, and i don't know why.... it uses all available memory... and when it uses all it then shutsdown.... why is this so? best regards |
|
#2
|
|||
|
|||
|
RE: 8 queen memory problem
What I can say is that there are many loops and those loops uses huge amount of memory. Running that much loops in a one page will cause exactly to slow your computer and shut down.
|
|
#3
|
|||
|
|||
|
RE: 8 queen memory problem
but why are those loops using so much memory? is it possible to make that more memory friendly...??
|
|
#4
|
|||
|
|||
|
RE: 8 queen memory problem
[moved to the theory forum. I think you will get better discussion here.]
|
|
#5
|
|||
|
|||
|
RE: 8 queen memory problem
It is not suprising that loops uses huge amount of memory to run on. In any programming language, if you use many loops inside a one code it will get slow/stuck. To make your code more friendlier you can use many functions and write your loops inside them. After that instead of writing same loop over and over again, just call the function with few parameters passed into them. It will make the code execution time more faster than now!!!!
|
|
#6
|
||||||
|
||||||
|
RE: 8 queen memory problem
Quote:
CodeKadiya is right. I estimate your code is trying to make 8^33 irriterations (over 6.3 octillion irriterations), and that's not counting loops that aren't processed due to logic errors. I'm not quite sure what your script is trying to accomplish. Through multiple loops it makes calls to scan and check functions; scan will always return true because $board[$i][$j] will never be set equal to '11'. Check doesn't do anything either; $board[$i][$j][1] does not exist so it will never be set to '1' and the the conditional code will never be processed. But I do have these recommendations for the rest of the code, though: Change tokens from '00', '01', '1' and '11' to 0, 1, 2 and 3. 0 is processed approximately 10% faster that '00'. Integer values also use less memory than string values. The clear function could better be written as follows: php Code:
The first loop generates an array of 8 values, each set to 0. The second loop generates an array of 8 value, each set to the array generated by the first loop. I benchmarked it and the approximate savings is 2/3rd over the current clear function. Hope this helps... |
|
#7
|
||||
|
||||
|
RE: 8 queen memory problem
I ran across this program this afternoon. It's not PHP, but perhaps it will give you some ideas.
Code:
-- The N Queens Problem:
-- Place N Queens on an NxN chess board
-- such that they don't threaten each other.
constant N = 8 -- try some other sizes
constant ROW = 1, COLUMN = 2
constant TRUE = 1, FALSE = 0
type square(sequence x)
-- a square on the board
return length(x) = 2
end type
type row(integer x)
-- a row on the board
return x >= 1 and x <= N
end type
function threat(square q1, square q2)
-- do two queens threaten each other?
if q1[COLUMN] = q2[COLUMN] then
return TRUE
elsif q1[ROW] - q1[COLUMN] = q2[ROW] - q2[COLUMN] then
return TRUE
elsif q1[ROW] + q1[COLUMN] = q2[ROW] + q2[COLUMN] then
return TRUE
elsif q1[ROW] = q2[ROW] then
return TRUE
else
return FALSE
end if
end function
function conflict(square q, sequence queens)
-- Would square p cause a conflict with other queens on board so far?
for i = 1 to length(queens) do
if threat(q, queens[i]) then
return TRUE
end if
end for
return FALSE
end function
integer soln
soln = 0 -- solution number
procedure print_board(sequence queens)
-- print a solution, showing the Queens on the board
integer k
position(1, 1)
printf(1, "Solution #%dnn ", soln)
for c = 'a' to 'a' + N - 1 do
printf(1, "%2s", c)
end for
puts(1, "n")
for r = 1 to N do
printf(1, "%2d ", r)
for c = 1 to N do
if find({r,c}, queens) then
puts(1, "Q ")
else
puts(1, ". ")
end if
end for
puts(1, "n")
end for
puts(1, "nPress Enter. (q to quit) ")
while TRUE do
k = get_key()
if k = 'q' then
abort(0)
elsif k != -1 then
exit
end if
end while
end procedure
procedure place_queen(sequence queens)
-- place queens on a NxN chess board
-- (recursive procedure)
row r -- only need to consider one row for each queen
if length(queens) = N then
soln += 1
print_board(queens)
return
end if
r = length(queens)+1
for c = 1 to N do
if not conflict({r,c}, queens) then
place_queen(append(queens, {r,c}))
end if
end for
end procedure
clear_screen()
place_queen({})
-Tim |
![]() |
| Viewing: Codewalkers Forums > Other Technologies > Programming Theory > 8 queen memory problem |
| Thread Tools | Search this Thread |
| Display Modes | Rate This Thread |
|
|
|
|
|
|
|