Under passive RFID environment, this paper presents a new localization of a mobile robot traversing over the floor covered with tags, which is superior to existing methods in terms of estimation performance and cost effectiveness. Basically, it is assumed that a mobile robot is traveling along a series of straight line segments, each segment at a certain constant velocity, and that the number of tags sensed by a mobile robot at each sampling instant is at most one. First, for a given line segment with known starting point, the velocity and position of a mobile robot is estimated using the spatial and temporal information acquired from the traversed tag. Some discussions are made on the validity of the basic assumptions and the localization for the initial segment with unknown starting point. Second, for a given tag distribution density, the optimal tag arrangement is considered to reduce the position estimation error as well as to make easy the tag attachment on the floor. After reviewing typical tag arrangements, the pseudorandom tag arrangement is devised inspired from the Sudoku puzzle, a number placement puzzle. Third, through experiments using our passive RFID localization system, the validity and performance of the mobile robot localization proposed in this paper is demonstrated.