Write a program to solve this puzzle. yetifoot Senior Member Posts: 484 Threads: 14 Joined: Apr 2005 06-01-2006, 07:00 AM I found the following puzzle a bit of a head-scratcher, but got there in the end. What i'm interested in though is a computer program to solve it. I think that it may be some kind of exact cover problem, that could be solved by Knuths DLX. Maybe it isn't though. I'm sure good use of Boolean Logic is the way to solve it though. I'd love to see anyone's program. I started one but it was a bit brute-force, so i'm going to rethink. There will be no time-limits, or even winners to this challenge, but you do get a smug face if you can do it, and that's what counts! Code:```Neighbours Five people of different nationality live in a row of five houses of different colour. Each person prefers a different beverage, smokes a different brand of cigar and keeps a different kind of animal. Can you figure out who owns the fish?    1. The Brit lives in the Red house.    2. The Swede keeps dogs as pets.    3. The Dane drinks tea.    4. The Green house is on the left of the White house.    5. The owner of the Green house drinks coffee.    6. The person who smokes Pall Mall rears birds.    7. The owner of the Yellow house smokes Dunhill.    8. The man living in the centre house drinks milk.    9. The Norwegian lives in the first house.   10. The man who smokes Blends lives next to the man who keeps cats.   11. The man who keeps horses lives next to the man who smokes Dunhill.   12. The man who smokes Blue Master drinks beer.   13. The German smokes Prince.   14. The Norwegian lives next to the Blue house.   15. The man who smokes Blends has a neighbour who drinks water. Who owns the fish?``` http://puzzles.about.com/library/weekly/...riddle.htm answer below in tiny text: The German owns the fish (I hope!) EVEN MEN OF STEEL RUST. Moneo Posting Freak Posts: 1,956 Threads: 65 Joined: Jun 2003 06-01-2006, 07:14 AM Back in 1961, when I was a programmer trainee attending the Basic Computing course at IBM in NY, they gave us this same puzzle to work out manually. I finally figured it out, but I hated it. I still hate it. But, I never thought of programming it --- hummm. ***** Agamemnus Posting Freak Posts: 3,368 Threads: 195 Joined: Jan 2003 06-01-2006, 07:25 AM Well it all depends. I could just do PRINT [the answer] or I could take each string and have it spit out the answer.... EDIT: Code:```house:  unknown - unknown - unknown - unknown - unknown nation: unknown - unknown - unknown - unknown - unknown pet:    unknown - unknown - unknown - unknown - unknown drink:  unknown - unknown - unknown - unknown - unknown cigar:  unknown - unknown - unknown - unknown - unknown 8. The man living in the centre house drinks milk. 9. The Norwegian lives in the first house. house:  unknown   - unknown - unknown - unknown - unknown nation: norwegian - unknown - unknown - unknown - unknown pet:    unknown   - unknown - unknown - unknown - unknown drink:  unknown   - unknown - milk    - unknown - unknown cigar:  unknown   - unknown - unknown - unknown - unknown 14. The Norwegian lives next to the Blue house. house:  unknown   - blue    - unknown - unknown - unknown nation: norwegian - unknown - unknown - unknown - unknown pet:    unknown   - unknown - unknown - unknown - unknown drink:  unknown   - unknown - milk    - unknown - unknown cigar:  unknown   - unknown - unknown - unknown - unknown 4. The Green house is on the left of the White house. green <- white 5. The owner of the Green house drinks coffee. house:  unknown   - blue    - unknown - green   - white nation: norwegian - unknown - unknown - unknown - unknown pet:    unknown   - unknown - unknown - unknown - unknown drink:  unknown   - unknown - milk    - coffee  - unknown cigar:  unknown   - unknown - unknown - unknown - unknown 1. The Brit lives in the Red house. house:  yellow    - blue    - red     - green   - white nation: norwegian - unknown - brit    - unknown - unknown pet:    unknown   - unknown - unknown - unknown - unknown drink:  unknown   - unknown - milk    - coffee  - unknown cigar:  unknown   - unknown - unknown - unknown - unknown 7. The owner of the Yellow house smokes Dunhill. 11. The man who keeps horses lives next to the man who smokes Dunhill. house:  yellow    - blue    - red     - green   - white nation: norwegian - unknown - brit    - unknown - unknown pet:    unknown   - horses  - unknown - unknown - unknown drink:  unknown   - unknown - milk    - coffee  - unknown cigar:  dunhill   - unknown - unknown - unknown - unknown 15. The man who smokes Blends has a neighbour who drinks water. house:  yellow    - blue    - red     - green   - white nation: norwegian - unknown - brit    - unknown - unknown pet:    unknown   - horses  - unknown - unknown - unknown drink:  unknown   - unknown - milk    - coffee  - unknown cigar:  dunhill   - blends? - blends? - blends? - unknown 3. The Dane drinks tea. house:  yellow    - blue    - red     - green   - white nation: norwegian - unknown - brit    - unknown - unknown pet:    unknown   - horses  - unknown - unknown - unknown drink:  not tea   - unknown - milk    - coffee  - unknown cigar:  dunhill   - blends? - blends? - blends? - unknown house:  yellow     - blue    - red     - green   - white nation: norwegian  - unknown - brit    - unknown - unknown pet:    unknown    - horses  - unknown - unknown - unknown drink:  water/beer - tea?    - milk    - coffee  - tea? cigar:  dunhill    - blends? - blends? - blends? - unknown 12. The man who smokes Blue Master drinks beer. house:  yellow    - blue     - red     - green   - white nation: norwegian - unknown  - brit    - unknown - unknown pet:    unknown   - horses   - unknown - unknown - unknown drink:  water     - tea/beer - milk    - coffee  - tea/beer cigar:  dunhill   - blends?  - blends? - blends? - unknown house:  yellow    - blue   - red     - green   - white nation: norwegian - dane   - brit    - unknown - unknown pet:    unknown   - horses - unknown - unknown - unknown drink:  water     - tea    - milk    - coffee  - beer cigar:  dunhill   - blends - unknown - unknown - blue master 13. The German smokes Prince. house:  yellow    - blue   - red       - green   - white nation: norwegian - dane   - brit      - german  - unknown pet:    unknown   - horses - unknown   - unknown - unknown drink:  water     - tea    - milk      - coffee  - beer cigar:  dunhill   - blends - pall mall - prince - blue master 6. The person who smokes Pall Mall rears birds. 10. The man who smokes Blends lives next to the man who keeps cats. house:  yellow    - blue   - red       - green   - white nation: norwegian - dane   - brit      - german  - unknown pet:    cats      - horses - birds     - unknown - unknown drink:  water     - tea    - milk      - coffee  - beer cigar:  dunhill   - blends - pall mall - prince - blue master 2. The Swede keeps dogs as pets. house:  yellow    - blue   - red       - green   - white nation: norwegian - dane   - brit      - german  - swede pet:    cats      - horses - birds     - unknown - dogs drink:  water     - tea    - milk      - coffee  - beer cigar:  dunhill   - blends - pall mall - prince - blue master ------------------------- house:  yellow    - blue    - red       - green   - white nation: norwegian - dane    - brit      - german  - swede pet:    cats      - horses  - birds     - FISH    - dogs drink:  water     - tea     - milk      - coffee  - beer cigar:  dunhill   - blends  - pall mall - prince  - blue master``` EDITed for clarity. Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war." Visit www.neobasic.net to see rubbish in all its finest. yetifoot Senior Member Posts: 484 Threads: 14 Joined: Apr 2005 06-01-2006, 05:14 PM Thats great, but its not a program that solves the problem, merely one that relays your thought process. EVEN MEN OF STEEL RUST. TheAdventMaster Senior Member Posts: 476 Threads: 35 Joined: May 2006 06-01-2006, 06:11 PM Quote:Thats great, but its not a program that solves the problem, merely one that relays your thought process. Is the brain not a big program? Anywho, I suppose I *could* write a program to figure this out, but it's so much work... yetifoot Senior Member Posts: 484 Threads: 14 Joined: Apr 2005 06-01-2006, 07:48 PM I've found a solver on the net, and it's actually a very small program. I'll post it later if anyones interested. EVEN MEN OF STEEL RUST. Agamemnus Posting Freak Posts: 3,368 Threads: 195 Joined: Jan 2003 06-02-2006, 08:28 AM Well.... but then the question becomes what kind of logic the solver takes and in what form. You could simply reduce the problem into true/false statements and by conversion finally get the answer, but then there are a variety of issues, such as: * Should you manually convert into logic statements or put in English semantics rules to parse the words into logic? * Should you limit the semantics rules to this particular problem set? (house per person) * Should you limit it to the size of the problem set? (attribute size, person size.. or even a differentiation between attributes and persons...) Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war." Visit www.neobasic.net to see rubbish in all its finest. yetifoot Senior Member Posts: 484 Threads: 14 Joined: Apr 2005 06-02-2006, 04:53 PM Quote:Well.... but then the question becomes what kind of logic the solver takes and in what form. You could simply reduce the problem into true/false statements and by conversion finally get the answer, but then there are a variety of issues, such as: * Should you manually convert into logic statements or put in English semantics rules to parse the words into logic? * Should you limit the semantics rules to this particular problem set? (house per person) * Should you limit it to the size of the problem set? (attribute size, person size.. or even a differentiation between attributes and persons...) All this is your choice, as I said there are no rules. The one i started coding was very specific, and very brute force, so i ditched it to research more elegant, generic solutions. As an idea though, the source i have found on the net is about 30-40 lines of C++, and is *very* specific to this problem. EVEN MEN OF STEEL RUST. Agamemnus Posting Freak Posts: 3,368 Threads: 195 Joined: Jan 2003 06-03-2006, 12:09 AM EDIT: I am close to finishing. Here is my code so far. All I need to do is figure out how to make the code to do the last step... EDIT2: The last step got subdivided into about 3 steps and I'm finishing up the last part of the first step now. Also made some design changes. EDIT3: Tired. So tired.. EDIT4: So very close. Need to figure out just one last bit of code. Code:```'Alright, so here is something that solves this specific problem, with 5 attributes and 5 men. 'Before making the program, I want to have "clean" data. 'First, let's transform the sentences into easy to parse logic. Before that, let's define the 'variables. DECLARE SUB setNonAdjacentValuesToZero (matrix() AS BYTE, matrixloc() AS BYTE, i, j1, j2, position as BYTE) DECLARE SUB qsort.linked.string.lowstart (array1() AS STRING, array2() AS INTEGER, amax AS INTEGER) DECLARE FUNCTION findValue(ats() AS STRING, vtf AS STRING, a AS INTEGER, b AS INTEGER) AS INTEGER DEFINT A-Z DIM testarray1(0 TO 10) DIM shared attrib = 6 DIM shared attribpos = 5 DIM attribString\$(0 TO attrib-1) attribString\$(0) = "brit, swede, dane, norwegian, german" attribString\$(1) = "red, green, yellow, white, blue" attribString\$(2) = "dogs, cats, horses, birds, fish" attribString\$(3) = "water, beer, tea, coffee, milk" attribString\$(4) = "pall mall, blends, dunhill, prince, blue master" attribString\$(5) = "leftmost, 2nd, center, 4th, rightmost" DIM totAttrib: totAttrib = attrib*attribpos DIM matrixAttrib\$(0 TO totAttrib-1), matrixAttrib2\$(0 TO totAttrib-1) DIM linksTo(0 TO totAttrib-1) DIM tempAttrib\$(0 TO 1) DIM matrix(0 TO attrib-1, 0 TO attribpos-1, 0 TO attrib-1, 0 TO attribpos-1) AS byte for i = 0 to attrib-1 for j = 0 to attribpos-1 for k = 0 to attrib-1 for m = 0 to attribpos-1 matrix(i, j, k, m) = 1 next m, k, j, i DIM matrixSolution(0 TO attrib-1, 0 TO attribpos-1) AS BYTE DIM logicAmount = 15 DIM matrixloc(1 to logicAmount-1, 0 TO 6) AS BYTE, locpos DIM val1(0 TO 1), val2(0 to 1) DIM logic\$(0 to logicAmount-1) logic\$(0)  = "brit = red"                  '"The brit lives in the red house" logic\$(1)  = "swede = dogs"                 logic\$(2)  = "dane = tea"                  'spatial strings must be logic\$(3)  = "green = left of white"       'on the right side. logic\$(4)  = "green = coffee"               logic\$(5)  = "pall mall = birds" logic\$(6)  = "yellow = dunhill" logic\$(7)  = "center = milk" logic\$(8)  = "leftmost = norwegian" logic\$(9)  = "blends = next to cats" logic\$(10) = "horses = next to dunhill" logic\$(11) = "blue master = beer" logic\$(12) = "german = prince" logic\$(13) = "norwegian = next to blue" logic\$(14) = "blends = next to water" 'Now we transform the sentences into the matrix. 'Matrix starts by default having all 1's. 'values of matrix(): '0 = false '1 = true ' 'As an example, take: 'matrix(0, 0, 1, 1) = 1      [0 = nationality, next 0 = brit, 1 = color, next value = color type] = true/false/unknown 'matrix(0, 0, 1, 1) = 1 'matrix(0, 0, 1, 2) = 0 'matrix(0, 0, 1, 3) = 0 'matrix(0, 0, 1, 4) = 0 'This means that the brit has either a red house or a green house. 'matrix(0, 0, 1, 0) = 0 'matrix(0, 0, 1, 1) = 1 'matrix(0, 0, 1, 2) = 1 'matrix(0, 0, 1, 3) = 1 'matrix(0, 0, 1, 4) = 1 'This means that the brit lives next to someone with a red house, 'or in other words, the brit definitely does not have a red house. 'we also must temporarily add that SOMEONE next to the Brit has 'a red house. 'matrixloc(n, 0) = 0 'nationality 'matrixloc(n, 1) = 0 'brit 'matrixloc(n, 2) = 1 'house 'matrixloc(n, 3) = 1 'red 'matrixloc(n, 4) = 2 'next to 'n = n + 1 'If we know, at some point in the future, the position of the brit, 'we can limit the color of non-nearby houses to exclude red: 'Let's say the brit is in the center house: ' 'matrix(5, 1, 1, 0) = 0      [5 = house, 2 = 2nd house, 1 = color, next value = color type] 'matrix(5, 1, 1, 1) = 1 'matrix(5, 1, 1, 2) = 1 'matrix(5, 1, 1, 3) = 1 'matrix(5, 1, 1, 4) = 1 'matrix(5, 5, 1, 0) = 0      [the 2nd house] 'matrix(5, 5, 1, 1) = 1 'matrix(5, 5, 1, 2) = 1 'matrix(5, 5, 1, 3) = 1 'matrix(5, 5, 1, 4) = 1 'Let's parse AttribString\$ into matrixAttrib\$(). k=0 FOR i = 0 TO attrib-1 startLoc = 1 FOR j = 0 TO attribpos-1 IF j < attrib-1 THEN endLoc = INSTR(startLoc, attribString\$(i), ",") ELSE endLoc = LEN(attribString\$(i)) + 1 END IF matrixAttrib\$(k) = LCASE\$(LTRIM\$(RTRIM\$(MID\$(attribString\$(i), startLoc, endLoc-startLoc)))) matrixAttrib2\$(k) = matrixAttrib\$(k) k = k + 1 startLoc = endLoc + 1 NEXT j, i 'To parse the logic sentences, we need a function that gives the 'attribute type [i] (e.g. house) and attribute position [j] (e.g. red) 'from the name of the attribute. 'Each attribute name corresponds to a value 0 through attrib^2-1, 'which become i = (value \ attribpos) and j = value - i * attribpos. 'We can use a B-tree to find the value given a sorted list. 'So, we must sort a duplicate of matrixAttrib\$(k) along with a value link LinksTo. for i = 0 to totAttrib-1: LinksTo(i) = i: next i qsort.linked.string.lowstart matrixAttrib2\$(), LinksTo(), totAttrib-1 'The structure of the sentence is: '{spatial string set} [attribute name] = {spatial string set} [another attribute name] '{spatial string set} = {"left of", "right of", "next to"} 'Let's parse the sentences now... FOR i = 0 to logicAmount-1 'First, separate each word or phrase into two parts: startLoc = 1 endLoc = INSTR(startLoc, logic\$(i), "=") tempAttrib\$(0) = LCASE\$(LTRIM\$(RTRIM\$(MID\$(logic\$(i), startLoc, endLoc-startLoc)))) tempAttrib\$(1) = LCASE\$(LTRIM\$(RTRIM\$(MID\$(logic\$(i), endLoc+1)))) testLeft = INSTR(tempAttrib\$(1), "left of") If testLeft THEN pos1 = 1: tempAttrib\$(1) = LCASE\$(LTRIM\$(RTRIM\$(MID\$(tempAttrib\$(1), testLeft+7)))) testRight = INSTR(tempAttrib\$(1), "right of") If testRighth THEN pos1 = 2: tempAttrib\$(1) = LCASE\$(LTRIM\$(RTRIM\$(MID\$(tempAttrib\$(1), testRight+7)))) testNextTo = INSTR(tempAttrib\$(1), "next to") If testNextTo THEN pos1 = 3: tempAttrib\$(1) = LCASE\$(LTRIM\$(RTRIM\$(MID\$(tempAttrib\$(1), testNextTo+7)))) for j = 0 to 1 value = linksTo(findValue(matrixAttrib2\$(), tempAttrib\$(j), 0, totAttrib-1)) val1(j) = value \ attribpos val2(j) = value - val1(j)*attribpos next j SELECT CASE pos1 CASE 0 FOR k = 0 to attribpos-1 IF k <> val2(0) THEN matrix(val1(0), k, val1(1), val2(1)) = 0 matrix(val1(1), val2(1), val1(0), k) = 0 'if i = 4 then print logic\$(i); val1(1); val2(1); val1(0); k 'if i = 4 then print logic\$(i); val1(0); k; val1(1); val2(1) END IF NEXT k FOR k = 0 to attribpos-1 IF k <> val2(1) THEN matrix(val1(0), val2(0), val1(1), k) = 0 matrix(val1(1), k, val1(0), val2(0)) = 0 END IF NEXT k CASE ELSE FOR k = 0 to attribpos-1 IF k = val2(0) THEN matrix(val1(0), val2(0), val1(1), val2(1)) = 0 matrix(val1(1), val2(1), val1(0), val2(0)) = 0 END IF NEXT k matrixloc(locpos, 0) = val1(0) matrixloc(locpos, 1) = val2(0) matrixloc(locpos, 2) = val1(1) matrixloc(locpos, 3) = val2(1) matrixloc(locpos, 4) = pos1 - 1 locpos = locpos + 1 matrixloc(locpos, 0) = val1(1) matrixloc(locpos, 1) = val2(1) matrixloc(locpos, 2) = val1(0) matrixloc(locpos, 3) = val2(0) matrixloc(locpos, 4) = pos1 - 1 locpos = locpos + 1 END SELECT pos1 = 0 NEXT i 'How the solution is found: 'we go through matrixloc() and filter it through matrix(). 'step 1: 'If the location of an attribute is known that has a relative position, 'we can add it to matrix(): 'e.x.: 'if brit is next to a red house, 'then if red house position is known, 'we can set all positions except those two or one nearby to false for brit. 'also, if brit position is known, 'we can set all positions except those two or one nearby to false for red house. 'We go through all of the outstanding relative position truths this way. ' 'step 2: 'then, we go through matrix() and check for all but one conditions 'being false on some attribute and set that one to true. 'Then we go back to step 1 until we know who the fish belongs to. '(or, alternatively, that there are no unknowns) do ex1 = 0 FOR i = 0 to locpos - 1 for j = 0 to 1 IF matrixloc(i, 5+j) = 0 THEN 'check whether attribute 1 position is known. 'To do that, we check whether all other attributes are false. temp1 = 0 for k = 0 to attribpos-1 IF matrix(matrixloc(i, j+j), matrixloc(i, 1+j+j), 5, k) = 1 THEN temp2 = k: temp1 = temp1 + 1 next k IF temp1 = 1 THEN ex1 = 1 'make non-adjacent values equal to 0... 'e.g. if house red = brit, 'set house red <> swede, house red <> german, etc. '(the mirror value is set in the next pass of 'j', I think..) 'matrixloc(i, 4): 0 = left, 1 = right, 2 = next to. setNonAdjacentValuesToZero matrix(), matrixloc(), i, j*2, (1-j)*2, matrix(5, k, matrixloc(i, j+j), matrixloc(i, 1+j+j)) matrixloc(i, 5+j) = 1 END IF END IF NEXT j NEXT i 'Inheritance: 'If green <> white and green = coffee, then coffee <> white. for i = 0 to attrib-1 for j = 0 to attribpos-1 'if [some attribute] <> [some other attribute]... 'and [some attribute] def.= [another attribute]... 'then [some attribute] <> [another attribute]. for k = 0 to attrib-1 for m = 0 to attribpos-1 if i * attribpos + j <> k * attribpos + m then if matrix(i, j, k, m) = 0 THEN for n = 0 to attrib-1 temp1 = 0 for o = 0 to attribpos-1 if matrix(i, j, n, o) = 1 then temp2 = o: temp1 = temp1 + 1 NEXT o if i * attribpos + j <> n * attribpos + temp2 then if k * attribpos + m <> n * attribpos + temp2 then IF temp1 = 1 THEN if matrix(n, temp2, k, m) <> 0 THEN matrix(n, temp2, k, m) = 0 matrix(k, m, n, temp2) = 0 ex1 = 1 end if end if END IF END IF NEXT n END IF END IF next m, k, j, i 'Inheritance2: 'if coffee = german and german = red, then coffee = red. for i = 0 to attrib-1 for j = 0 to attribpos-1 for k = 0 to attrib-1 temp1 = 0 for m = 0 to attribpos-1 temp1 = matrix(i, j, k, m) if matrix(i, j, k, m) = 1 THEN temp3 = o: temp1 = temp1 + 1 next m if i * attribpos + j <> k * attribpos + temp3 then if temp1 = 1 then for n = 0 to attrib-1 temp1 = 0 for o = 0 to attribpos-1 if matrix(i, j, n, o) = 1 then temp2 = o: temp1 = temp1 + 1 NEXT o if i * attribpos + j <> n * attribpos + temp2 then if k * attribpos + temp3 <> n * attribpos + temp2 then IF temp1 = 1 THEN if matrix(k, temp3, n, temp2) <> 0 THEN matrix(k, temp3, n, temp2) = 0 matrix(n, temp2, k, temp3) = 0 ex1 = 1 end if end if END IF END IF NEXT n END IF END IF next k, j, i if ex1 = 0 then exit do loop for i = 0 to attrib-1 for j = 0 to attribpos-1 for k = 0 to attrib-1 for m = 0 to attribpos-1 IF matrixAttrib\$(i * attribpos + j) = "center" THEN IF matrix(i, j, k, m) = 0 THEN PRINT matrixAttrib\$(i * attribpos + j); " <> " ; matrixAttrib\$(k * attribpos + m); i ; j ; k; m END IF next m, k, j, i for i = 0 to attrib-1 for j = 0 to attribpos-1 for k = 5 to 5 temp1 = 0 for m = 0 to attribpos-1 if matrix(i, j, k, m) = 1 then temp2 = m: temp1 = temp1 + 1 next m if temp1 = 1 then matrixSolution(i, j) = k*attribpos + temp2 else matrixSolution(i, j) = -1 end if next k, j, i print for i = 0 to attrib-1 for j = 0 to attribpos-1 if matrixSolution(i, j) <> -1 then PRINT matrixAttrib\$(i * attribpos + j);" - ";matrixAttrib\$(matrixSolution(i,j)) end if next i, j sleep system SUB setNonAdjacentValuesToZero (matrix() AS BYTE, matrixloc() AS BYTE, i, j1, j2, position AS BYTE) leftadj = position - 1 rightadj = position + 1 FOR x = 0 to attribpos-1 SELECT CASE matrixloc(i, 4) CASE 0: IF x = leftadj THEN GOTO nextfor CASE 1: IF x = rightadj THEN GOTO nextfor CASE 2: IF x = leftadj OR x = rightadj THEN GOTO nextfor END SELECT matrix(5, x, matrixloc(i, j2), matrixloc(i, j2+1)) = 0 matrix(matrixloc(i, j2), matrixloc(i, j2+1), 5, x) = 0 nextfor: NEXT x END SUB FUNCTION findValue(ats() AS STRING, vtf AS STRING, a AS INTEGER, b AS INTEGER) AS INTEGER DO IF a > b then exit do n = (a + b) / 2 IF vtf = ats(n) THEN findValue = n: EXIT FUNCTION IF vtf < ats(n) THEN b = n - 1 ELSE a = n + 1 END IF LOOP findValue = -1 END FUNCTION SUB qsort.linked.string.lowstart (array1() AS STRING, array2() AS INTEGER, amax AS INTEGER) DIM g2(0 TO amax) AS INTEGER, h2(0 TO amax) AS INTEGER, i AS INTEGER, j AS INTEGER, r AS INTEGER, E AS INTEGER, g AS INTEGER, h AS INTEGER, k AS STRING E = 0: g2(0) = 0: h2(0) = amax e1: g = g2(E): h = h2(E) e2: i = g: j = h: r = (g + h) \ 2: k = array1(r) e3: IF array1(i) < k THEN i = i + 1: GOTO e3 e4: IF array1(j) > k THEN j = j - 1: GOTO e4 IF i <= j THEN SWAP array1(i), array1(j): SWAP array2(i), array2(j): i = i + 1: j = j - 1: IF i <= j THEN GOTO e3 IF j - g + i < h THEN IF i < h THEN g2(E) = i: h2(E) = h: E = E + 1 h = j ELSE IF g < j THEN g2(E) = g: h2(E) = j: E = E + 1 g = i END IF IF g < h THEN GOTO e2 ELSE E = E - 1: IF E >-1 THEN GOTO e1 ERASE g2, h2 END SUB``` Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war." Visit www.neobasic.net to see rubbish in all its finest. Agamemnus Posting Freak Posts: 3,368 Threads: 195 Joined: Jan 2003 06-09-2006, 05:56 AM I have not been able to crack the locational issues with "regular" logic so here is a possible system to do it, but I would rather use regular logic as this is a bit cumbersome... 1) First, construct a physical link map: "The Green house is on the left of the White house." & "The owner of the Green house drinks coffee. " translates to: G(a)-W(a) | C(d) 2) Now, take the current physical map that is available: 1. 2. 3. 4. 5. a. 0 B 0 0 0 b. N 0 0 0 0 c. 0 0 0 0 0 d. 0 0 M 0 0 e. 0 0 0 0 0 3) From that, test the link possibilities, starting with C: * which d. location(s) can C. fit in? * a1) If it fits, check the next on the link and wait for a position or 0. If you get a position, return your position and the previous one, else return 0. * a2) If it fits and it's the last one, return the position that it fits in. * b) If it doesn't fit, check the next possibility. * c) If no more possibilities, return 0. Note: Obviously this can be solved much faster through brute force, as there are only 5^5 possible combinations. (Don't quote me on that.) Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war." Visit www.neobasic.net to see rubbish in all its finest. « Next Oldest | Next Newest »