algorithm - Why doesn't the knight cover all the table? -


i want knight start @ (1,1) , try move on table. code:

canmove :: (int  -> int) -> (int  -> int) -> [(int,int)] -> bool  canmove (x) (y) list          | (x (fst lastmove),y (snd lastmove)) `elem` list = false         | newx> 8 || newy> 8 || newx<=0 || newy<=0 = false         | otherwise = true         lastmove = last list               newx = x (fst lastmove)               newy = y (snd lastmove)  move :: [(int, int)] -> [( int, int)] move list    | length list == 64 = list   | canmove (+1) (+2) list = move (list ++ [(x+1,y+2)])   | canmove (+2) (+1) list = move (list ++ [(x+2,y+1)])   | canmove (subtract 1) (+2) list = move (list ++ [(x-1,y+2)])   | canmove (subtract 2) (+1) list = move (list ++ [(x-2,y+1)])   | canmove (subtract 1) (subtract 2) list = move (list ++ [(x-1,y-2)])   | canmove (subtract 2) (subtract  1) list = move (list ++ [(x-2,y-1)])   | canmove (+1) (subtract 2) list = move (list ++ [(x+1,y-2)])   | canmove (+2) (subtract 1) list = move (list ++ [(x+2,y-1)])   | otherwise = list    lastmove = last list          x = fst lastmove          y = snd lastmove  y=length (move [(1,1)])  main = print $ y

why knight stop after 34 steps?

i assuming you're attempting solve knight's tour problem in haskell. in case, problem you're using greedy algorithm, fails knight's tour problem. if remove length y function, can see path algorithm chose.

[(1,1),(2,3),(3,5),(4,7),(6,8),(5,6),(7,7),(5,8),(4,6),(6,7),  (8,8),(7,6),(5,7),(7,8),(6,6),(8,7),(7,5),(6,3),(8,4),(6,5),  (8,6),(7,4),(5,5),(3,6),(4,8),(2,7),(1,5),(3,4),(2,6),(3,8),  (1,7),(2,5),(3,7),(1,8)] -- (1,8), can go either (4,6) or (3,5). -- we've been both of positions.

simply put, knight made "wrong" turn @ point , got stuck in position couldn't out without repeating position. circumvent this, you'll need use kind of backtracking algorithm, when knight makes mistake this, can undo moves , try else. fortunately you, haskell makes relatively easy list monad. if you're not familiar monads, they're integral haskell, , can learn them here.


-

Comments

Post a Comment

Popular posts from this blog

java - SSE Emitter : Manage timeouts and complete() -

i writing web app multiple listeners(evcentsource sse clients js) connected server . want store sse emitter per connected listener : can done in memory or other means assigning id each client able achieve far now question ; how send response/event specific client connected web app ? while doing sseemmiters stored either getting completed or timed out. how prevent ? how keep sseemmiter available open infinite time (till client closes) , send events selectively .
Read more

jquery - uncaught exception: DataTables Editor - remote hosting of code not allowed -

i'm trying implement crud operation using datatableseditor using datatables.but i'm getting error messages: 1)uncaught exception: datatables editor - remote hosting of code not allowed. please see http://editor.datatables.net details on how purchase editor license 2)typeerror: a.editor undefined 3) $.fn.datatable.editor not constructor" what reason? here configuration: <%@ page language="java" contenttype="text/html; charset=iso-8859-1" pageencoding="iso-8859-1"%> <!doctype html public "-//w3c//dtd html 4.01 transitional//en" "http://www.w3.org/tr/html4/loose.dtd"> <html> <head> <meta http-equiv="content-type" content="text/html; charset=iso-8859-1"> <title>insert title here</title> <link rel="stylesheet" type="text/css" href="//cdn.datatables.net/1.10.12/css/jquery.datatables.min.css"> <link re...
Read more

java - How to resolve error - package com.squareup.okhttp3 doesn't exist? -

i trying convert json java object use of gson in maven, following youtube video guidance - https://www.youtube.com/watch?v=vqgghm9pwe0 , theres error occurs when in main class error - package com.squareup.okhttp3 doesn't exist. code below: java package com.codebeasty.json; import com.squareup.okhttp3.okhttpclient; public class main { private static okhttpclient client = new okhttpclient(); public static void main (string [] args) { } } i put in dependency in pom.xml: <dependencies> <dependency> <groupid>com.squareup.okhttp3</groupid> <artifactid>okhttp</artifactid> <version>3.4.2</version> </dependency> <dependency> <groupid>com.google.code.gson</groupid> <artifactid>gson</artifactid> <version>2.8.0</version> </dependency> </dependencies> i dont understand why doesn't recognize com.squareup. there may need download? have downl...
Read more