SunQuest
           Programming Theory
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
User Name:
Password:
Remember me
Go Back   Codewalkers ForumsOther TechnologiesProgramming Theory

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Rate Thread Display Modes
 
Unread Codewalkers Forums Sponsor:
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  
Old December 20th, 2003, 03:46 PM
Rokm Rokm is offline
Codewalkers Newbie (0 - 499 posts)
 
Join Date: Apr 2007
Location: Idrija, Slovenia
Posts: 7 Rokm User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: < 1 sec
Reputation Power: 0
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

Reply With Quote
  #2  
Old December 20th, 2003, 03:54 PM
CodeKadiya CodeKadiya is offline
Codewalkers Regular (2000 - 2499 posts)
 
Join Date: Apr 2007
Location: Colombo,Sri Lanka
Posts: 2,313 CodeKadiya User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: < 1 sec
Reputation Power: 4
Send a message via Yahoo to CodeKadiya
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.

Reply With Quote
  #3  
Old December 20th, 2003, 03:55 PM
Rokm Rokm is offline
Codewalkers Newbie (0 - 499 posts)
 
Join Date: Apr 2007
Location: Idrija, Slovenia
Posts: 7 Rokm User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: < 1 sec
Reputation Power: 0
RE: 8 queen memory problem

but why are those loops using so much memory? is it possible to make that more memory friendly...??

Reply With Quote
  #4  
Old December 21st, 2003, 12:00 AM
Matt Matt is offline
Moderator
Codewalkers Specialist (4000 - 4499 posts)
 
Join Date: Apr 2007
Location: Florida
Posts: 4,158 Matt User rank is Private First Class (20 - 50 Reputation Level)Matt User rank is Private First Class (20 - 50 Reputation Level) 
Time spent in forums: 4 h 10 m 20 sec
Reputation Power: 6
RE: 8 queen memory problem

[moved to the theory forum. I think you will get better discussion here.]

Reply With Quote
  #5  
Old December 21st, 2003, 12:10 AM
CodeKadiya CodeKadiya is offline
Codewalkers Regular (2000 - 2499 posts)
 
Join Date: Apr 2007
Location: Colombo,Sri Lanka
Posts: 2,313 CodeKadiya User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: < 1 sec
Reputation Power: 4
Send a message via Yahoo to CodeKadiya
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!!!!

Reply With Quote
  #6  
Old December 31st, 2003, 05:41 AM
bluephoenix's Avatar
bluephoenix bluephoenix is offline
Levelheaded Curmudgeon
Codewalkers Novice (500 - 999 posts)
 
Join Date: Apr 2007
Location: Syracuse, NY
Posts: 507 bluephoenix User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 7 h 13 m 2 sec
Reputation Power: 2
Send a message via AIM to bluephoenix
RE: 8 queen memory problem

Quote:
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.


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:
Original - php Code
  1. function clear() {
  2.   for ($i = 1; $i <= 8; $i++) {$zeroset[] = 0; }
  3.   for ($i = 1; $i <= 8; $i++) {$temp_board[] = $zeroset; }
  4.   return $temp_board;
  5. }


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...

Reply With Quote
  #7  
Old January 2nd, 2004, 04:03 AM
bluephoenix's Avatar
bluephoenix bluephoenix is offline
Levelheaded Curmudgeon
Codewalkers Novice (500 - 999 posts)
 
Join Date: Apr 2007
Location: Syracuse, NY
Posts: 507 bluephoenix User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 7 h 13 m 2 sec
Reputation Power: 2
Send a message via AIM to bluephoenix
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

Reply With Quote
Reply

Viewing: Codewalkers ForumsOther TechnologiesProgramming Theory > 8 queen memory problem


Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump


Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
  
 





© 2003-2008 by Developer Shed. All rights reserved. DS Cluster 4 hosted by Hostway